Phase retrieval from local measurements: improved robustness via eigenvector-based angular synchronization. (English) Zbl 07140142

Summary: We improve a phase retrieval approach that uses correlation-based measurements with compactly supported measurement masks [30]. Our approach admits deterministic measurement constructions together with a robust, fast recovery algorithm that consists of solving a system of linear equations in a lifted space, followed by finding an eigenvector (e.g., via an inverse power iteration). Theoretical reconstruction error guarantees from [30] are improved as a result for the new and more robust reconstruction approach proposed herein. Numerical experiments demonstrate robustness and computational efficiency that compete with other approaches on large problems. Along the way, we show that this approach also trivially extends to phase retrieval problems based on windowed Fourier measurements.


65-XX Numerical analysis
94-XX Information and communication theory, circuits
Full Text: DOI arXiv


[1] Alexeev, B.; Bandeira, A. S.; Fickus, M.; Mixon, D. G., Phase retrieval with polarization, SIAM J. Imaging Sci., 7, 1, 35-66 (2014) · Zbl 1304.49071
[2] Balan, R.; Bodmann, B.; Casazza, P.; Edidin, D., Fast algorithms for signal reconstruction without phase, (Optical Engineering+Applications (2007), International Society for Optics and Photonics), 67011L
[3] Balan, R.; Bodmann, B. G.; Casazza, P. G.; Edidin, D., Painless reconstruction from magnitudes of frame coefficients, J. Fourier Anal. Appl., 15, 4, 488-501 (2009) · Zbl 1181.42032
[4] Balan, R.; Casazza, P.; Edidin, D., On signal reconstruction without phase, Appl. Comput. Harmon. Anal., 20, 3, 345-356 (2006) · Zbl 1090.94006
[5] Bandeira, A. S.; Mixon, D. G., Near-optimal phase retrieval of sparse vectors, (Wavelets and Sparsity XV, vol. 8858 (2013), International Society for Optics and Photonics), Article 88581O pp.
[6] Bandeira, A. S.; Singer, A.; Spielman, D. A., A Cheeger inequality for the graph connection Laplacian, SIAM J. Matrix Anal. Appl., 34, 4, 1611-1630 (2013) · Zbl 1287.05081
[7] Bauschke, H.; Combettes, P.; Luke, D., Hybrid projection-reflection method for phase retrieval, J. Opt. Soc. Amer. A, 20, 6, 1025-1034 (2003)
[8] Bauschke, H. H.; Combettes, P. L.; Luke, D. R., Phase retrieval, error reduction algorithm, and Fienup variants: a view from convex optimization, J. Opt. Soc. Amer. A, 19, 7, 1334-1345 (2002)
[9] Bendory, T.; Eldar, Y. C.; Boumal, N., Non-convex phase retrieval from STFT measurements, IEEE Trans. Inform. Theory, 64, 1, 467-484 (2018) · Zbl 1390.94093
[10] Bodmann, B. G.; Hammen, N., Stable phase retrieval with low-redundancy frames, Adv. Comput. Math., 41, 2, 317-331 (2015) · Zbl 1316.42035
[11] Candes, E. J.; Li, X., 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
[12] Candes, E. J.; Li, X.; Soltanolkotabi, M., Phase retrieval from coded diffraction patterns, Appl. Comput. Harmon. Anal., 39, 2, 277-299 (Sept. 2015)
[13] Candes, E. J.; Li, X.; Soltanolkotabi, M., Phase retrieval via Wirtinger flow: theory and algorithms, IEEE Trans. Inform. Theory, 61, 4, 1985-2007 (2015) · Zbl 1359.94069
[14] Candes, E. J.; Strohmer, T.; Voroninski, V., Phaselift: exact and stable signal recovery from magnitude measurements via convex programming, Comm. Pure Appl. Math., 66, 8, 1241-1274 (2013) · Zbl 1335.94013
[15] Chung, F. R., Spectral Graph Theory. Number 92 (1997), American Mathematical Society
[16] Davis, C.; Kahan, W. M., The rotation of eigenvectors by a perturbation. III, SIAM J. Numer. Anal., 7, 1, 1-46 (1970) · Zbl 0198.47201
[17] Dierolf, M.; Bunk, O.; Kynde, S.; Thibault, P.; Johnson, I.; Menzel, A.; Jefimovs, K.; David, C.; Marti, O.; Pfeiffer, F., Ptychography & lensless X-ray imaging, Europhys. News, 39, 1, 22-24 (2008)
[18] Eldar, Y.; Sidorenko, P.; Mixon, D.; Barel, S.; Cohen, O., Sparse phase retrieval from short-time Fourier measurements, IEEE Signal Process. Lett., 22, 5 (2015)
[19] Eldar, Y. C.; Mendelson, S., Phase retrieval: stability and recovery guarantees, Appl. Comput. Harmon. Anal., 36, 3, 473-494 (2014) · Zbl 06298184
[20] Elser, V., Phase retrieval by iterated projections, J. Opt. Soc. Amer. A, 20, 1, 40-55 (2003)
[21] Fienup, J. R., Reconstruction of an object from the modulus of its Fourier transform, Opt. Lett., 3, 1, 27-29 (1978)
[22] Fienup, J. R., Phase retrieval algorithms: a comparison, Appl. Opt., 21, 15, 2758-2769 (1982)
[23] Gerchberg, R.; Saxton, W., A practical algorithm for the determination of the phase from image and diffraction plane pictures, Optik, 35, 237-246 (1972)
[24] Goodman, J. W., Introduction to Fourier Optics (2005), Roberts and Company Publishers
[25] Grant, M.; Boyd, S., Graph implementations for nonsmooth convex programs, (Blondel, V.; Boyd, S.; Kimura, H., Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences (2008), Springer-Verlag), 95-110 · Zbl 1205.90223
[26] Grant, M.; Boyd, S., CVX: Matlab software for disciplined convex programming (Mar. 2014), version 2.1
[27] Gross, D.; Krahmer, F.; Kueng, R., Improved recovery guarantees for phase retrieval from coded diffraction patterns, Appl. Comput. Harmon. Anal., 42, 1, 37-64 (January 2017)
[28] Horn, R. A.; Johnson, C. R., Matrix Analysis (2012), Cambridge University Press
[29] Iwen, M.; Krahmer, F.; Viswanathan, A., Technical note: a minor correction of Theorem 1.3 from [1] (April 2015), Unpublished note available at
[30] Iwen, M.; Viswanathan, A.; Wang, Y., Fast phase retrieval from local correlation measurements, SIAM J. Imaging Sci., 9, 4, 1655-1688 (2016) · Zbl 1352.49035
[31] Iwen, M.; Wang, Y.; Viswanathan, A., BlockPR: Matlab software for phase retrieval using block circulant measurement constructions and angular synchronization, version 2.0 (Apr. 2016)
[32] Jaganathan, K.; Eldar, Y. C.; Hassibi, B., STFT phase retrieval: uniqueness guarantees and recovery algorithms, IEEE J. Sel. Top. Signal Process., 10, 4, 770-781 (2016)
[33] 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
[34] Marchesini, S.; Tu, Y.-C.; Wu, H.-t., Alternating projection, ptychographic imaging and phase synchronization, Appl. Comput. Harmon. Anal., 41, 3, 815-851 (2016) · Zbl 1388.94015
[35] Merhi, S.; Viswanathan, A.; Iwen, M., Recovery of compactly supported functions from spectrogram measurements via lifting, (2017 International Conference on Sampling Theory and Applications. 2017 International Conference on Sampling Theory and Applications, SampTA (2017), IEEE), 538-542
[36] Millane, R., Phase retrieval in crystallography and optics, J. Opt. Soc. Amer. A, 7, 3, 394-411 (1990)
[37] Netrapalli, P.; Jain, P.; Sanghavi, S., Phase retrieval using alternating minimization, (Advances in Neural Information Processing Systems (2013)), 2796-2804
[38] Pfander, G. E.; Salanevich, P., Robust phase retrieval algorithm for time-frequency structured measurements (2016), eprint
[39] Salanevich, P.; Pfander, G. E., Polarization based phase retrieval for time-frequency structured measurements, (2015 International Conference on Sampling Theory and Applications. 2015 International Conference on Sampling Theory and Applications, SampTA (2015), IEEE), 187-191
[40] Stewart, G.; Sun, J., Matrix Perturbation Theory (1990), Academic Press
[41] Takajo, H.; Takahashi, T.; Kawanami, H.; Ueda, R., Numerical investigation of the iterative phase-retrieval stagnation problem: territories of convergence objects and holes in their boundaries, J. Opt. Soc. Amer. A, 14, 12, 3175-3187 (1997)
[42] Takajo, H.; Takahashi, T.; Shizuma, T., Further study on the convergence property of the hybrid input–output algorithm used for phase retrieval, J. Opt. Soc. Amer. A, 16, 9, 2163-2168 (1999)
[43] Takajo, H.; Takahashi, T.; Ueda, R.; Taninaka, M., Study on the convergence property of the hybrid input–output algorithm used for phase retrieval, J. Opt. Soc. Amer. A, 15, 11, 2849-2861 (1998)
[44] Trefethen, L. N.; Bau, D., Numerical Linear Algebra, vol. 50 (1997), SIAM
[45] Viswanathan, A.; Iwen, M., Fast angular synchronization for phase retrieval via incomplete information, (Wavelets and Sparsity XVI, vol. 9597 (2015), International Society for Optics and Photonics), Article 959718 pp.
[46] Walther, A., The question of phase retrieval in optics, Opt. Acta, 10, 41-49 (1963)
[48] Yu, Y.; Wang, T.; Samworth, R., A useful variant of the Davis-Kahan theorem for statisticians, Biometrika, 102, 2, 315-323 (2015) · Zbl 1452.15010
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.