Phase recovery, MaxCut and complex semidefinite programming

DOI10.1007/S10107-013-0738-9MaRDI QIDQ2515033zbMATH OpenOpenAlexWikidataFDO

Authors Irène Waldspurger, Alexandre d'Aspremont, Stéphane Mallat

Publication date 9 February 2015

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.0102

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Phase retrieval seeks to recover a signal x from the amplitude |Ax| of linear measurements. 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-Saxton, 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.

Recommendations

• A flexible convex relaxation for phase retrieval
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Phase retrieval via Wirtinger flow: theory and algorithms
• Phase retrieval via matrix completion
• Phase retrieval via matrix completion

Cites work

• A predictor-corrector algorithm for the coupling of stiff ODEs to a particle population balance
• An Interior-Point Method for Semidefinite Programming
• An Interior-Point Perspective on Sensitivity Analysis in Semidefinite Programming
• Angular synchronization by eigenvectors and semidefinite programming
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Array imaging using intensity-only measurements
• Block coordinate descent methods for semidefinite programming
• Complex Quadratic Optimization and Semidefinite Programming
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Exact matrix completion via convex optimization
• Extended Matrix Cube Theorems with Applications to μ-Theory in Control
• First-Order Methods for Sparse Covariance Selection
• scientific article; zbMATH DE number 3850830 (Why is no real title available?)
• scientific article; zbMATH DE number 4070633 (Why is no real title available?)
• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• scientific article; zbMATH DE number 1206370 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 967931 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Laplacian eigenvalues and the maximum cut problem
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Mathematical Considerations for the Problem of Fourier Transform Phase Retrieval from Magnitude
• Matrix algorithms. Vol. 2: Eigensystems
• On approximating complex quadratic optimization problems via semidefinite programming relaxations
• On the Determination of the Phase of a Fourier Integral, I
• Perturbation theory for linear operators.
• Phase retrieval for the Cauchy wavelet transform
• Phase retrieval via matrix completion
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Probabilistic analysis of semidefinite relaxation detectors for multiple-input, multiple-output systems
• Probabilistic Analysis of Semidefinite Relaxation for Binary Quadratic Minimization
• Probabilistic analysis of the semidefinite relaxation detector in digital communications
• Robust optimization
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Semidefinite relaxation and nonconvex quadratic optimization
• Sensitivity analysis in linear programming and semidefinite programming using interior-point methods
• Smoothing technique and its applications in semidefinite optimization
• Solving quadratic equations via phaselift when there are about as many equations as unknowns
• Sparse signal recovery from quadratic measurements via convex programming
• Stable optimizationless recovery from phaseless linear measurements
• Templates for convex cone problems with applications to sparse signal recovery
• The convex geometry of linear inverse problems

Cited in

(only showing first 100 items - show all)

