Phase recovery, MaxCut and complex semidefinite programming

By Irène Waldspurger, Alexandre d'Aspremont, Stéphane Mallat. Mathematical programming, 2012

670 citations recorded by the source corpus.

Phase retrieval seeks to recover a signal x∈Cp\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x \in {\mathbb {C}}^p$$\end{document} from the amplitude |Ax|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|A x|$$\end{document} of linear measurements Ax∈Cn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Ax \in {\mathbb {C}}^n$$\end{document}. 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.

Subfields: Atomic and Molecular Physics, and Optics, Computer Vision and Pattern Recognition, Radiation

View Paper: https://www.semanticscholar.org/paper/6b25b3ac092a6475ad083ff692786c912e0d6183

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Atomic and Molecular Physics, and Optics

In Computer Vision and Pattern Recognition

In Radiation

Citations in the corpus

Deep Scattering Spectrum (2013, background): “Recent convex relaxation approaches [35], [36] are able to compute exact solutions, but they require too much computation and memory for audio applications.”
Phase Retrieval Using Alternating Minimization (2013, background): “Inspired by the recent literature on trace norm relaxation of the rank constraint, they design SDPs to solve this problem.”
Phase Retrieval from Coded Diffraction Patterns (2013, neutral): “Finally, inspired by PhaseLift and the famous MAXCUT relaxation of Goemans and Williamson, [53] proposed another semidefinite relaxation called PhaseCut whose performance from noiseless data—in terms of the number of samples needed to achieve perfect recovery—turns out to be identical to that of Pha”
Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow (2016, methodology): “Convex counterparts on the other hand rely on the so-called matrix-lifting technique orShor’s semidefinite relaxation [43], to obtain the solvers abbreviated as PhaseLift [30], PhaseCut [44], and CoRK [45].”
A Geometric Analysis of Phase Retrieval (2016, background): “1): For a fixed problem instance (fixed set of randommeasurements and fixed target x), gradient descent seems to always return a global minimizer (i.e., the target x up to a global phase shift), across many independent random initializations!”
GESPAR: Efficient Phase Retrieval of Sparse Signals (2013, methodology): “Existing approaches aimed at recovering sparse signals from their Fourier magnitude belong to two main categories: SDP-based techniques [8]–[11] and algorithms that use alternate projections (Fienup-type methods) [12].”
Phase Retrieval with Application to Optical Imaging: A contemporary overview (2015, methodology): “This approach yields several variations of existing methods, notably PhaseCut [57], which is a relaxation of the MaxCut algorithm [98] obtained by dropping the rank constraint.”
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems (2015, background): “To alleviate this computational intractability, several convex surrogates have been proposed that work particularly well when the design vectors {ai} are chosen at random [6–20].”
Phase Retrieval via Wirtinger Flow: Theory and Algorithms (2014, methodology): “For comparison, SDP based solutions such as PhaseLift [14, 17] and PhaseCut [66] would be prohibitive on a laptop computer as the lifted signal would not fit into memory.”
PhaseMax: Convex Phase Retrieval via Basis Pursuit (2016, methodology): “Prominent instances are PhaseLift [1] and PhaseCut [19].”
Invariant Scattering Convolution Networks (2012, background): “The averaging by φ 2 J at the output is also a pooling operator which aggregates coefﬁcients to build an invariant.”
Signal recovery from Pooling Representations (2013, methodology): “…show that with a trained initialization, the alternating method compares favorably with the state of the art recovery methods (for ℓ2 with no rectification) in (Waldspurger et al., 2012; Candes et al., 2013), which suggests that the above observations are not an artifcact of the alternating method.”
Compressive phase retrieval via generalized approximate message passing (2012, methodology): “For completeness, we note that Waldspurger, D’Aspremont, and Mallat mentioned, in [13], a heuristic modification by which sparsity can be leveraged within PhaseCut, but they did not investigate the performance of this approach.”
Invariant Scattering Convolution Networks (2013, background): “Indeed, one can prove [37] that x can be reconstructed from the modulus of its wavelet coefficients fjx ? ðuÞjg , up to a multiplicative constant.”