×

Provable sample-efficient sparse phase retrieval initialized by truncated power method. (English) Zbl 1516.94009

Summary: We study the sparse phase retrieval problem, recovering an \(s\)-sparse length-\(n\) signal from \(m\) magnitude-only measurements. Two-stage non-convex approaches have drawn much attention in recent studies. Despite non-convexity, many two-stage algorithms provably converge to the underlying solution linearly when appropriately initialized. However, in terms of sample complexity, the bottleneck of those algorithms with Gaussian random measurements often comes from the initialization stage. Although the refinement stage usually needs only \(m=\Omega(s\log n)\) measurements, the widely used spectral initialization in the initialization stage requires \(m=\Omega(s^2\log n)\) measurements to produce a desired initial guess, which causes the total sample complexity order-wisely more than necessary. To reduce the number of measurements, we propose a truncated power method to replace the spectral initialization for non-convex sparse phase retrieval algorithms. We prove that \(m=\Omega(\bar{s}s\log n)\) measurements, where \(\bar{s}\) is the stable sparsity of the underlying signal, are sufficient to produce a desired initial guess. When the underlying signal contains only very few significant components, the sample complexity of the proposed algorithm is \(m=\Omega(s\log n)\) and optimal. Numerical experiments illustrate that the proposed method is more sample-efficient than state-of-the-art algorithms.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
90C26 Nonconvex programming, global optimization
62H25 Factor analysis and principal components; correspondence analysis

References:

[1] Bahmani, S.; Romberg, J., Efficient compressive phase retrieval with constrained sensing vectors, Advances in Neural Information Processing Systems, vol 28 (2015)
[2] Bahmani, S.; Romberg, J., A flexible convex relaxation for phase retrieval, Electron. J. Stat., 11, 5254-81 (2017) · Zbl 1408.62032 · doi:10.1214/17-EJS1378SI
[3] Balakrishnan, S.; Du, S. S.; Li, J.; Singh, A., Computationally efficient robust sparse estimation in high dimensions, pp 169-212 (2017), PMLR
[4] Balan, R.; Casazza, P.; Edidin, D., On signal reconstruction without phase, Appl. Comput. Harmon. Anal., 20, 345-56 (2006) · Zbl 1090.94006 · doi:10.1016/j.acha.2005.07.001
[5] Berthet, Q.; Rigollet, P., Complexity theoretic lower bounds for sparse principal component detection, pp 1046-66 (2013), PMLR
[6] Cai, J-F; Huang, M.; Li, D.; Wang, Y., The global landscape of phase retrieval I: perturbed amplitude models, Ann. Appl. Math., 37, 437-512 (2021) · Zbl 1499.94017 · doi:10.4208/aam.OA-2021-0009
[7] Cai, J-F; Huang, M.; Li, D.; Wang, Y., The global landscape of phase retrieval II: quotient intensity models, Ann. Appl. Math., 38, 62-114 (2022) · Zbl 1499.94018 · doi:10.4208/aam.OA-2021-0010
[8] Cai, J-F; Huang, M.; Li, D.; Wang, Y., Nearly optimal bounds for the global geometric landscape of phase retrieval (2022)
[9] Cai, J-F; Huang, M.; Li, D.; Wang, Y., Solving phase retrieval with random initial guess is nearly as good as by spectral initialization, Appl. Comput. Harmon. Anal., 58, 60-84 (2022) · Zbl 1485.94015 · doi:10.1016/j.acha.2022.01.002
[10] Cai, J-F; Jiao, Y.; Lu, X.; You, J., Sample-efficient sparse phase retrieval via stochastic alternating minimization, IEEE Trans. Signal Process., 70, 4951-66 (2022) · Zbl 07911585 · doi:10.1109/TSP.2022.3214091
[11] Cai, J-F; Li, J.; Lu, X.; You, J., Sparse signal recovery from phaseless measurements via hard thresholding pursuit, Appl. Comput. Harmon. Anal., 56, 367-90 (2022) · Zbl 1479.94058 · doi:10.1016/j.acha.2021.10.002
[12] Cai, J-F; Li, J.; Xia, D., Generalized low-rank plus sparse tensor estimation by fast Riemannian optimization, J. Am. Stat. Assoc., 1-17 (2022) · Zbl 1506.62470 · doi:10.1080/01621459.2021.1906684
[13] Cai, J-F; Wei, K., Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity, J. Comput. Math.
[14] Cai, T. T.; Li, X.; Ma, Z., Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow, Ann. Stat., 44, 2221-51 (2016) · Zbl 1349.62019 · doi:10.1214/16-AOS1443
[15] Candes, E. J.; Eldar, Y. C.; Strohmer, T.; Voroninski, V., Phase retrieval via matrix completion, SIAM Rev., 57, 225-51 (2015) · Zbl 1344.49057 · doi:10.1137/151005099
[16] Candes, E. J.; Li, X.; Soltanolkotabi, M., Phase retrieval via Wirtinger flow: theory and algorithms, IEEE Trans. Inf. Theory, 61, 1985-2007 (2015) · Zbl 1359.94069 · doi:10.1109/TIT.2015.2399924
[17] Chen, Y.; Candès, E. J., Solving random quadratic systems of equations is nearly as easy as solving linear systems, Commun. Pure Appl. Math., 70, 822-83 (2017) · Zbl 1379.90024 · doi:10.1002/cpa.21638
[18] Chen, Y.; Chi, Y.; Goldsmith, A. J., Exact and stable covariance estimation from quadratic sampling via convex programming, IEEE Trans. Inf. Theory, 61, 4034-59 (2015) · Zbl 1359.62181 · doi:10.1109/TIT.2015.2429594
[19] Fienup, J. R., Phase retrieval algorithms: a comparison, Appl. Opt., 21, 2758-69 (1982) · doi:10.1364/AO.21.002758
[20] Goldstein, T.; Studer, C., Phasemax: convex phase retrieval via basis pursuit, IEEE Trans. Inf. Theory, 64, 2675-89 (2018) · Zbl 1390.94194 · doi:10.1109/TIT.2018.2800768
[21] Hand, P.; Voroninski, V., An elementary proof of convex phase retrieval in the natural parameter space via the linear program phasemax, Commun. Math. Sci., 16, 2047-51 (2018) · Zbl 1441.94040 · doi:10.4310/CMS.2018.v16.n7.a13
[22] Harrison, R. W., Phase problem in crystallography, J. Opt. Soc. Am. A, 10, 1046-55 (1993) · doi:10.1364/JOSAA.10.001046
[23] Horn, R. A.; Johnson, C. R., Matrix Analysis (2012), Cambridge: Cambridge University Press, Cambridge
[24] Iwen, M.; Viswanathan, A.; Wang, Y., Robust sparse phase retrieval made easy, Appl. Comput. Harmon. Anal., 42, 135-42 (2017) · Zbl 1393.94274 · doi:10.1016/j.acha.2015.06.007
[25] Jagatap, G.; Hegde, C., Sample-efficient algorithms for recovering structured signals from magnitude-only measurements, IEEE Trans. Inf. Theory, 65, 4434-56 (2019) · Zbl 1432.94023 · doi:10.1109/TIT.2019.2902924
[26] Journée, M.; Nesterov, Y.; Richtárik, P.; Sepulchre, R., Generalized power method for sparse principal component analysis, J. Mach. Learn. Res., 11, 517-53 (2010) · Zbl 1242.62048
[27] Laurent, B.; Massart, P., Adaptive estimation of a quadratic functional by model selection, Ann. Stat., 28, 1302-38 (2000) · Zbl 1105.62328 · doi:10.1214/aos/1015957395
[28] Li, Z.; Cai, J.; Wei, K., Toward the optimal construction of a loss function without spurious local minima for solving quadratic equations, IEEE Trans. Inf. Theory, 66, 3242-60 (2020) · Zbl 1448.65053 · doi:10.1109/TIT.2019.2956922
[29] Liu, Z.; Ghosh, S.; Scarlett, J., Towards sample-optimal compressive phase retrieval with sparse and generative priors, Advances in Neural Information Processing Systems, vol 34, 17656-68 (2021)
[30] Luo, W.; Alghamdi, W.; Lu, Y. M., Optimal spectral initialization for signal recovery with applications to phase retrieval, IEEE Trans. Signal Process., 67, 2347-56 (2019) · Zbl 1458.94111 · doi:10.1109/TSP.2019.2904918
[31] Ma, C.; Wang, K.; Chi, Y.; Chen, Y., Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval and matrix completion, pp 3345-54 (2018), PMLR
[32] Ma, Z., Sparse principal component analysis and iterative thresholding, Ann. Stat., 41, 772-801 (2013) · Zbl 1267.62074 · doi:10.1214/13-AOS1097
[33] Mallat, S., A Wavelet Tour of Signal Processing (1998), New York: Academic, New York · Zbl 1125.94306
[34] Miao, J.; Ishikawa, T.; Shen, Q.; Earnest, T., Extending x-ray crystallography to allow the imaging of noncrystalline materials, cells and single protein complexes, Annu. Rev. Phys. Chem., 59, 387-410 (2008) · doi:10.1146/annurev.physchem.59.032607.093642
[35] Moghaddam, B.; Weiss, Y.; Avidan, S., Spectral bounds for sparse PCA: exact and greedy algorithms, Advances in Neural Information Processing Systems, vol 18 (2005)
[36] Mondelli, M.; Montanari, A., Fundamental limits of weak recovery with applications to phase retrieval, Found. Comput. Math., 19, 703-73 (2019) · Zbl 1464.62296 · doi:10.1007/s10208-018-9395-y
[37] Netrapalli, P.; Jain, P.; Sanghavi, S., Phase retrieval using alternating minimization, pp 2796-804 (2013)
[38] Netrapalli, P.; Jain, P.; Sanghavi, S., Phase retrieval using alternating minimization, IEEE Trans. Signal Process., 63, 4814-26 (2015) · Zbl 1394.94421 · doi:10.1109/TSP.2015.2448516
[39] Salehi, F.; Abbasi, E.; Hassibi, B., Learning without the phase: regularized phasemax achieves optimal sample complexity, Advances in Neural Information Processing Systems, vol 31 (2018)
[40] Shechtman, Y.; Eldar, Y. C.; Cohen, O.; Chapman, H. N.; Miao, J.; Segev, M., Phase retrieval with application to optical imaging: a contemporary overview, IEEE Signal Process. Mag., 32, 87-109 (2015) · doi:10.1109/MSP.2014.2352673
[41] Shen, Y.; Li, J.; Cai, J-F; Xia, D., Computationally efficient and statistically optimal robust low-rank matrix estimation (2022)
[42] Soltanolkotabi, M., Structured signal recovery from quadratic measurements: breaking sample complexity barriers via nonconvex optimization, IEEE Trans. Inf. Theory, 65, 2374-400 (2019) · Zbl 1431.94025 · doi:10.1109/TIT.2019.2891653
[43] Sun, J.; Qu, Q.; Wright, J., A geometric analysis of phase retrieval, Found. Comput. Math., 18, 1131-98 (2018) · Zbl 1401.94049 · doi:10.1007/s10208-017-9365-9
[44] Tong, T.; Ma, C.; Chi, Y., Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent, J. Mach. Learn. Res., 22, 150-1 (2021) · Zbl 07415093
[45] Tong, T.; Ma, C.; Prater-Bennette, A.; Tripp, E.; Chi, Y., Scaling and scalability: provable nonconvex low-rank tensor estimation from incomplete measurements, J. Mach. Learn. Res., 23, 1-77 (2022)
[46] Vershynin, R., High-Dimensional Probability: An Introduction With Applications in Data Science, vol 47 (2018), Cambridge: Cambridge University Press, Cambridge · Zbl 1430.60005
[47] Waldspurger, I.; d’Aspremont, A.; Mallat, S., Phase recovery, maxcut and complex semidefinite programming, Math. Program., 149, 47-81 (2015) · Zbl 1329.94018 · doi:10.1007/s10107-013-0738-9
[48] Walther, A., The question of phase retrieval in optics, J. Mod. Opt., 10, 41-49 (1963) · doi:10.1080/713817747
[49] Wang, G.; Giannakis, G., Solving random systems of quadratic equations via truncated generalized gradient flow, pp 568-76 (2016)
[50] Wang, G.; Zhang, L.; Giannakis, G. B.; Akakaya, M.; Chen, J., Sparse phase retrieval via truncated amplitude flow, IEEE Trans. Signal Process., 66, 479-91 (2017) · Zbl 1414.94656 · doi:10.1109/TSP.2017.2771733
[51] Wang, Y.; Xu, Z., Phase retrieval for sparse signals, Appl. Comput. Harmon. Anal., 37, 531-44 (2014) · Zbl 1297.94009 · doi:10.1016/j.acha.2014.04.001
[52] Wei, K.; Cai, J-F; Chan, T. F.; Leung, S., Guarantees of Riemannian optimization for low rank matrix recovery, SIAM J. Matrix Anal. Appl., 37, 1198-222 (2016) · Zbl 1347.65109 · doi:10.1137/15M1050525
[53] Wu, F.; Rebeschini, P., Hadamard Wirtinger flow for sparse phase retrieval, pp 982-90 (2021), PMLR
[54] Yuan, X-T; Zhang, T., Truncated power method for sparse eigenvalue problems, J. Mach. Learn. Res., 14, 899-925 (2013) · Zbl 1320.62141
[55] Zhang, H.; Liang, Y., Reshaped Wirtinger flow for solving quadratic system of equations, pp 2622-30 (2016)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.