nips nips2013 nips2013-247 nips2013-247-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Praneeth Netrapalli, Prateek Jain, Sujay Sanghavi
Abstract: Phase retrieval problems involve solving linear equations, but with missing sign (or phase, for complex numbers). Over the last two decades, a popular generic empirical approach to the many variants of this problem has been one of alternating minimization; i.e. alternating between estimating the missing phase information, and the candidate solution. In this paper, we show that a simple alternating minimization algorithm geometrically converges to the solution of one such problem – finding a vector x from y, A, where y = |AT x| and |z| denotes a vector of element-wise magnitudes of z – under the assumption that A is Gaussian. Empirically, our algorithm performs similar to recently proposed convex techniques for this variant (which are based on “lifting” to a convex matrix problem) in sample complexity and robustness to noise. However, our algorithm is much more efficient and can scale to large problems. Analytically, we show geometric convergence to the solution, and sample complexity that is off by log factors from obvious lower bounds. We also establish close to optimal scaling for the case when the unknown vector is sparse. Our work represents the only known theoretical guarantee for alternating minimization for any variant of phase retrieval problems in the non-convex setting. 1
[1] J. Abrahams and A. Leslie. Methods used in the structure determination of bovine mitochondrial f1 atpase. Acta Crystallographica Section D: Biological Crystallography, 52(1):30–42, 1996.
[2] H. H. Bauschke, P. L. Combettes, and D. R. Luke. Hybrid projection–reflection method for phase retrieval. JOSA A, 20(6):1025–1034, 2003.
[3] L. Bregman. Finding the common point of convex sets by the method of successive projection.(russian). In Dokl. Akad. Nauk SSSR, volume 162, pages 487–490, 1965.
[4] E. J. Candes, Y. C. Eldar, T. Strohmer, and V. Voroninski. Phase retrieval via matrix completion. SIAM Journal on Imaging Sciences, 6(1):199–225, 2013.
[5] E. J. Candes and X. Li. Solving quadratic equations via phaselift when there are about as many equations as unknowns. arXiv preprint arXiv:1208.6247, 2012.
[6] 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, 2012.
[7] A. Chai, M. Moscoso, and G. Papanicolaou. Array imaging using intensity-only measurements. Inverse Problems, 27(1):015005, 2011.
[8] J. C. Dainty and J. R. Fienup. Phase retrieval and image reconstruction for astronomy. Image Recovery: Theory and Application, ed. byH. Stark, Academic Press, San Diego, pages 231–275, 1987.
[9] H. Duadi, O. Margalit, V. Mico, J. A. Rodrigo, T. Alieva, J. Garcia, and Z. Zalevsky. Digital holography and phase retrieval. Source: Holography, Research and Technologies. InTech, 2011.
[10] V. Elser. Phase retrieval by iterated projections. JOSA A, 20(1):40–55, 2003.
[11] J. R. Fienup et al. Phase retrieval algorithms: a comparison. Applied optics, 21(15):2758–2769, 1982.
[12] D. Gabor. A new microscopic principle. Nature, 161(4098):777–778, 1948.
[13] R. W. Gerchberg and W. O. Saxton. A practical algorithm for the determination of phase from image and diffraction plane pictures. Optik, 35:237, 1972.
[14] N. E. Hurt. Phase Retrieval and Zero Crossings: Mathematical Methods in Image Reconstruction, volume 52. Kluwer Academic Print on Demand, 2001.
[15] P. Jain, P. Netrapalli, and S. Sanghavi. Low-rank matrix completion using alternating minimization. arXiv preprint arXiv:1212.0467, 2012.
[16] R. H. Keshavan. Efficient algorithms for collaborative filtering. Phd Thesis, Stanford University, 2012.
[17] W. V. Li and A. Wei. Gaussian integrals involving absolute value functions. In Proceedings of the Conference in Luminy, 2009.
[18] X. Li and V. Voroninski. Sparse signal recovery from quadratic measurements via convex programming. arXiv preprint arXiv:1209.4785, 2012.
[19] S. Marchesini. Invited article: A unified evaluation of iterative projection algorithms for phase retrieval. Review of Scientific Instruments, 78(1):011301–011301, 2007.
[20] J. Miao, P. Charalambous, J. Kirz, and D. Sayre. Extending the methodology of x-ray crystallography to allow imaging of micrometre-sized non-crystalline specimens. Nature, 400(6742):342–344, 1999.
[21] D. Misell. A method for the solution of the phase problem in electron microscopy. Journal of Physics D: Applied Physics, 6(1):L6, 1973.
[22] H. Ohlsson, A. Y. Yang, R. Dong, and S. S. Sastry. Compressive phase retrieval from squared output measurements via semidefinite programming. arXiv preprint arXiv:1111.6323, 2011.
[23] S. Oymak, A. Jalali, M. Fazel, Y. C. Eldar, and B. Hassibi. Simultaneously structured models with application to sparse and low-rank matrices. arXiv preprint arXiv:1212.3753, 2012.
[24] J. L. Sanz. Mathematical considerations for the problem of fourier transform phase retrieval from magnitude. SIAM Journal on Applied Mathematics, 45(4):651–664, 1985.
[25] Y. Shechtman, Y. C. Eldar, A. Szameit, and M. Segev. Sparsity based sub-wavelength imaging with partially incoherent light via quadratic compressed sensing. arXiv preprint arXiv:1104.4406, 2011.
[26] J. A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389–434, 2012.
[27] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
[28] I. Waldspurger, A. d’Aspremont, and S. Mallat. Phase recovery, maxcut and complex semidefinite programming. arXiv preprint arXiv:1206.0102, 2012.
[29] D. C. Youla and H. Webb. Image restoration by the method of convex projections: Part 1theory. Medical Imaging, IEEE Transactions on, 1(2):81–94, 1982. 9