2018

Phase Retrieval via Polytope Optimization: Geometry, Phase Transitions, and New Algorithms

Dhifallah, Oussama, Thrampoulidis, Christos, Lu, Yue M.

Understand

We study algorithms for solving quadratic systems of equations based on optimization methods over polytopes.

Our work is inspired by a recently proposed convex formulation of the phase retrieval problem, which estimates the unknown signal by solving a simple linear program over a polytope constructed from the measurements.
We present a sharp characterization of the high-dimensional geometry of the aforementioned polytope under Gaussian measurements.
This characterization allows us to derive asymptotically exact performance guarantees for PhaseMax, which also reveal a phase transition phenomenon with respect to its sample complexity.

Built on

R. Rockafellar, Convex Analysis , ser. Princeton landmarks in mathematics and physics. Princeton University Press, 1970. [Online]. Available: https://books.google.com/books?id=1TiOka9bx3sC
1970
Earlier work this paper cites.
J. R. Fienup, “Phase retrieval algorithms: a comparison,” Applied Optics , vol. 21, no. 15, pp. 2758–2769, 1982
1982
Earlier work this paper cites.
Y. Gordon, “Some inequalities for Gaussian processes and applications,” Israel Journal of Mathematics , vol. 50, no. 4, pp. 265–289, Dec 1985
1985
Earlier work this paper cites.
Y. Gordon, “On Milman’s inequality and random subspaces which escape through a mesh in ℝ n \mathbb{R}^{n} ,” in Geometric Aspects of Functional Analysis . Berlin, Heidelberg: Springer Berlin Heidelberg, 1988, pp. 84–106
1988
Earlier work this paper cites.
W. K. Newey and D. McFadden, “Large sample estimation and hypothesis testing,” in Handbook of Econometrics , ser. Handbook of Econometrics, R. F. Engle and D. McFadden, Eds. Elsevier, 1994, vol. 4, ch. 36, pp. 2111–2245
1994
Earlier work this paper cites.
R. T. Rockafellar and R. J.-B. Wets, Variational Analysis . Springer, 1998
1998
Earlier work this paper cites.
R. Balan, B. G. Bodmann, P. G. Casazza, and D. Edidin, “Painless reconstruction from magnitudes of frame coefficients,” Journal of Fourier Analysis and Applications , vol. 15, no. 4, pp. 488–501, 2009
2009
Earlier work this paper cites.
G. R. Lanckriet and B. K. Sriperumbudur, “On the convergence of the concave-convex procedure,” in Advances in Neural Information Processing Systems 22 . Curran Associates, Inc., 2009, pp. 1759–1767
2009
Earlier work this paper cites.
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 , vol. 66, no. 8, pp. 1241–1274, 2013
2013
Earlier work this paper cites.
P. Netrapalli, P. Jain, and S. Sanghavi, “Phase retrieval using alternating minimization,” in Advances in Neural Information Processing Systems , 2013, pp. 2796–2804
2013
Earlier work this paper cites.
M. Stojnic, “A framework to characterize performance of LASSO algorithms,” CoRR , vol. abs/1303.7291, 2013. [Online]. Available: http://arxiv.org/abs/1303.7291
Original
2013
Earlier work this paper cites.
E. J. Candès, T. Strohmer, and V. Voroninski, “Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming,” Communications on Pure and Applied Mathematics , vol. 66, no. 8, pp. 1241–1274, 2013
2013
Earlier work this paper cites.

Similar

