zbMATH — the first resource for mathematics

A geometric analysis of phase retrieval. (English) Zbl 1401.94049
Summary: Can we recover a complex signal from its Fourier magnitudes? More generally, given a set of \(m\) measurements, \(y_k = | \mathbf{a}_k^\ast \mathbf{x} | \) for \(k = 1, \dots, m\), is it possible to recover \(\mathbf{x} \in \mathbb C^n\) (i.e., length-\(n\) complex vector)? This generalized phase retrieval (GPR) problem is a fundamental task in various disciplines and has been the subject of much recent investigation. Natural nonconvex heuristics often work remarkably well for GPR in practice, but lack clear theoretic explanations. In this paper, we take a step toward bridging this gap. We prove that when the measurement vectors \(\mathbf{a}_k\)’s are generic (i.i.d. complex Gaussian) and numerous enough (\(m \geq C n \log^3 n\)), with high probability, a natural least-squares formulation for GPR has the following benign geometric structure: (1) There are no spurious local minimizers, and all global minimizers are equal to the target signal \(\mathbf{x}\), up to a global phase, and (2) the objective function has a negative directional curvature around each saddle point. This structure allows a number of iterative optimization methods to efficiently find a global minimizer, without special initialization. To corroborate the claim, we describe and analyze a second-order trust-region algorithm.

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
49K45 Optimality conditions for problems involving randomness
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
90C90 Applications of mathematical programming
Full Text: DOI
[1] Absil, P.-A.; Baker, C. G.; Gallivan, K. A., Trust-Region Methods on Riemannian Manifolds, Foundations of Computational Mathematics, 7, 303-330, (2006) · Zbl 1129.65045
[2] Pierre-Antoine. Absil, Robert Mahoney, and Rodolphe Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2009.
[3] Alekh Agarwal, Animashree Anandkumar, Prateek Jain, Praneeth Netrapalli, and Rashish Tandon. Learning sparsely used overcomplete dictionaries via alternating minimization. arXiv preprint arXiv:1310.7991, 2013. · Zbl 1358.90104
[4] Alekh Agarwal, Animashree Anandkumar, and Praneeth Netrapalli. Exact recovery of sparsely used overcomplete dictionaries. arXiv preprint arXiv:1309.1952, 2013. · Zbl 1359.62229
[5] Alexeev, Boris; Bandeira, Afonso S.; Fickus, Matthew; Mixon, Dustin G., Phase retrieval with polarization, SIAM Journal on Imaging Sciences, 7, 35-66, (2014) · Zbl 1304.49071
[6] Anima Anandkumar and Rong Ge. Efficient approaches for escaping higher order saddle points in non-convex optimization. arXiv preprint arXiv:1602.05908, 2016.
[7] Animashree Anandkumar, Rong Ge, and Majid Janzamin. Analyzing tensor power method dynamics: Applications to learning overcomplete latent variable models. arXiv preprint arXiv:1411.1488, 2014. · Zbl 1437.65037
[8] Animashree Anandkumar, Rong Ge, and Majid Janzamin. Guaranteed non-orthogonal tensor decomposition via alternating rank-1 updates. arXiv preprint arXiv:1402.5180, 2014. · Zbl 1319.62112
[9] Animashree Anandkumar, Prateek Jain, Yang Shi, and Uma Naresh Niranjan. Tensor vs matrix methods: Robust tensor decomposition under block sparse perturbations. arXiv preprint arXiv:1510.04747, 2015.
[10] Sanjeev Arora, Aditya Bhaskara, Rong Ge, and Tengyu Ma. More algorithms for provable dictionary learning. arXiv preprint arXiv:1401.0579, 2014.
[11] Sanjeev Arora, Rong Ge, Tengyu Ma, and Ankur Moitra. Simple, efficient, and neural algorithms for sparse coding. arXiv preprint arXiv:1503.00778, 2015.
[12] Sanjeev Arora, Rong Ge, and Ankur Moitra. New algorithms for learning incoherent and overcomplete dictionaries. arXiv preprint arXiv:1308.6273, 2013.
[13] Sohail Bahmani and Justin Romberg. Phase retrieval meets statistical learning theory: A flexible convex relaxation. arXiv preprint arXiv:1610.04210, 2016. · Zbl 1408.62032
[14] Balan, Radu; Bodmann, Bernhard G.; Casazza, Peter G.; Edidin, Dan, Painless reconstruction from magnitudes of frame coefficients, Journal of Fourier Analysis and Applications, 15, 488-501, (2009) · Zbl 1181.42032
[15] Radu V. Balan. On signal reconstruction from its spectrogram. In Information Sciences and Systems (CISS), 44th Annual Conference on, pp. 1-4. IEEE, 2010.
[16] Balana, Radu; Casazzab, Pete; Edidin, Dan, On signal reconstruction without phase, Applied and Computational Harmonic Analysis, 20, 345-356, (2006) · Zbl 1090.94006
[17] Afonso S. Bandeira, Nicolas Boumal, and Vladislav Voroninski. On the low-rank approach for semidefinite programs arising in synchronization and community detection. arXiv preprint arXiv:1602.04426, 2016.
[18] Tamir Bendory and Yonina C. Eldar. Non-convex phase retrieval from STFT measurements. arXiv preprint arXiv:1607.08218, 2016. · Zbl 1390.94093
[19] Dimitri P. Bertsekas. Nonlinear programming. 1999. · Zbl 1015.90077
[20] Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Global optimality of local search for low rank matrix recovery. arXiv preprint arXiv:1605.07221, 2016.
[21] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, Oxford, 2013. · Zbl 1279.60005
[22] Nicolas Boumal. Nonconvex phase synchronization. arXiv preprint arXiv:1601.06114, 2016. · Zbl 1356.90111
[23] Nicolas Boumal, P-A Absil, and Coralia Cartis. Global rates of convergence for nonconvex optimization on manifolds. arXiv preprint arXiv:1605.08101, 2016.
[24] Boumal, Nicolas; Mishra, Bamdev; Absil, P-A; Sepulchre, Rodolphe, Manopt, a Matlab toolbox for optimization on manifolds, Journal of Machine Learning Research, 15, 1455-1459, (2014) · Zbl 1319.90003
[25] Nicolas Boumal, Vladislav Voroninski, and Afonso S. Bandeira. The non-convex burer-monteiro approach works on smooth semidefinite programs. arXiv preprint arXiv:1606.04970, 2016.
[26] Bunk, Oliver; Diaz, Ana; Pfeiffer, Franz; David, Christian; Schmitt, Bernd; Satapathy, Dillip K.; Friso van der Veen, J., Diffractive imaging for periodic samples: retrieving one-dimensional concentration profiles across microfluidic channels, Acta Crystallographica Section A, 63, 306-314, (2007)
[27] T. Tony Cai, Xiaodong Li, and Zongming Ma. Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow. arXiv preprint arXiv:1506.03382, 2015. · Zbl 1349.62019
[28] Emmanuel J. Candès, Yonina C. Eldar, Thomas Strohmer, and Vladislav Voroninski. Phase retrieval via matrix completion. SIAM Journal on Imaging Sciences, 6(1), 2013. · Zbl 1280.49052
[29] Candès, Emmanuel J.; Li, Xiaodong, Solving quadratic equations via phaselift when there are about as many equations as unknowns, Foundations of Computational Mathematics, 14, 1017-1026, (2014) · Zbl 1312.90054
[30] Candès, Emmanuel J.; Li, Xiaodong; Soltanolkotabi, Mahdi, Phase retrieval from coded diffraction patterns, Applied and Computational Harmonic Analysis, 39, 277-299, (2015) · Zbl 1329.78056
[31] Candès, Emmanuel J.; Li, Xiaodong; Soltanolkotabi, Mahdi, Phase retrieval via wirtinger flow: Theory and algorithms, IEEE Transactions on Information Theory, 61, 1985-2007, (2015) · Zbl 1359.94069
[32] Candès, Emmanuel J.; Strohmer, Thomas; Voroninski, Vladislav, Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming, Communications on Pure and Applied Mathematics, 66, 1241-1274, (2013) · Zbl 1335.94013
[33] Cartis, Coralia; Gould, Nicholas IM; Toint, Ph L., Complexity bounds for second-order optimality in unconstrained optimization, Journal of Complexity, 28, 93-108, (2012) · Zbl 1245.65063
[34] Chai, Anwei; Moscoso, Miguel; Papanicolaou, George, Array imaging using intensity-only measurements, Inverse Problems, 27, 015005, (2011) · Zbl 1207.78022
[35] Yudong Chen and Martin J. Wainwright. Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprint arXiv:1509.03025, 2015.
[36] Yuxin Chen and Emmanuel J. Candès. Solving random quadratic systems of equations is nearly as easy as solving linear systems. arXiv preprint arXiv:1505.05114, 2015.
[37] Andrew R. Conn, Nicholas I.M. Gould, and Philippe L. Toint. Trust region methods, volume 1. SIAM, 2000. · Zbl 0958.65071
[38] Corbett, John V., The pauli problem, state reconstruction and quantum-real numbers, Reports on Mathematical Physics, 57, 53-68, (2006) · Zbl 1110.81007
[39] Chris Dainty and James R. Fienup. Phase retrieval and image reconstruction for astronomy. Image Recovery: Theory and Application, pages 231-275, 1987.
[40] Armin Eftekhari and Michael B. Wakin. Greed is super: A fast algorithm for super-resolution. arXiv preprint arXiv:1511.03385, 2015.
[41] Fienup, James R., Phase retrieval algorithms: a comparison, Applied Optics, 21, 2758-2769, (1982)
[42] Fortin, Charles; Wolkowicz, Henry, The trust region subproblem and semidefinite programming, Optimization methods and software, 19, 41-67, (2004) · Zbl 1070.65041
[43] Bing Gao and Zhiqiang Xu. Gauss-newton method for phase retrieval. arXiv preprint arXiv:1606.08135, 2016.
[44] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points—online stochastic gradient for tensor decomposition. In Proceedings of The 28th Conference on Learning Theory, pages 797-842, 2015.
[45] Rong Ge, Jason D. Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. arXiv preprint arXiv:1605.07272, 2016.
[46] Gerchberg, RW; Owen, W., Saxton. A practical algorithm for the determination of the phase from image and diffraction plane pictures, Optik, 35, 237-246, (1972)
[47] Goldfarb, Donald, Curvilinear path steplength algorithms for minimization which use directions of negative curvature, Mathematical programming, 18, 31-40, (1980) · Zbl 0428.90068
[48] Tom Goldstein and Christoph Studer. Phasemax: Convex phase retrieval via basis pursuit. arXiv preprint arXiv:1610.07531, 2016. · Zbl 1390.94194
[49] David Gross, Felix Krahmer, and Richard Kueng. A partial derandomization of phaselift using spherical designs. arXiv preprint arXiv:1310.2267, 2013. · Zbl 1332.90197
[50] Paul Hand and Vladislav Voroninski. Compressed sensing from phaseless gaussian measurements via linear programming in the natural parameter space. arXiv preprint arXiv:1611.05985, 2016.
[51] Paul Hand and Vladislav Voroninski. An elementary proof of convex phase retrieval in the natural parameter space via the linear program phasemax. arXiv preprint arXiv:1611.03935, 2016.
[52] Moritz Hardt. Understanding alternating minimization for matrix completion. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 651-660. IEEE, 2014.
[53] Moritz Hardt and Mary Wootters. Fast matrix completion without the condition number. In Proceedings of The 27th Conference on Learning Theory, pages 638-678, 2014.
[54] Heinosaari, Teiko; Mazzarella, Luca; Wolf, Michael M., Quantum tomography under prior information, Communications in Mathematical Physics, 318, 355-374, (2013) · Zbl 1263.81102
[55] Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer. Speeding up sum-of-squares for tensor decomposition and planted sparse vectors. arXiv preprint arXiv:1512.02337, 2015. · Zbl 1377.68199
[56] Kishore Jaganathan, Yonina C. Eldar, and Babak Hassibi. Phase retrieval: An overview of recent developments. arXiv preprint arXiv:1510.07713, 2015.
[57] Kishore Jaganathan, Samet Oymak, and Babak Hassibi. Sparse phase retrieval: Convex algorithms and limitations. In Proceedings of IEEE International Symposium on Information Theory, pages 1022-1026. IEEE, 2013.
[58] Prateek Jain, Chi Jin, Sham M. Kakade, and Praneeth Netrapalli. Computing matrix squareroot via non convex local search. arXiv preprint arXiv:1507.05854, 2015.
[59] Prateek Jain and Praneeth Netrapalli. Fast exact matrix completion with finite samples. arXiv preprint arXiv:1411.1087, 2014. · Zbl 1293.65073
[60] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the forty-fifth annual ACM symposium on Theory of Computing, pages 665-674. ACM, 2013. · Zbl 1293.65073
[61] Prateek Jain and Sewoong Oh. Provable tensor factorization with missing data. In Advances in Neural Information Processing Systems, pages 1431-1439, 2014.
[62] Kenji Kawaguchi. Deep learning without poor local minima. arXiv preprint arXiv:1605.07110, 2016.
[63] Keshavan, Raghunandan H.; Montanari, Andrea; Sewoong, Oh, Matrix completion from a few entries, IEEE Transactions on Information Theory, 56, 2980-2998, (2010) · Zbl 1366.62111
[64] Ritesh Kolte and Ayfer Özgür. Phase retrieval via incremental truncated wirtinger flow. arXiv preprint arXiv:1606.03196, 2016.
[65] Ken Kreutz-Delgado. The complex gradient operator and the \(\mathbb{C}\mathbb{R}\)-calculus. arXiv preprint arXiv:0906.4835, 2009.
[66] Jason D Lee, Max Simchowitz, Michael I Jordan, and Benjamin Recht. Gradient descent converges to minimizers. arXiv preprint arXiv:1602.04915, 2016.
[67] Kiryung Lee and Marius Junge. RIP-like properties in subsampled blind deconvolution. arXiv preprint arXiv:1511.06146, 2015.
[68] Kiryung Lee, Yanjun Li, Marius Junge, and Yoram Bresler. Blind recovery of sparse signals from subsampled convolution. arXiv preprint arXiv:1511.06149, 2015. · Zbl 1364.94261
[69] Kiryung Lee, Yihong Wu, and Yoram Bresler. Near optimal compressed sensing of sparse rank-one matrices via sparse power factorization. arXiv preprint arXiv:1312.0525, 2013. · Zbl 1390.94261
[70] Li, Xiaodong; Voroninski, Vladislav, Sparse signal recovery from quadratic measurements via convex programming, SIAM Journal on Mathematical Analysis, 45, 3019-3033, (2013) · Zbl 1320.94023
[71] Miao, Jianwei; Ishikawa, Tetsuya; Johnson, Bart; Anderson, Erik H.; Lai, Barry; Hodgson, Keith O., High resolution 3D X-Ray diffraction microscopy, Phys. Rev. Lett., 89, 088303, (2002)
[72] Millane, RP, Phase retrieval in crystallography and optics, Journal of the Optical Society of America A, 7, 394-411, (1990)
[73] Moré, Jorge J.; Sorensen, Danny C., Computing a trust region step, SIAM Journal on Scientific and Statistical Computing, 4, 553-572, (1983) · Zbl 0551.65042
[74] Cun, Mu; Huang, Bo; Wright, John; Goldfarb, Donald, Square deal: Lower bounds and improved convex relaxations for tensor recovery, Journal of Machine Learning Research, 1, 1-48, (2014)
[75] Nesterov, Yurii; Polyak, Boris T., Cubic regularization of newton method and its global performance, Mathematical Programming, 108, 177-205, (2006) · Zbl 1142.90500
[76] Praneeth Netrapalli, Prateek Jain, and Sujay Sanghavi. Phase retrieval using alternating minimization. In Advances in Neural Information Processing Systems, pages 2796-2804, 2013. · Zbl 1293.65073
[77] Praneeth Netrapalli, Uma Naresh. Niranjan, Sujay Sanghavi, Animashree Anandkumar, and Prateek Jain. Non-convex robust PCA. In Advances in Neural Information Processing Systems, pages 1107-1115, 2014.
[78] Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, Berlin, UK,2006. · Zbl 1104.65059
[79] Henrik Ohlsson, Allen Y. Yang, Roy Dong, and S. Shankar Sastry. CPRL - An extension of compressive sensing to the phase retrieval problem. In Advances in Neural Information Processing Systems. 2012.
[80] Henrik Ohlsson, Allen Y. Yang, Roy Dong, and S. Shankar Sastry. Compressive phase retrieval from squared output measurements via semidefinite programming. arXiv preprint arXiv:1111.6323, 2013.
[81] Henrik Ohlsson, Allen Y. Yang, Michel Verhaegen, and S. Shankar Sastry. Quadratic basis pursuit. arXiv preprint arXiv:1301.7002, 2013.
[82] Samet Oymak, Amin Jalali, Maryam Fazel, Yonina C. Eldar, and Babak Hassibi. Simultaneously structured models with application to sparse and low-rank matrices. arXiv preprint arXiv:1212.3753, 2012. · Zbl 1359.94150
[83] Ioannis Panageas and Georgios Piliouras. Gradient descent only converges to minimizers: Non-isolated critical points and invariant regions. CoRR, vol. abs/1605.00405, 2016. · Zbl 1402.90210
[84] Dohyung Park, Anastasios Kyrillidis, Constantine Caramanis, and Sujay Sanghavi. Non-square matrix sensing without spurious local minima via the burer-monteiro approach. arXiv preprint arXiv:1609.03240, 2016.
[85] Qing Qu, Ju Sun, and John Wright. Finding a sparse vector in a subspace: Linear sparsity using alternating directions. In Advances in Neural Information Processing Systems, pages 3401-3409, 2014. · Zbl 1359.94156
[86] H. Reichenbach. In Philosophic foundations of quantum mechanics. University of California Press, 1965.
[87] Rendl, Franz; Wolkowicz, Henry, A semidefinite framework for trust region subproblems with applications to large scale minimization, Mathematical Programming, 77, 273-299, (1997) · Zbl 0888.90137
[88] Harrison, W., Robert. Phase problem in crystallography, Journal of the Optical Society of America A, 10, 1046-1055, (1993)
[89] Christopher De Sa, Christopher Re, and Kunle Olukotun. Global convergence of stochastic gradient descent for some non-convex matrix problems. In The 32nd International Conference on Machine Learning, volume 37, pages 2332-2341, 2015.
[90] Hanie Sedghi and Animashree Anandkumar. Provable tensor methods for learning mixtures of classifiers. arXiv preprint arXiv:1412.3046, 2014.
[91] Shechtman, Yoav; Beck, Amir; Eldar, Yonina C., GESPAR: Efficient phase retrieval of sparse signals, Signal Processing, IEEE Transactions on, 62, 928-938, (2014) · Zbl 1394.94522
[92] Shechtman, Yoav; Eldar, Yonina C.; Cohen, Oren; Chapman, Henry N.; Miao, Jianwei; Segev, Mordechai, Phase retrieval with application to optical imaging: A contemporary overview, Signal Processing Magazine, IEEE, 32, 87-109, (2015)
[93] Mahdi Soltanolkotabi. Algorithms and theory for clustering and nonconvex quadratic programming. PhD thesis, Stanford University, 2014.
[94] Daniel Soudry and Yair Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks. arXiv preprint arXiv:1605.08361, 2016.
[95] Gilbert W. Stewart and Ji-guang Sun. Matrix Perturbation Theory. Academic press, Cambridge, 1990. · Zbl 0706.65013
[96] Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere. arXiv preprint arXiv:1504.06785, 2015. · Zbl 1364.94165
[97] Ju Sun, Qing Qu, and John Wright. When are nonconvex problems not scary? arXiv preprint arXiv:1510.06096, 2015.
[98] Ruoyu Sun and Zhi-Quan Luo. Guaranteed matrix completion via non-convex factorization. arXiv preprint arXiv:1411.8003, 2014. · Zbl 1359.94179
[99] Stephen Tu, Ross Boczar, Mahdi Soltanolkotabi, and Benjamin Recht. Low-rank solutions of linear matrix equations via procrustes flow. arXiv preprint arXiv:1507.03566, 2015.
[100] Stephen A. Vavasis and Richard Zippel. Proving polynomial-time for sphere-constrained quadratic programming. Technical report, Cornell University, 1990.
[101] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Yonina C. Eldar and Gitta Kutyniok, editors, Compressed Sensing, pages 210-268. Cambridge University Press, 2012.
[102] Vladislav Voroninski and Zhiqiang Xu. A strong restricted isometry property, with an application to phaseless compressed sensing. arXiv preprint arXiv:1404.3811, 2014. · Zbl 1338.94024
[103] Irène Waldspurger. Phase retrieval with random gaussian sensing vectors by alternating projections. arXiv preprint arXiv:1609.03088, 2016.
[104] Waldspurger, Iréne; d’Aspremont, Alexandre; Mallat, Stéphane, Phase recovery, maxcut and complex semidefinite programming, Mathematical Programming, 149, 47-81, (2015) · Zbl 1329.94018
[105] Walther, Adriaan, The question of phase retrieval in optics, Journal of Modern Optics, 10, 41-49, (1963)
[106] Gang Wang, Georgios B Giannakis, and Yonina C Eldar. Solving systems of random quadratic equations via truncated amplitude flow. arXiv preprint, 2016. · Zbl 1390.90451
[107] Ke Wei, Jian-Feng Cai, Tony F. Chan, and Shingyu Leung. Guarantees of Riemannian optimization for low rank matrix recovery. arXiv preprint arXiv:1511.01562, 2015. · Zbl 1347.65109
[108] Chris D. White, Rachel Ward, and Sujay Sanghavi. The local convexity of solving quadratic equations. arXiv preprint arXiv:1506.07868, 2015. · Zbl 1383.65064
[109] Ye, Yinyu, On affine scaling algorithms for nonconvex quadratic programming, Mathematical Programming, 56, 285-300, (1992) · Zbl 0767.90065
[110] Xinyang Yi, Constantine Caramanis, and Sujay Sanghavi. Alternating minimization for mixed linear regression. arXiv preprint arXiv:1310.3745, 2013.
[111] Huishuai Zhang, Yuejie Chi, and Yingbin Liang. Provable non-convex phase retrieval with outliers: Median truncated wirtinger flow. arXiv preprint arXiv:1603.03805, 2016. · Zbl 1440.94020
[112] Huishuai Zhang and Yingbin Liang. Reshaped wirtinger flow for solving quadratic systems of equations. arXiv preprint arXiv:1605.07719, 2016. · Zbl 1440.94020
[113] Qinqing Zheng and John Lafferty. A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements. arXiv preprint arXiv:1506.06081, 2015.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.