article

Phase recovery, MaxCut and complex semidefinite programming

Authors:

Irène Waldspurger,

Alexandre D'aspremont,

Stéphane MallatAuthors Info & Claims

Mathematical Programming: Series A and B, Volume 149, Issue 1-2

Pages 47 - 81

https://doi.org/10.1007/s10107-013-0738-9

Published: 01 February 2015 Publication History

Abstract

Phase retrieval seeks to recover a signal $$x \in {\mathbb {C}}^p$$ x C p from the amplitude $$|A x|$$ | A x | of linear measurements $$Ax \in {\mathbb {C}}^n$$ A x C n . We cast the phase retrieval problem as a non-convex quadratic program over a complex phase vector and formulate a tractable relaxation (called PhaseCut) similar to the classical MaxCut semidefinite program. We solve this problem using a provably convergent block coordinate descent algorithm whose structure is similar to that of the original greedy algorithm in Gerchberg and Saxton (Optik 35:237---246, 1972 ), where each iteration is a matrix vector product. Numerical results show the performance of this approach over three different phase retrieval problems, in comparison with greedy phase retrieval algorithms and matrix completion formulations.

References

[1]

Akutowicz, E.J.: On the determination of the phase of a Fourier integral, I. Trans. Am. Math. Soc. 83, 179---192 (1956)

[2]

Becker, S., Candes, E.J., Grant, M.: Templates for convex cone problems with applications to sparse signal recovery. Math. Prog. Comp. 3, 165---218 (2011)

[3]

Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: analysis, algorithms, and engineering applications. MPS-SIAM series on optimization. Society for Industrial and Applied Mathematics: Mathematical Programming Society, Philadelphia, PA (2001)

Digital Library

[4]

Ben-Tal, A., Nemirovski, A., Roos, C.: Extended matrix cube theorems with applications to $$\mu $$μ-theory in control. Math. Oper. Res. 28(3), 497---523 (2003)

Digital Library

[5]

Ben-Tal, A., El Ghaoui, L., Nemirovski, A.S.: Robust Optimization. Princeton University Press, Princeton, NJ (2009)

[6]

Bertsekas, D.: Nonlinear Programming. Athena Scientific, Belmont, MA (1998)

[7]

Bhatia, R.: Matrix Analysis, vol. 169. Springer, NewYork (1997)

[8]

Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)

Digital Library

[9]

Bunk, O., Diaz, A., Pfeiffer, F., David, C., Schmitt, B., Satapathy, D.K., Veen, J.F.: Diffractive imaging for periodic samples: retrieving one-dimensional concentration profiles across microfluidic channels. Acta Crystallogr. A 63(4), 306---314 (2007)

[10]

Candes, E.J., Strohmer, T., Voroninski, V.: Phaselift: exact and stable signal recovery from magnitude measurements via convex programming. Commun. Pure Appl. Math. 66(8), 1241---1274 (2013)

[11]

Candes, E.J., Li, X.: Solving quadratic equations via phaselift when there are about as many equations as unknowns. ArXiv preprint arXiv:1208.6247 (2012)

[12]

Candes, E.J., Recht, B.: Exact matrix completion via convex optimization. Preprint (2008)

[13]

Candes, E.J., Eldar, Y., Strohmer, T., Voroninski, V.L: Phase retrieval via matrix completion. ArXiv preprint arXiv:1109.0573 (2011)

[14]

Chai, A., Moscoso, M., Papanicolaou, G.: Array imaging using intensity-only measurements. Inverse Probl. 27, 015005 (2011)

[15]

Chandrasekaran, V., Recht, B., Parrilo, P., Willsky, A.S.: The convex geometry of linear inverse problems. Found. Comput. Math 12(6), 805---849 (2012)

Digital Library

[16]

Chi, T., Ru, P., Shamma, S.: Multiresolution spectrotemporal analysis of complex sounds. J. Acoust. Soc. Am 118, 887---906 (2005)

[17]

d'Aspremont, A., Banerjee, O., El Ghaoui, L.: First-order methods for sparse covariance selection. SIAM J. Matrix Anal. Appl. 30(1), 56---66 (2006)

Digital Library

[18]

Delorme, C., Poljak, S.: Laplacian eigenvalues and the maximum cut problem. Math. Program. 62(1), 557---574 (1993)

Digital Library

[19]

Demanet, L., Hand, P.: Stable optimizationless recovery from phaseless linear measurements. ArXiv preprint arXiv:1208.1803 (2012)

[20]

El Karoui, N., d'Aspremont, A.: Approximating eigenvectors by subsampling. ArXiv:0908.0137 (2009)

[21]