T. Goldstein, C. Studer, and R. Baraniuk, “A field guide to forward-backward splitting with a FASTA implementation,” arXiv eprint , vol. abs/1411.3406, 2014. [Online]. Available: http://arxiv.org/abs/1411.3406
Original
2014
Cited alongside, same era.
K. Jaganathan, Y. C. Eldar, and B. Hassibi, “Phase retrieval: An overview of recent developments,” arXiv preprint arXiv:1510.07713 , 2015
Original
2015
Cited alongside, same era.
I. Waldspurger, A. d’Aspremont, and S. Mallat, “Phase recovery, maxcut and complex semidefinite programming,” Mathematical Programming , vol. 149, no. 1-2, pp. 47–81, 2015
2015
Cited alongside, same era.
E. J. Candes, X. Li, and M. Soltanolkotabi, “Phase retrieval via Wirtinger flow: Theory and algorithms,” Information Theory, IEEE Transactions on , vol. 61, no. 4, pp. 1985–2007, 2015
2015
Cited alongside, same era.
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 , vol. 32, no. 3, pp. 87–109, May 2015
2015
Cited alongside, same era.
Y. Chen and E. J. Candes, “Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems,” arXiv:1505.05114 , 2015
Original
2015
Cited alongside, same era.
C. Thrampoulidis, S. Oymak, and B. Hassibi, “Regularized linear regression: A precise analysis of the estimation error,” in Proceedings of The 28th Conference on Learning Theory , vol. 40. Paris, France: PMLR, 03–06 Jul 2015, pp. 1683–1709
2015
Cited alongside, same era.
C. Thrampoulidis, E. Abbasi, and B. Hassibi, “Lasso with non-linear measurements is equivalent to one with linear measurements,” in Advances in Neural Information Processing Systems , 2015, pp. 3420–3428
2015
Cited alongside, same era.
G. Wang, G. B. Giannakis, and Y. C. Eldar, “Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow,” arXiv:1605.08285 , May 2016
Original
2016
Cited alongside, same era.
S. Bahmani and J. Romberg, “Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation,” CoRR , vol. abs/1610.04210, 2016. [Online]. Available: http://arxiv.org/abs/1610.04210
Original
2016
Cited alongside, same era.
T. Goldstein and C. Studer, “PhaseMax: Convex Phase Retrieval via Basis Pursuit,” CoRR , vol. abs/1610.07531, 2016. [Online]. Available: http://arxiv.org/abs/1610.07531
Original
2016
Cited alongside, same era.

Then

P. Hand and V. Voroninski, “An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax,” arXiv:1611.03935 [cs, math] , Nov. 2016, arXiv: 1611.03935. [Online]. Available: http://arxiv.org/abs/1611.03935
Original
2016
Later among the works it cites.
P. Hand and V. Voroninski, “An elementary proof of convex phase retrieval in the natural parameter space via the linear program phasemax,” arXiv:1611.03935 , 2016
Original
2016
Later among the works it cites.
C. Thrampoulidis, E. Abbasi, and B. Hassibi, “Precise error analysis of regularized m-estimators in high-dimensions,” CoRR , vol. abs/1601.06233, 2016. [Online]. Available: http://arxiv.org/abs/1601.06233
Original
2016
Later among the works it cites.
K. Lange, MM Optimization Algorithms . SIAM, 2016
2016
Later among the works it cites.
O. Dhifallah, C. Thrampoulidis, and Y. M. Lu, “Phase retrieval via linear programming: Fundamental limits and algorithmic improvements,” in 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , Oct 2017, pp. 1071–1077
2017
Later among the works it cites.
Y. M. Lu and G. Li, “Phase transitions of spectral initialization for high-dimensional nonconvex estimation,” arXiv:1702.06435 [cs.IT] , 2017. [Online]. Available: https://arxiv.org/abs/1702.06435
Original
2017
Later among the works it cites.
O. Dhifallah and Y. M. Lu, “Fundamental Limits of PhaseMax for Phase Retrieval: A Replica Analysis,” Proc. International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) , 2017. [Online]. Available: https://arxiv.org/abs/1708.03355
Original
2017
Later among the works it cites.
M. Mondelli and A. Montanari, “Fundamental limits of weak recovery with applications to phase retrieval,” CoRR , vol. abs/1708.05932, 2017. [Online]. Available: https://arxiv.org/abs/1708.05932
Original
2017
Later among the works it cites.
R. Chandra, Z. Zhong, J. Hontz, V. McCulloch, C. Studer, and T. Goldstein, “Phasepack: A phase retrieval library,” Asilomar Conference on Signals, Systems, and Computers , 2017
2017
Later among the works it cites.
S. Fariborz, A. Ehsan, and H. Babak, “A precise analysis of phasemax in phase retrieval,” CoRR , vol. abs/1801.06609, 2018. [Online]. Available: http://arxiv.org/abs/1801.06609
Original
2018
Closest in time.
C. Thrampoulidis, A. Panahi, and B. Hassibi, “Asymptotically exact error analysis for the generalized equation-lasso,” in Information Theory (ISIT), 2015 IEEE International Symposium on . IEEE, 2015, pp. 2021–2025
2025
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…