• Phase retrieval with one or two diffraction patterns by alternating projections with the null initialization
• The discrete sign problem: uniqueness, recovery algorithms and phase retrieval applications
• A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables
• On global convergence of gradient descent algorithms for generalized phase retrieval problem
• A flexible convex relaxation for phase retrieval
• Phase retrieval using random cubatures and fusion frames of positive semidefinite matrices
• Level-set methods for convex optimization
• Fourier phase retrieval with a single mask by Douglas-Rachford algorithms
• A geometric analysis of phase retrieval
• Phase retrieval from Fourier measurements with masks
• Fast rank-one alternating minimization algorithm for phase retrieval
• Scalable incremental nonconvex optimization approach for phase retrieval
• Convex combination of alternating projection and Douglas-Rachford operators for phase retrieval
• Robust necessary optimality conditions for nondifferentiable complex fractional programming with uncertain data
• Phase retrieval with PhaseLift algorithm
• Phase retrieval for sub-Gaussian measurements
• Optimal combination of linear and spectral estimators for generalized linear models
• A semismooth Newton-based augmented Lagrangian algorithm for density matrix least squares problems
• Solving phase retrieval with random initial guess is nearly as good as by spectral initialization
• Constructing confidence intervals for the signals in sparse phase retrieval
• On the local stability of semidefinite relaxations
• Phase retrieval of complex and vector-valued functions
• On the effect of zero-flipping on the stability of the phase retrieval problem in the Paley-Wiener class
• Phase retrieval using alternating minimization in a batch setting
• Hermitian completely positive matrices
• Phase retrieval: a data-driven wavelet frame based approach
• A brief introduction to manifold optimization
• A perturbation view of level-set methods for convex optimization
• Smoothed amplitude flow-based phase retrieval algorithm
• Saving phase: injectivity and stability for phase retrieval
• Stable phase retrieval in infinite dimensions
• Invertibility and robustness of phaseless reconstruction
• Stable phase retrieval with low-redundancy frames
• Algorithms and error bounds for noisy phase retrieval with low-redundancy frames
• The local convexity of solving systems of quadratic equations
• Fundamental limits of weak recovery with applications to phase retrieval
• Phase retrieval via sensor network localization
• Phase retrieval via sparse Wirtinger flow
• Misspecified nonconvex statistical optimization for sparse phase retrieval
• Phase retrieval from very few measurements
• Phase retrieval from coded diffraction patterns
• Admissible measurements and robust algorithms for ptychography
• Computational methods for solving nonconvex block-separable constrained quadratic problems
• Low-rank spectral optimization via gauge duality
• Nonconvex phase synchronization
• Phase retrieval from incomplete magnitude information via total variation regularization
• Phase transitions in semidefinite relaxations
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Reconstruction of signals from magnitudes of redundant representations: the complex case
• Phase retrieval for imaging problems
• Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
• The phase retrieval problem for solutions of the Helmholtz equation
• Approximate global minimizers to pairwise interaction problems via convex relaxation
• Tightness of a New and Enhanced Semidefinite Relaxation for MIMO Detection
• Iterative phase retrieval by combining modulus constraints and angle relationships
• Total variation-based phase retrieval for Poisson noise removal
• Variational phase retrieval with globally convergent preconditioned proximal algorithm
• Rank optimality for the Burer-Monteiro factorization
• Solving phase retrieval via graph projection splitting
• The Cramer-Rao lower bound in a non-AWGN model for the affine phase retrieval
• Toward a mathematical theory of the crystallographic phase retrieval problem
• scientific article; zbMATH DE number 7626745 (Why is no real title available?)
• Approximate message passing with spectral initialization for generalized linear models*
• Quantization-aware phase retrieval
• Linear Convergence of Randomized Kaczmarz Method for Solving Complex-Valued Phaseless Equations
• A generalization of Wirtinger flow for exact interferometric inversion
• PhaseMax: stable guarantees from noisy sub-Gaussian measurements
• Well-conditioned ptychograpic imaging via lost subspace completion
• On the simplicity and conditioning of low rank semidefinite programs
• An optimal-storage approach to semidefinite programming using approximate complementarity
• Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
• Benchmark problems for phase retrieval
• A proximal operator for multispectral phase retrieval problems
• Global registration of multiple point clouds using semidefinite programming
• Solving PhaseLift by Low-Rank Riemannian Optimization Methods for Complex Semidefinite Constraints
• Robust phase retrieval via median-truncated smoothed amplitude flow
• The global landscape of phase retrieval. I: Perturbed amplitude models
• The global landscape of phase retrieval. II: Quotient intensity models
• Sampling complexity on phase retrieval from masked Fourier measurements via Wirtinger flow
• The numerics of phase retrieval
• Dynamic Fourier ptychography with deep spatiotemporal priors
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
• A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds
• A Dynamic Smoothing Technique for a Class of Nonsmooth Optimization Problems on Manifolds
• Compressive phase retrieval: Optimal sample complexity with deep generative priors
• Provable sample-efficient sparse phase retrieval initialized by truncated power method
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• New semidefinite relaxations for a class of complex quadratic programming problems
• Provable Phase Retrieval with Mirror Descent
• A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem
• Performance bounds of the intensity-based estimators for noisy phase retrieval
• Polarimetric Fourier phase retrieval
• A sublinear functional based approximated equivalence to optimality and duality for multiobjective programming in complex spaces
• Towards a bilipschitz invariant theory
• Riesz feature representation: scale equivariant scattering network for classification tasks
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
• Truncated amplitude flow with coded diffraction patterns
• Argument division based branch-and-bound algorithm for unit-modulus constrained complex quadratic programming
• Gabor phase retrieval via semidefinite programming
• Convergence analysis of Wirtinger flow for Poisson phase retrieval

Describes a project that uses

Uses Software

• SDPT3
• TFOCS
• PhaseLift

This page was built for publication: Phase recovery, MaxCut and complex semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2515033)