×

Sparse signal recovery from phaseless measurements via hard thresholding pursuit. (English) Zbl 1479.94058

Summary: In this paper, we consider the sparse phase retrieval problem, recovering an \(s\)-sparse signal \(\mathfrak{x}^\natural\in\mathbb{R}^n\) from \(m\) phaseless samples \(y_i=|\langle\mathfrak{x}^\natural,\mathfrak{a}_i\rangle|\) for \(i=1,\dots,m\). Existing sparse phase retrieval algorithms are usually first-order and hence converge at most linearly. Inspired by the hard thresholding pursuit (HTP) algorithm in compressed sensing, we propose an efficient second-order algorithm for sparse phase retrieval. Our proposed algorithm is theoretically guaranteed to give an exact sparse signal recovery in finite (in particular, at most \(O(\log m+\log(\| \mathfrak{x}^\natural \|_2/| x_{\min}^\natural|))\) steps, when \(\{\mathfrak{a}_i\}_{i=1}^m\) are i.i.d. standard Gaussian random vector with \(m\sim O(s\log(n/s))\) and the initialization is in a neighborhood of the underlying sparse signal. Together with a spectral initialization, our algorithm is guaranteed to have an exact recovery from \(O(s^2\log n)\) samples. Since the computational cost per iteration of our proposed algorithm is the same order as popular first-order algorithms, our algorithm is extremely efficient. Experimental results show that our algorithm can be several times faster than existing sparse phase retrieval algorithms.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)

References:

[1] Bahmani, S.; Romberg, J., A flexible convex relaxation for phase retrieval, Electron. J. Stat., 11, 2, 5254-5281 (2017) · Zbl 1408.62032
[2] Balan, R.; Casazza, P.; Edidin, D., On signal reconstruction without phase, Appl. Comput. Harmon. Anal., 20, 3, 345-356 (2006) · Zbl 1090.94006
[3] Blumensath, T., Accelerated iterative hard thresholding, Signal Process., 92, 3, 752-756 (2012)
[4] Blumensath, T.; Davies, M. E., Iterative thresholding for sparse approximations, J. Fourier Anal. Appl., 14, 5-6, 629-654 (2008) · Zbl 1175.94060
[5] Bouchot, J.-L.; Foucart, S.; Hitczenko, P., Hard thresholding pursuit algorithms: number of iterations, Appl. Comput. Harmon. Anal., 41, 2, 412-435 (2016) · Zbl 1346.65012
[6] Cai, J.-F.; Wei, K., Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity (2018), arXiv preprint
[7] Cai, T. T.; Li, X.; Ma, Z., Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow, Ann. Stat., 44, 5, 2221-2251 (2016) · Zbl 1349.62019
[8] Candes, E. J., The restricted isometry property and its implications for compressed sensing, C. R. Math., 346, 9-10, 589-592 (2008) · Zbl 1153.94002
[9] Candes, E. J.; Eldar, Y. C.; Strohmer, T.; Voroninski, V., Phase retrieval via matrix completion, SIAM Rev., 57, 2, 225-251 (2015) · Zbl 1344.49057
[10] Candes, E. J.; Li, X.; Soltanolkotabi, M., Phase retrieval via Wirtinger flow: theory and algorithms, IEEE Trans. Inf. Theory, 61, 4, 1985-2007 (2015) · Zbl 1359.94069
[11] Candes, E. J.; Tao, T., Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 12, 4203-4215 (2005) · Zbl 1264.94121
[12] Chen, Y.; Candes, E., Solving random quadratic systems of equations is nearly as easy as solving linear systems, (Advances in Neural Information Processing Systems (2015)), 739-747
[13] Chen, Y.; Chi, Y.; Fan, J.; Ma, C., Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval, Math. Program., 176, 1-2, 5-37 (2019) · Zbl 1415.90086
[14] Conca, A.; Edidin, D.; Hering, M.; Vinzant, C., An algebraic characterization of injectivity in phase retrieval, Appl. Comput. Harmon. Anal., 38, 2, 346-356 (2015) · Zbl 1354.42003
[15] Fienup, J. R., Phase retrieval algorithms: a comparison, Appl. Opt., 21, 15, 2758-2769 (1982)
[16] Foucart, S., Hard thresholding pursuit: an algorithm for compressive sensing, SIAM J. Numer. Anal., 49, 6, 2543-2563 (2011) · Zbl 1242.65060
[17] Foucart, S.; Rauhut, H., An invitation to compressive sensing, (A Mathematical Introduction to Compressive Sensing (2013), Springer), 1-39 · Zbl 1315.94002
[18] Gao, B.; Xu, Z., Gauss-Newton method for phase retrieval, IEEE Trans. Signal Process., 65, 22, 5885-5896 (2017) · Zbl 1414.94207
[19] Gerchberg, R. W., A practical algorithm for the determination of the phase from image and diffraction plane pictures, Optik, 35, 237-246 (1972)
[20] Goldstein, T.; Studer, C., Phasemax: convex phase retrieval via basis pursuit, IEEE Trans. Inf. Theory, 64, 4, 2675-2689 (2018) · Zbl 1390.94194
[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, 7, 2047-2051 (2018) · Zbl 1441.94040
[22] Harrison, R. W., Phase problem in crystallography, J. Opt. Soc. Am. A, 10, 5, 1046-1055 (1993)
[23] Huang, J.; Jiao, Y.; Jin, B.; Liu, J.; Lu, X.; Yang, C., A unified primal dual active set algorithm for nonconvex sparse recovery, Stat. Sci., 36, 2, 215-238 (2021) · Zbl 07368234
[24] Iwen, M.; Viswanathan, A.; Wang, Y., Robust sparse phase retrieval made easy, Appl. Comput. Harmon. Anal., 42, 1, 135-142 (2017) · Zbl 1393.94274
[25] Jagatap, G.; Hegde, C., Sample-efficient algorithms for recovering structured signals from magnitude-only measurements, IEEE Trans. Inf. Theory, 65, 7, 4434-4456 (2019) · Zbl 1432.94023
[26] Li, X.; Voroninski, V., Sparse signal recovery from quadratic measurements via convex programming, SIAM J. Math. Anal., 45, 5, 3019-3033 (2013) · Zbl 1320.94023
[27] 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, 5, 3242-3260 (2020) · Zbl 1448.65053
[28] Luo, W.; Alghamdi, W.; Lu, Y. M., Optimal spectral initialization for signal recovery with applications to phase retrieval, IEEE Trans. Signal Process., 67, 9, 2347-2356 (2019) · Zbl 1458.94111
[29] Ma, C.; Liu, X.; Wen, Z., Globally convergent Levenberg-Marquardt method for phase retrieval, IEEE Trans. Inf. Theory, 65, 4, 2343-2359 (2018) · Zbl 1431.94018
[30] Ma, C.; Wang, K.; Chi, Y.; Chen, Y., Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval and matrix completion, (International Conference on Machine Learning (2018), PMLR), 3345-3354
[31] Mallat, S., A Wavelet Tour of Signal Processing (1999), Elsevier · Zbl 0998.94510
[32] 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)
[33] Needell, D.; Tropp, J. A., CoSaMP: iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26, 3, 301-321 (2009) · Zbl 1163.94003
[34] Netrapalli, P.; Jain, P.; Sanghavi, S., Phase retrieval using alternating minimization, (Advances in Neural Information Processing Systems (2013)), 2796-2804
[35] Soltanolkotabi, M., Structured signal recovery from quadratic measurements: breaking sample complexity barriers via nonconvex optimization, IEEE Trans. Inf. Theory, 65, 4, 2374-2400 (2019) · Zbl 1431.94025
[36] Sun, J.; Qu, Q.; Wright, J., A geometric analysis of phase retrieval, Found. Comput. Math., 18, 5, 1131-1198 (2018) · Zbl 1401.94049
[37] Tan, Y. S.; Vershynin, R., Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval (2019), arXiv preprint
[38] Tan, Y. S.; Vershynin, R., Phase retrieval via randomized Kaczmarz: theoretical guarantees, Inf. Inference, 8, 1, 97-123 (2019) · Zbl 1476.90224
[39] Waldspurger, I., Phase retrieval with random Gaussian sensing vectors by alternating projections, IEEE Trans. Inf. Theory, 64, 5, 3301-3312 (2018) · Zbl 1395.94172
[40] Walther, A., The question of phase retrieval in optics, J. Mod. Opt., 10, 1, 41-49 (1963)
[41] Wang, G.; Giannakis, G. B.; Eldar, Y. C., Solving systems of random quadratic equations via truncated amplitude flow, IEEE Trans. Inf. Theory, 64, 2, 773-794 (2017) · Zbl 1390.90451
[42] Wang, G.; Zhang, L.; Giannakis, G. B.; Akçakaya, M.; Chen, J., Sparse phase retrieval via truncated amplitude flow, IEEE Trans. Signal Process., 66, 2, 479-491 (2018) · Zbl 1414.94656
[43] Wang, Y.; Xu, Z., Phase retrieval for sparse signals, Appl. Comput. Harmon. Anal., 37, 3, 531-544 (2014) · Zbl 1297.94009
[44] Wei, K., Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study, Inverse Probl., 31, 12, Article 125008 pp. (2015) · Zbl 1332.65045
[45] Zhang, H.; Zhou, Y.; Liang, Y.; Chi, Y., A nonconvex approach for phase retrieval: reshaped Wirtinger flow and incremental algorithms, J. Mach. Learn. Res., 18, 1, 5164-5198 (2017) · Zbl 1440.94020
[46] Zhou, S.; Xiu, N.; Qi, H.-D., Global and quadratic convergence of newton hard-thresholding pursuit (2019), arXiv preprint
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.