Stable optimizationless recovery from phaseless linear measurements

DOI10.1007/S00041-013-9305-2zbMATH Open1330.90069arXiv1208.1803OpenAlexW2155434899MaRDI QIDQ485222FDOQ485222

Authors: Laurent Demanet, Paul E. Hand 

Publication date: 9 January 2015

Published in: The Journal of Fourier Analysis and Applications (Search for Journal in Brave)

Abstract: We address the problem of recovering an n-vector from m linear measurements lacking sign or phase information. We show that lifting and semidefinite relaxation suffice by themselves for stable recovery in the setting of m = O(n log n) random sensing vectors, with high probability. The recovery method is optimizationless in the sense that trace minimization in the PhaseLift procedure is unnecessary. That is, PhaseLift reduces to a feasibility problem. The optimizationless perspective allows for a Douglas-Rachford numerical algorithm that is unavailable for PhaseLift. This method exhibits linear convergence with a favorable convergence rate and without any parameter tuning.

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

Recommendations

• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Stable signal recovery from phaseless measurements
• PhaseLiftOff: an accurate and stable phase retrieval method based on difference of trace and Frobenius norms
• Phase retrieval with PhaseLift algorithm
• The recovery of complex sparse signals from few phaseless measurements

zbMATH Keywords

matrix completionliftingBernstein inequalitysemidefinite relaxationfeasibilityphase retrievalphaseliftDouglas-Rachford

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Matrix completion problems (15A83) Semidefinite programming (90C22)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Phase retrieval via matrix completion
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Cheeger Inequality for the Graph Connection Laplacian
• A predictor-corrector algorithm for the coupling of stiff ODEs to a particle population balance
• Painless reconstruction from magnitudes of frame coefficients
• On signal reconstruction without phase
• Solving quadratic equations via phaselift when there are about as many equations as unknowns
• A generalized forward-backward splitting
• Array imaging using intensity-only measurements
• Angular synchronization by eigenvectors and semidefinite programming

Cited In (32)

• Solving PhaseLift by Low-Rank Riemannian Optimization Methods for Complex Semidefinite Constraints
• The numerics of phase retrieval
• Phased and phaseless domain reconstructions in the inverse scattering problem via scattering coefficients
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Towards a bilipschitz invariant theory
• Complex phase retrieval from subgaussian measurements
• Phase retrieval from coded diffraction patterns
• Phase retrieval from very few measurements
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Fast Phase Retrieval from Local Correlation Measurements
• Phase retrieval from Fourier measurements with masks
• Phaselift is robust to a constant fraction of arbitrary errors
• Stable low-rank matrix recovery via null space properties
• Scalable incremental nonconvex optimization approach for phase retrieval
• Phaseless reconstruction from space-time samples
• Reconstruction of signals from magnitudes of redundant representations: the complex case
• Phase retrieval with one or two diffraction patterns by alternating projections with the null initialization
• Fourier phase retrieval with a single mask by Douglas-Rachford algorithms
• Solving quadratic equations via phaselift when there are about as many equations as unknowns
• PhaseMax: stable guarantees from noisy sub-Gaussian measurements
• A generalization of Wirtinger flow for exact interferometric inversion
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• On the robustness of noise-blind low-rank recovery from rank-one measurements
• Algorithms and error bounds for noisy phase retrieval with low-redundancy frames
• Title not available (Why is that?)
• Saving phase: injectivity and stability for phase retrieval
• The local convexity of solving systems of quadratic equations
• Stable phase retrieval with low-redundancy frames
• Phase recovery, MaxCut and complex semidefinite programming
• Plug-and-Play Unplugged: Optimization-Free Reconstruction Using Consensus Equilibrium
• Phase retrieval using random cubatures and fusion frames of positive semidefinite matrices
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

Uses Software

• UNLocBoX
• PhaseLift

This page was built for publication: Stable optimizationless recovery from phaseless linear measurements

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