SOLVING SYSTEMS OF QUADRATIC EQUATIONS VIA EXPONENTIAL-TYPE GRADIENT DESCENT ALGORITHM

doi:10.4208/jcm.1902-m2018-0109

Journal of Computational Mathematics ›› 2020, Vol. 38 ›› Issue (4): 638-660.DOI: 10.4208/jcm.1902-m2018-0109

Previous Articles Next Articles

SOLVING SYSTEMS OF QUADRATIC EQUATIONS VIA EXPONENTIAL-TYPE GRADIENT DESCENT ALGORITHM

Meng Huang^1,2, Zhiqiang Xu^1,2

1. LSEC, Inst. Comp. Math., Academy of Mathematics and System Science, Chinese Academy of Sciences, Beijing 100190, China;
2. School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China

Received:2018-06-01 Revised:2019-01-21 Online:2020-07-15 Published:2020-07-15

PDF ( 2 ) Cited

Meng Huang, Zhiqiang Xu. SOLVING SYSTEMS OF QUADRATIC EQUATIONS VIA EXPONENTIAL-TYPE GRADIENT DESCENT ALGORITHM[J]. Journal of Computational Mathematics, 2020, 38(4): 638-660.

We consider the rank minimization problem from quadratic measurements, i.e., recovering a rank r matrix X ∈ R^n×r from m scalar measurements y^#em/em#=a_#em/em#^?XX^?a^#em/em#, a^#em/em# ∈ Rⁿ, #em/em#=1, …, m. Such problem arises in a variety of applications such as quadratic regression and quantum state tomography. We present a novel algorithm, which is termed exponential-type gradient descent algorithm, to minimize a non-convex objective function f(U)=1/4m Σ_#em/em#=1^m (y^#em/em#-a^#em/em#^?UU^?a^#em/em#)². This algorithm starts with a careful initialization, and then refines this initial guess by iteratively applying exponential-type gradient descent. Particularly, we can obtain a good initial guess of X as long as the number of Gaussian random measurements is O(nr), and our iteration algorithm can converge linearly to the true X (up to an orthogonal matrix) with m=O (nr log(cr)) Gaussian random measurements.

Key words: Low-rank matrix recovery, Non-convex optimization, Phase retrieval

CLC Number:

90C26
94A15

[1] R. Balan, Reconstruction of signals from magnitudes of redundant representations:The complex case, Foundations of Computational Mathematics, 16(2016), 677-721.

[2] E.J. Candes, Y. C. Eldar, T. Strohmer and V. Voroninski, Phase retrieval via matrix completion, SIAM review, 57(2015), 225-251.

[3] E.J. Candes, X. Li and M. Soltanolkotabi, Phase retrieval via wirtinger flow:Theory and algorithms, IEEE Transactions on Information Theory, 61(2015), 1985-2007.

[4] E.J. Candes and Y. Plan, Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements, IEEE Transactions on Information Theory, 57(2011), 2342-2359.

[5] E.J. Candes, T. Strohmer and V. Voroninski, Phaselift:Exact and stable signal recovery from magnitude measurements via convex programming. Communications on Pure and Applied Mathematics, 66(2013), 1241-1274.

[6] Y. Chen and E.J. Candes, Solving random quadratic systems of equations is nearly as easy as solving linear systems, in Advances in Neural Information Processing Systems, 2015, 739-747.

[7] Y. Chen, Y. Chi and A.J. Goldsmith, Exact and stable covariance estimation from quadratic sampling via convex programming, IEEE Transactions on Information Theory, 61(2015), 4034- 4059.

[8] A. Conca, D. Edidin, M. Hering and C. Vinzant, An algebraic characterization of injectivity in phase retrieval, Applied and Computational Harmonic Analysis, 38(2015), 346-356.

[9] L. Demanet and P. Hand, Stable optimizationless recovery from phaseless linear measurements, Journal of Fourier Analysis and Applications, 20(2014), 199-221.

[10] Y.C. Eldar and S. Mendelson, Phase retrieval:Stability and recovery guarantees, Applied and Computational Harmonic Analysis, 36(2014), 473-494.

[11] C. Fienup and J. Dainty, Phase retrieval and image reconstruction for astronomy, Image Recovery:Theory and Application, 231(1987), 275.

[12] B. Gao and Z. Xu, Phaseless recovery using the gauss-newton method, IEEE Transactions on Signal Processing, 65(2017), 5885-5896.

[13] R.W. Gerchberg, A practical algorithm for the determination of phase from image and diffraction plane pictures, Optik, 35(1972), 237-246.

[14] R.W. Harrison, Phase problem in crystallography, JOSA A, 10(1993), 1046-1055.

[15] P. Jain, P. Netrapalli and S. Sanghavi, Low-rank matrix completion using alternating minimization, In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, ACM, (2013), 665-674.

[16] R. Kueng, H. Rauhut and U. Terstiege, Low rank matrix recovery from rank one measurements, Applied and Computational Harmonic Analysis, 42(2017), 88-116.

[17] Y. Li, Y. Sun and Y. Chi, Low-rank positive semidefinite matrix recovery from corrupted rank-one measurements, IEEE Transactions on Signal Processing, 65(2017), 397-408.

[18] R. Meka, P. Jain, C. Caramanis and I. S. Dhillon, Rank minimization via online learning, in Proceedings of the 25th International Conference on Machine learning, ACM, 2008, 656-663.

[19] R.P. Millane, Phase retrieval in crystallography and optics, JOSA A, 7(1990), 394-411.

[20] P. Netrapalli, P. Jain and S. Sanghavi, Phase retrieval using alternating minimization, in Advances in Neural Information Processing Systems, (2013), 2796-2804.

[21] H. Rauhut and U. Terstiege, Low-rank matrix recovery via rank one tight frame measurements, Journal of Fourier Analysis and Applications, (2016), 1-6.

[22] B. Recht, M. Fazel and P.A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM review, 52(2010), 471-501.

[23] S. Sanghavi, R. Ward and C.D. White, The local convexity of solving systems of quadratic equations, Results in Mathematics, 71(2017), 569-608.

[24] Y. Shechtman, Y. C. Eldar, O. Cohen, H.N. Chapman, J. Miao and M. Segev, Phase retrieval with application to optical imaging:a contemporary overview, IEEE signal processing magazine, 32(2015), 87-109.

[25] R. Vershynin, High-dimensional probability:An introduction with applications in data science, Cambridge University Press, Cambridge, 2018.

[26] Z. Xu, The minimal measurement number for low-rank matrix recovery, Applied and Computational Harmonic Analysis, 44(2018), 497-508.

[27] Q. Zheng and J. Lafferty, A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements, in Advances in Neural Information Processing Systems, (2015), 109-117.

[1]	Yangyang Xu. FAST ALGORITHMS FOR HIGHER-ORDER SINGULAR VALUE DECOMPOSITION FROM INCOMPLETE DATA [J]. Journal of Computational Mathematics, 2017, 35(4): 397-422.

Viewed

Full text

Abstract

SOLVING SYSTEMS OF QUADRATIC EQUATIONS VIA EXPONENTIAL-TYPE GRADIENT DESCENT ALGORITHM

扫码分享