The sampling complexity on nonconvex sparse phase retrieval problem. (English) Zbl 07776392
Summary: This paper discusses the k-sparse complex signal recovery from quadratic measurements via the \(\ell_p\)-minimization model, where \(0 < p\leq 1\). We establish the \(\ell_p\) restricted isometry property over simultaneously low-rank and sparse matrices, which is a weaker restricted isometry property to guarantee the successful recovery in the \(\ell_p\) case. The main result is to demonstrate that \(\ell_p\)-minimization can recover complex \(k\)-sparse signals from \(m\gtrsim k+pk\log(n/k)\) complex Gaussian quadratic measurements with high probability. The resulting sufficient condition is met by fewer measurements for smaller \(p\) and reaches \(m\gtrsim k\) when \(p\) turns to zero. Furthermore, an iteratively-reweighted algorithm is proposed. Numerical experiments also demonstrate that \(\ell_p\) minimization with \(0< p < 1\) performs better than \(\ell_1\) minimization.
Keywords:
nonconvex optimization; restricted isometry property; sampling complexity; sparse phase retrievalReferences:
| [1] | J.R. Fienup, Phase retrieval algorithms: a comparison, Appl, Optics, 21 (1982), 2758-2769. |
| [2] | R.W. Gerchberg, W.O. Saxton, A practical algorithm for the determination of phase from image and diffrac-tion plane pictures, Optik 35 (1972), 237-250. |
| [3] | J. Miao, P. Charalambous, J. Kirz, D. Sayre, Extending the methodology of x-ray crystallography to allow imaging of micrometer-sized non-crystalline specimens, Nature, 400 (1999), 342-344. |
| [4] | R. Balan, P. Casazza, D. Edidin, On signal reconstruction without phase, Appl. Comput. Harmonic Anal. 20 (2006), 345-356. · Zbl 1090.94006 |
| [5] | A. Conca, D. Edidin, M. Hering, C. Vinzant, Algebraic characterization of injectivity in phase retrieval, Appl. Comput. Harmonic Anal. 38 (2015), 346-356. · Zbl 1354.42003 |
| [6] | E. J. Candès, X. Li. Solving quadratic equations via phaselift when there are about as many equations as unknowns, Found. Comput. Math. 14(5): 1017-1026, 2014. · Zbl 1312.90054 |
| [7] | E. J. Candès, T. Stromher, V. Voroninshi. PhaseLift: Exact and stable signal recovery from magnitude mea-surements via convex programming, Commun. Pure Appl. Math. 66 (2013), 1241-1274. · Zbl 1335.94013 |
| [8] | E. J. Candès, X. Li, M. Soltanolkotabi. Phase retrieval via Wirtinger flow: Theory and algorithms, IEEE Trans. Info. Theory 61 (2015), 1985-2007. · Zbl 1359.94069 |
| [9] | P. Schniter, S. Rangan. Compressive phase retrieval via generalized approximate message passing, IEEE Trans. Signal Process. 63 (2015), 1043-1055. · Zbl 1394.94506 |
| [10] | Y. Xia, L. Zhou. Adaptive iterative hard thresholding for low-rank matrix recovery and rank-one measure-ments, J. Complexity 76: 101725, 2023. · Zbl 1510.94067 |
| [11] | H. Zhang, Y. Liang, Reshaped Wirtinger flow for solving quadratic system of equations, Advances in Neural Information Processing Systems, pp. 2630-2638, 2016. |
| [12] | Y. Wang, Z. Xu. Phase retrieval for sparse signals, Appl. Comput. Harmon. Anal. 37 (2014), 531-544. · Zbl 1297.94009 |
| [13] | V. Voroninski, Z. Xu, A strong restricted isometry property with an application to phaseless compressed sensing, Appl. Comput. Harmon. Anal. 40 (2016), 386-395. · Zbl 1338.94024 |
| [14] | Y. Xia, Z. Xu, The recovery of complex sparse signals from few phaseless measurements, Appl. Comput. Harmon. Anal. 50 (2021), 1-15. · Zbl 1460.94027 |
| [15] | Z. Yang, C. Zhang, L. Xie, Robust compressive phase retrieval via L1 minimization with application to image reconstruction, arXiv:1302.0081, 2013. |
| [16] | G. Wang, L. Zhang, G.B. Giannakis. Sparse phase retrieval via truncated amplitude flow, IEEE Trans. Signal Process. 66 (2018), 479-491. · Zbl 1414.94656 |
| [17] | G. Jagatap, C. Hegde, Sample-efficient algorithms for recovering structured signals from magnitude-only measurements, IEEE Trans. Info. Theory 65 (2019), 4434-4456. · Zbl 1432.94023 |
| [18] | Y. Xia, Z. Xu, Sparse phase retrieval via PhaseLiftOff, IEEE Trans. Signal Process. 69 (2021), 2129-2143. · Zbl 1543.94443 |
| [19] | R. Chartrand, V. Staneva, Restricted isometry properties and nonconvex compressive sensing, Inverse Probl. 24 (2008), 035020. · Zbl 1143.94004 |
| [20] | M.L. Moravec, J.K. Romberg, R.G. Baraniuk, Compressive phase retrieval, Proc. SPIE 6701, Wavelets XII, 670120, 2007. https://doi.org/10.1117/12.736360. · doi:10.1117/12.736360 |
| [21] | S. Burer, R. D. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program. 95 (2003), 329-357. · Zbl 1030.90077 |
| [22] | T. Tong, C. Ma, Y. Chi, Low-rank matrix recovery with scaled subgradient methods: fast and robust conver-gence without the condition number, IEEE Trans. Signal Process. 69 (2921), 2396-2409. · Zbl 1543.65063 |
| [23] | S. Foucart, M. Lai, Sparsest Solutions of Underdetermined Linear Systems via lq-minimization for 0 < q ≤ 1, Appl. Comput. Harmon. Anal. 26 (2009), 395-407. · Zbl 1171.90014 |
| [24] | V.V. Buldygin, Yu. V. Kozachenko, Metric Characterization of random variables and random processes, Translations of mathematical monographs v. 188, American Mathematical Society, Providence, R.I. 2000. · Zbl 0998.60503 |
| [25] | R. Vershynin. Introduction to the Non-asymptotic Analysis of Random Matrices, Cambridge University Press, Cambridge, 2010. · Zbl 1184.15023 |
| [26] | C. Impens, Stirling’s series made easy, Amer. Math. Monthly 110 (2003), 730-735. · Zbl 1087.11010 |
| [27] | S. Mendelson, A. Pajor, N. Tomczak-Jaegermann, Uniform uncertainty principle for Bernoulli and subgaus-sian ensembles, Constr. Approx. 28 (2008), 277-289. · Zbl 1230.46011 |
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.
