Fundamental limits of weak recovery with applications to phase retrieval

DOI10.1007/s10208-018-9395-yzbMath1464.62296arXiv1708.05932OpenAlexW2964130120MaRDI QIDQ2420637

Marco Mondelli, Andrea Montanari

Publication date: 6 June 2019

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

mutual informationphase transitionphase retrievalsecond-moment methodspectral initialization

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Generalized linear models (logistic models) (62J12) Signal detection and filtering (aspects of stochastic processes) (60G35) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Related Items

The numerics of phase retrieval, Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery, Approximate message passing with spectral initialization for generalized linear models*, Linear Convergence of Randomized Kaczmarz Method for Solving Complex-Valued Phaseless Equations, Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution, Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval, Provable sample-efficient sparse phase retrieval initialized by truncated power method, Complex phase retrieval from subgaussian measurements, Unnamed Item, Estimation from nonlinear observations via convex programming with application to bilinear regression, Optimal combination of linear and spectral estimators for generalized linear models, Generalized approximate survey propagation for high-dimensional estimation ^*, Local saddles of relaxed averaged alternating reflections algorithms on phase retrieval, A Spectral Estimation Framework for Phase Retrieval via Bregman Divergence Minimization, Graph Powering and Spectral Robustness

Uses Software

• PhaseMax
• PhaseLift
• Wirtinger Flow

Cites Work

• SLOPE is adaptive to unknown sparsity and asymptotically minimax
• Belief propagation, robust reconstruction and optimal recovery of block models
• Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow
• High dimensional robust M-estimation: asymptotic variance via approximate message passing
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• Outliers in the spectrum of large deformed unitarily invariant models
• On sample eigenvalues in a generalized spiked population model
• The Pauli problem, state reconstruction and quantum-real numbers
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Spectral analysis of large dimensional random matrices
• Limit laws for random matrices and free products
• Free convolution and the random sum of matrices
• A flexible convex relaxation for phase retrieval
• A strong converse bound for multiple hypothesis testing, with applications to high-dimensional estimation
• Analysis of the limiting spectral distribution of large dimensional random matrices
• Saving phase: injectivity and stability for phase retrieval
• Rapid, robust, and reliable blind deconvolution via nonconvex optimization
• Universality in polytope phase transitions and message passing algorithms
• On signal reconstruction without phase
• An algebraic characterization of injectivity in phase retrieval
• Phase recovery, MaxCut and complex semidefinite programming
• Phase retrieval from coded diffraction patterns
• Estimation of low-rank matrices via approximate message passing
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Phase Transitions and Sample Complexity in Bayes-Optimal Matrix Factorization
• Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
• The Generalized Lasso With Non-Linear Observations
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Blind Recovery of Sparse Signals From Subsampled Convolution
• Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
• Maximum likelihood estimation of liner signal parameters for Poisson processes
• Recursive consistent estimation with bounded noise
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• PhaseMax: Convex Phase Retrieval via Basis Pursuit
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Phase Retrieval Using Alternating Minimization
• The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
• Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Optimal errors and phase transitions in high-dimensional generalized linear models
• Structured Signal Recovery From Quadratic Measurements: Breaking Sample Complexity Barriers via Nonconvex Optimization
• The LASSO Risk for Gaussian Matrices
• The Noise-Sensitivity Phase Transition in Compressed Sensing
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• Matrix Completion From a Few Entries
• Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing
• Bits From Photons: Oversampled Image Acquisition Using Binary Poisson Statistics
• Low-rank matrix completion using alternating minimization
• DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES
• The Rotation of Eigenvectors by a Perturbation. III
• Phase Retrieval via Matrix Completion