Fazel, M., Hindi, H., Boyd, S.P.: Log-det heuristic for matrix rank minimization with applications to hankel and euclidean distance matrices. In: American Control Conference, 2003. Proceedings of the 2003, vol. 3, pp. 2156---2162. Ieee (2003)

[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 phase from image and diffraction plane pictures. Optik 35, 237---246 (1972)

[24]

Goemans, M.X., Williamson, D.P.: Approximation algorithms for max-3-cut and other problems via complex semidefinite programming. J. Comput. Syst. Sci. 68(2), 442---470 (2004)

Digital Library

[25]

Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115---1145 (1995)

Digital Library

[26]

Griffin, D., Lim, J.: Signal estimation from modified short-time fourier transform. IEEE Trans. Acoust. Speech Signal Process. 32(2), 236---243 (1984)

[27]

Harrison, R.W.: Phase problem in crystallography. JOSA A 10(5), 1046---1055 (1993)

[28]

Helmberg, C., Rendl, F., Vanderbei, R.J., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6, 342---361 (1996)

Digital Library

[29]

Kato, T.: Perturbation Theory for Linear Operators. Springer, Berlin (1995)

[30]

Kisialiou, M., Luo, Z.Q.: Probabilistic analysis of semidefinite relaxation for binary quadratic minimization. SIAM J Optim 20, 1906 (2010)

Digital Library

[31]

Li, X., Voroninski, V.: Sparse signal recovery from quadratic measurements via convex programming. ArXiv preprint arXiv:1209.4785 (2012)

[32]

Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0---1 optimization. SIAM J. Optim. 1(2), 166---190 (1991)

[33]

Luo, Z.Q., Luo, X., Kisialiou, M.: An efficient quasi-maximum likelihood decoder for psk signals. In: Acoustics, Speech, and Signal Processing, 2003. Proceedings. (ICASSP'03). 2003 IEEE International Conference on, vol. 6, pp. VI-561. IEEE (2003)

[34]

Miao, J., Ishikawa, T., Shen, Q., Earnest, T.: Extending X-ray crystallography to allow the imaging of noncrystalline materials, cells, and single protein complexes. Annu. Rev. Phys. Chem. 59, 387---410 (2008)

[35]

Moravec, M.L., Romberg, J.K., Baraniuk, R.G.: Compressive phase retrieval. In: Proc. of SPIE vol. 6701, pp. 670120---1 (2007)

[36]

Nesterov, Y.: A method of solving a convex programming problem with convergence rate $${O}(1/k^2)$$O(1/k2). Sov. Math. Dokl. 27(2), 372---376 (1983)

[37]

Nesterov, Y.: Semidefinite relaxation and nonconvex quadratic optimization. Optim Methods Softw. 9(1), 141---160 (1998)

[38]

Nesterov, Y.: Smoothing technique and its applications in semidefinite optimization. Math. Program. 110(2), 245---259 (2007)

Digital Library

[39]

Osherovich, E., Shechtman, Y., Szameit, A., Sidorenko, P., Bullkich, E., Gazit, S., Shoham, S., Kley, E.B., Zibulevsky, M., Yavneh, I., et al.: Sparsity-based single-shot subwavelength coherent diffractive imaging. Nat. Mater. 11(5), 455---459 (2012)

[40]

Sanz, J.L.C.: Mathematical considerations for the problem of fourier transform phase retrieval from magnitude. SIAM J. Appl. Math. 45, 651---664 (1985)

[41]

Shor, N.Z.: Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25, 1---11 (1987)

[42]

Singer, A.: Angular synchronization by eigenvectors and semidefinite programming. Appl. comput. Harmon. Anal. 30(1), 20---36 (2011)

[43]

So, A.M.C.: Non-asymptotic performance analysis of the semidefinite relaxation detector in digital communications. Working paper (2010)

[44]

So, A.M.C., Zhang, J., Ye, Y.: On approximating complex quadratic optimization problems via semidefinite programming relaxations. Math. Program. 110(1), 93---110 (2007)

Digital Library

[45]

So, A.M.-C., Ye, Y.: Probabilistic analysis of semidefinite relaxation detectors for multiple-input, multiple-output. Convex Optim. Signal Process. Commun. 166 (2010)

[46]

Stewart, G.W.: Matrix Algorithms, Vol. II: Eigensystems. Society for Industrial Mathematics, Philadelphia (2001)

Digital Library

[47]

Stewart, G.W., Sun, J.: Matrix perturbation theory. Academic Press, Boston (1990)

[48]

Todd, M., Yildirim, E.A.: Sensitivity analysis in linear programming and semidefinite programming using interior-points methods. Math. Program. 90(2), 229---261 (2001)

[49]

Toh, K.C., Todd, M.J., Tutuncu, R.H.: SDPT3--a MATLAB software package for semidefinite programming. Optim. Methods Softw. 11, 545---581 (1999)

[50]

Voroninski, V.: A comparison between the phaselift and phasecut algorithms. Working paper (2012)

[51]

Waldspurger, I., Mallat, S.: Time-frequency phase recovery. Working paper (2012)

[52]

Wen, Z., Goldfarb, D., Scheinberg, K.: Block coordinate descent methods for semidefinite programming. In: Anjos, M., Lasserre, J.B. (eds.) Handbook on Semidefinite, Conic and Polynomial Optimization, pp. 533---564. Springer (2012)

[53]

Yildirim, E.A.: An interior-point perspective on sensitivity analysis in semidefinite programming. Math. Oper. Res. 28(4), 649---676 (2003)

Digital Library

[54]

Zhang, S., Huang, Y.: Complex quadratic optimization and semidefinite programming. SIAM J. Optim. 16(3), 871---890 (2006)

Digital Library

Cited By

Li JWang CSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)DiffFPRProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693222(28673-28687)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693222
Luo YHuang WLi XZhang A(2024)Recursive Importance Sketching for Rank Constrained Least SquaresOperations Research10.1287/opre.2023.244572:1(237-256)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/opre.2023.2445
Liu JLiu YMa WShao MSo A(2024)Extreme Point Pursuit—Part I: A Framework for Constant Modulus OptimizationIEEE Transactions on Signal Processing10.1109/TSP.2024.345800872(4541-4556)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3458008
Show More Cited By

Phase recovery, MaxCut and complex semidefinite programming
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

On linear and semidefinite programming relaxations for hypergraph matching

The hypergraph matching problem is to find a largest collection of disjoint hyperedges in a hypergraph. This is a well-studied problem in combinatorial optimization and graph theory with various applications. The best known approximation algorithms for ...
Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons

At the intersection of nonlinear and combinatorial optimization, quadratic programming has attracted significant interest over the past several decades. A variety of relaxations for quadratically constrained quadratic programming (QCQP) can be ...
Enhancing Semidefinite Relaxation for Quadratically Constrained Quadratic Programming via Penalty Methods

Quadratically constrained quadratic programming arises from a broad range of applications and is known to be among the hardest optimization problems. In recent years, semidefinite relaxation has become a popular approach for quadratically constrained ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Programming: Series A and B

Mathematical Programming: Series A and B Volume 149, Issue 1-2

February 2015

454 pages

ISSN:0025-5610

Issue’s Table of Contents

Copyright © Copyright © 2015 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 February 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

82
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li JWang CSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)DiffFPRProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693222(28673-28687)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693222
Luo YHuang WLi XZhang A(2024)Recursive Importance Sketching for Rank Constrained Least SquaresOperations Research10.1287/opre.2023.244572:1(237-256)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/opre.2023.2445
Liu JLiu YMa WShao MSo A(2024)Extreme Point Pursuit—Part I: A Framework for Constant Modulus OptimizationIEEE Transactions on Signal Processing10.1109/TSP.2024.345800872(4541-4556)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3458008
Liu KWang ZWu L(2024)The Local Landscape of Phase Retrieval Under Limited SamplesIEEE Transactions on Information Theory10.1109/TIT.2024.348126970:12(9012-9035)Online publication date: 15-Oct-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3481269
Xu MDong DWang J(2024)Subspace Phase RetrievalIEEE Transactions on Information Theory10.1109/TIT.2024.338682170:6(4538-4570)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3386821
Kim SBahmani SLee K(2024)Max-Linear Regression by Convex ProgrammingIEEE Transactions on Information Theory10.1109/TIT.2024.335051870:3(1897-1912)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3350518
Lu CMa JDeng ZXing W(2024)A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problemJournal of Global Optimization10.1007/s10898-023-01305-988:1(115-137)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s10898-023-01305-9
Talkington SGrijalva S(2023)Phase Retrieval via Model-Free Power Flow Jacobian RecoveryProceedings of the 14th ACM International Conference on Future Energy Systems10.1145/3575813.3597357(510-523)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3575813.3597357
Vu TRaich RFu X(2023)On Local Linear Convergence of Projected Gradient Descent for Unit-Modulus Least SquaresIEEE Transactions on Signal Processing10.1109/TSP.2023.332418171(3883-3897)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TSP.2023.3324181
Yang YWu RChen DFei CLi DYang Y(2023)An improved Fourier Ptychography algorithm for ultrasonic array imagingComputers in Biology and Medicine10.1016/j.compbiomed.2023.107157163:COnline publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1016/j.compbiomed.2023.107157
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents