Structured Signal Recovery From Quadratic Measurements: Breaking Sample Complexity Barriers via Nonconvex Optimization

This paper concerns the problem of recovering an unknown but structured signal <inline-formula> <tex-math notation="LaTeX">${x}\in \mathbb {R} ^{n}$ </tex-math></inline-formula> from <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula>-quadratic measurements of the form <inline-formula> <tex-math notation="LaTeX">${y}_{r}= \left |{\langle {a}_{r}, {x}\rangle }\right |^{{2}}$ </tex-math></inline-formula> for <inline-formula> <tex-math notation="LaTeX">${r}={1},{2},\ldots, {m}$ </tex-math></inline-formula>. We focus on the under-determined setting where the number of measurements is significantly smaller than the dimension of the signal (<inline-formula> <tex-math notation="LaTeX">${m} < < {n}$ </tex-math></inline-formula>). We formulate the recovery problem as a nonconvex optimization problem where prior structural information about the signal is enforced through constrains on the optimization variables. We prove the projected gradient descent, when initialized in a neighborhood of the desired signal, converges to the unknown signal at a linear rate. These results hold for <italic>any</italic> closed constraint set (convex or non-convex) providing convergence guarantees to the global optimum even when the objective function and constraint set are nonconvex. Furthermore, these results hold with a number of measurements that are only a constant factor away from the minimal number of measurements required to uniquely identify the unknown signal. Our results provide the first provably tractable algorithm for this data-poor regime, breaking local sample complexity barriers that have emerged in this paper. In this paper, we utilize and further develop powerful tools for uniform convergence of empirical processes that may have broader implications for rigorous understanding of constrained nonconvex optimization heuristics.

• Publication year

  2017

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2017-02-20

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1109/TIT.2019.2891653arXiv 1702.06175
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A unified evaluation of iterative projection algorithms for phase retrieval

  2018cited by this paper
• Multiple illumination phaseless super-resolution (MIPS) with applications to phaseless DoA estimation and diffraction imaging

  2017cited by this paper
• Coherent inverse scattering via transmission matrices: Efficient phase retrieval algorithms and a public dataset

  2017cited by this paper
• Global Optimality of Local Search for Low Rank Matrix Recovery

  2016cited by this paper
• Direct single-shot phase retrieval from the diffraction pattern of separated objects

  2016influential reference
• A Geometric Analysis of Phase Retrieval

  2016cited by this paper
• Matrix Completion has No Spurious Local Minimum

  2016cited by this paper
• Reconstruction of Signals From Their Autocorrelation and Cross-Correlation Vectors, With Applications to Phase Retrieval and Blind Channel Estimation

  2016cited by this paper
• The discrete sign problem: Uniqueness, recovery algorithms and phase retrieval applications

  2016cited by this paper
• Sparse Phase Retrieval via Truncated Amplitude Flow

  2016cited by this paper
• Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space

  2016cited by this paper
• Fast Phase Retrieval for High Dimensions: A Block-Based Approach

  2016cited by this paper
• A simple tool for bounding the deviation of random matrices on geometric sets

  2016cited by this paper
• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization

  2016cited by this paper
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations

  2016cited by this paper
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow

  2016cited by this paper
• Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation

  2016cited by this paper
• Finding Low-rank Solutions to Matrix Problems, Efficiently and Provably

  2016cited by this paper
• Non-Convex Phase Retrieval From STFT Measurements

  2016cited by this paper
• An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax

  2016cited by this paper
• Provable Non-convex Phase Retrieval with Outliers: Median TruncatedWirtinger Flow

  2016cited by this paper
• Median-Truncated Nonconvex Approach for Phase Retrieval With Outliers

  2016cited by this paper
• PhaseMax: Convex Phase Retrieval via Basis Pursuit

  2016influential reference
• Fast and Reliable Parameter Estimation from Nonlinear Observations

  2016cited by this paper
• The non-convex Burer-Monteiro approach works on smooth semidefinite programs

  2016cited by this paper
• Solving Random Systems of Quadratic Equations via Truncated Generalized Gradient Flow

  2016cited by this paper
• Phase Retrieval With Random Gaussian Sensing Vectors by Alternating Projections

  2016cited by this paper
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent

  2016cited by this paper
• Reshaped Wirtinger Flow for Solving Quadratic System of Equations

  2016cited by this paper
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems

  2015cited by this paper
• Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems

  2015cited by this paper
• A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements

  2015influential reference
• Nonconvex Low Rank Matrix Factorization via Inexact First Order Oracle

  2015cited by this paper
• Efficient Compressive Phase Retrieval with Constrained Sensing Vectors

  2015cited by this paper
• Simple, Efficient, and Neural Algorithms for Sparse Coding

  2015cited by this paper
• STFT Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms

  2015cited by this paper
• Fast Phase Retrieval from Local Correlation Measurements

  2015cited by this paper
• SAFFRON: A fast, efficient, and robust framework for group testing based on sparse-graph codes

  2015cited by this paper
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees

  2015influential reference
• Sharp Time–Data Tradeoffs for Linear Inverse Problems

  2015influential reference
• Experimental robustness of Fourier Ptychography phase retrieval algorithms

  2015influential reference
• Partially coherent phase imaging with simultaneous source recovery.

  2015cited by this paper
• Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow

  2015cited by this paper
• When Are Nonconvex Problems Not Scary?

  2015influential reference
• Fast Phase Retrieval for High-Dimensions

  2015influential reference
• Phase retrieval using iterative projections: Dynamics in the large systems limit

  2015cited by this paper
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow

  2015cited by this paper
• Phase Retrieval: An Overview of Recent Developments

  2015cited by this paper
• Finding Hidden Cliques of Size in Nearly Linear Time

  2015cited by this paper
• Sparse Phase Retrieval from Short-Time Fourier Measurements

  2014cited by this paper
• Robust sparse phase retrieval made easy

  2014cited by this paper
• Guaranteed Matrix Completion via Non-Convex Factorization

  2014cited by this paper
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms

  2014influential reference
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems

  2014cited by this paper
• Improved Recovery Guarantees for Phase Retrieval from Coded Diffraction Patterns

  2014cited by this paper
• Phase Retrieval with Application to Optical Imaging

  2014cited by this paper
• PhaseCode: Fast and efficient compressive phase retrieval based on sparse-graph codes

  2014cited by this paper
• Statistical guarantees for the EM algorithm: From population to sample-based analysis

  2014cited by this paper
• Structured Low-Rank Matrix Factorization: Optimality, Algorithm, and Applications to Image Processing

  2014cited by this paper
• Saving phase: Injectivity and stability for phase retrieval

  2013cited by this paper
• Living on the edge: phase transitions in convex programs with random data

  2013cited by this paper
• Complexity Theoretic Lower Bounds for Sparse Principal Component Detection

  2013cited by this paper
• The squared-error of generalized LASSO: A precise analysis

  2013cited by this paper
• Phase Retrieval Using Alternating Minimization

  2013cited by this paper
• A Partial Derandomization of PhaseLift Using Spherical Designs

  2013cited by this paper
• Tail bounds via generic chaining

  2013influential reference
• Sparse PCA via Covariance Thresholding

  2013cited by this paper
• Near-Optimal Compressed Sensing of a Class of Sparse Low-Rank Matrices Via Sparse Power Factorization

  2013cited by this paper
• Finding Hidden Cliques of Size $$\sqrt{N/e}$$N/e in Nearly Linear Time

  2013cited by this paper
• Sparse phase retrieval: Convex algorithms and limitations

  2013cited by this paper
• Phase Retrieval By Projections

  2013influential reference
• Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time

  2013cited by this paper
• Phase Retrieval from Coded Diffraction Patterns

  2013influential reference
• Efficient algorithms for collaborative filtering

  2012cited by this paper
• Phase recovery, MaxCut and complex semidefinite programming

  2012cited by this paper
• Oracle inequalities and the isomorphic method

  2012cited by this paper
• Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices

  2012influential reference
• Phase Retrieval: Stability and Recovery Guarantees

  2012influential reference
• Sparse Signal Recovery from Quadratic Measurements via Convex Programming

  2012cited by this paper
• On robust phase retrieval for sparse signals

  2012cited by this paper
• Compressive Phase Retrieval From Squared Output Measurements Via Semidefinite Programming

  2011cited by this paper
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming

  2011cited by this paper
• The Convex Geometry of Linear Inverse Problems

  2010cited by this paper
• Matrix completion from a few entries

  2009cited by this paper
• Matrix Completion from Noisy Entries

  2009cited by this paper
• High-dimensional analysis of semidefinite relaxations for sparse principal components

  2008cited by this paper
• High dimensional probability : proceedings of the Fourth International Conference

  2006cited by this paper
• High Dimensional Probability III

  2003cited by this paper
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization

  2003cited by this paper
• On Milman's inequality and random subspaces which escape through a mesh in ℝ n

  1988influential reference
• Phase retrieval algorithms: a comparison.

  1982cited by this paper
• MEASUREMENTS: IMPROVED ROBUSTNESS VIA EIGENVECTOR-BASED ANGULAR SYNCHRONIZATION

  year unknowncited by this paper

• Support Recovery and $\ell_2$-Error Bound for Sparse Regression with Quadratic Measurements via Weakly-Convex-Concave Regularization

  2026cites this paper
• Stability of Constrained Optimization Models for Structured Signal Recovery

  2026influential citation
• Gridless Line Spectral Estimation With Phaseless Samples

  2025cites this paper
• Phase transition of descending phase retrieval algorithms

  2025cites this paper
• Phase retrieval with rank d measurements - descending algorithms phase transitions

  2025cites this paper
• Sparse Signal Recovery From Quadratic Systems with Full-Rank Matrices

  2025cites this paper
• Optimal spectral initializers impact on phase retrieval phase transitions - an RDT view

  2025cites this paper
• Achieving Optimal Sample Complexity for a Broader Class of Signals in Sparse Phase Retrieval

  2025cites this paper
• Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization

  2025cites this paper
• GraHTP: A Provable Newton-like Algorithm for Sparse Phase Retrieval

  2024cites this paper
• Accelerated Wirtinger Flow With Score-Based Image Priors for Holographic Phase Retrieval in Poisson-Gaussian Noise Conditions

  2024cites this paper
• The Star Geometry of Critic-Based Regularizer Learning

  2024cites this paper
• Low Complexity Regularized Phase Retrieval

  2024cites this paper
• Nonlinear tomographic reconstruction via nonsmooth optimization

  2024cites this paper
• On the Phase Retrievability of Phase-Retrieval Coherent Receivers

  2024cites this paper
• Geometric Characteristics and Stable Guarantees for Phaseless Operators and Structured Matrix Restoration

  2024cites this paper
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction

  2024cites this paper
• Poisson-Gaussian Holographic Phase Retrieval with Score-based Image Prior

  2023cites this paper
• Adversarial Phase Retrieval via Nonlinear Least Absolute Deviation

  2023influential citation
• In the recovery of sparse vectors from quadratic measurements, the presence of linear terms breaks the square root bottleneck

  2023cites this paper
• AWFSD: Accelerated Wirtinger Flow with Score-based Diffusion Image Prior for Poisson-Gaussian Holographic Phase Retrieval

  2023cites this paper
• Gradient Descent Provably Solves Nonlinear Tomographic Reconstruction

  2023cites this paper
• A Fast and Provable Algorithm for Sparse Phase Retrieval

  2023cites this paper
• Heavy-Ball-Based Hard Thresholding Pursuit for Sparse Phase Retrieval Problems

  2023cites this paper
• Deep Denoising Prior-Based Spectral Estimation for Phaseless Synthetic Aperture Radar

  2023cites this paper
• Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares

  2023cites this paper
• Uniform Cramér–Rao Lower Bound for Phase Retrieval: An Empirical Study

  2022cites this paper
• Deep Phaseless Imaging via Wirtinger Flow with Decoding Prior

  2022cites this paper
• Structured Phase Retrieval-aided Channel Estimation for Millimeter-Wave/Sub-Terahertz MIMO Systems

  2022cites this paper
• Provable sample-efficient sparse phase retrieval initialized by truncated power method

  2022cites this paper
• Bisparse blind deconvolution through hierarchical sparse recovery

  2022cites this paper
• Misspecified Phase Retrieval with Generative Priors

  2022cites this paper
• Poisson Phase Retrieval in Very Low-Count Regimes

  2021cites this paper
• Riemannian thresholding methods for row-sparse and low-rank matrix recovery

  2021cites this paper
• Sample-Efficient Sparse Phase Retrieval via Stochastic Alternating Minimization

  2021cites this paper
• Optimal Convex Lifted Sparse Phase Retrieval and PCA With an Atomic Matrix Norm Regularizer

  2021cites this paper
• Unrolled Wirtinger Flow With Deep Decoding Priors for Phaseless Imaging

  2021cites this paper
• Simultaneous Monitoring of Frequency-dependent IQ Imbalances in a Dual-polarization IQ Modulator by using a Single Photodetector: A Phase Retrieval Approach

  2021cites this paper
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors

  2021cites this paper
• Passive Multistatic Radar Imaging with Prior Information

  2021cites this paper
• Understanding Overparameterization in Generative Adversarial Networks

  2021cites this paper
• PhaseEqual: Convex Phase Retrieval via Alternating Direction Method of Multipliers

  2020cites this paper
• A Deterministic Convergence Framework for Exact Non-Convex Phase Retrieval

  2020cites this paper
• Toward a mathematical theory of the crystallographic phase retrieval problem

  2020cites this paper
• 3D Phase Retrieval at Nano-Scale via Accelerated Wirtinger Flow

  2020cites this paper
• The estimation error of general first order methods

  2020cites this paper
• On the Sample Complexity of Phase-Retrieval Receiver Based on 2-D Arrayed Photodetectors

  2020cites this paper
• Phase retrieval of complex-valued objects via a randomized Kaczmarz method

  2020cites this paper
• Sparse Signal Recovery From Phaseless Measurements via Hard Thresholding Pursuit

  2020cites this paper
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance

  2020cites this paper
• A Deterministic Theory for Exact Non-Convex Phase Retrieval

  2020cites this paper
• Compressive phase retrieval: Optimal sample complexity with deep generative priors

  2020influential citation
• A Geometric Approach to Dynamical System: Global Analysis for Non-Convex Optimization

  2020influential citation
• Spectral Methods for Data Science: A Statistical Perspective

  2020cites this paper
• 3D Phaseless Imaging at Nano-scale: Challenges and Possible Solutions

  2019cites this paper
• Understanding Sample Complexities for Structured Signal Recovery from Non-Linear Measurements

  2019influential citation
• Robust Initialization Estimator and its Application in Solving Quadratic Equations

  2019cites this paper
• A Generalization of Wirtinger Flow for Exact Interferometric Inversion

  2019cites this paper
• A stochastic alternating minimizing method for sparse phase retrieval

  2019cites this paper
• A family of measurement basis for fast compressed imaging

  2019cites this paper
• Complex Phase Retrieval from Subgaussian Measurements

  2019cites this paper
• A Novel Riemannian Optimization Approach and Algorithm for Solving the Phase Retrieval Problem

  2019cites this paper
• Learning without the Phase: Regularized PhaseMax Achieves Optimal Sample Complexity

  2018cites this paper
• Sparse power factorization: balancing peakiness and sample complexity

  2018cites this paper
• Subgradient Descent Learns Orthogonal Dictionaries

  2018cites this paper
• Newton-MR: Newton's Method Without Smoothness or Convexity

  2018cites this paper
• Some Algorithms and Paradigms for Big Data

  2018cites this paper
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview

  2018cites this paper
• Accelerated Wirtinger Flow: A fast algorithm for ptychography

  2018cites this paper
• Recovering Signals from their FROG Trace

  2018cites this paper
• Phase Retrieval via Reweighted Amplitude Flow

  2018cites this paper
• Accelerated Wirtinger Flow for Multiplexed Fourier Ptychographic Microscopy

  2018cites this paper
• Fundamental Limits of Weak Recovery with Applications to Phase Retrieval

  2018cites this paper
• Optimization-Based AMP for Phase Retrieval: The Impact of Initialization and $\ell_{2}$ Regularization

  2018cites this paper
• Nonconvex Matrix Factorization From Rank-One Measurements

  2018cites this paper
• Towards Sample-Optimal Methods for Solving Random Quadratic Equations with Structure

  2018cites this paper
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval

  2018cites this paper
• Phase Retrieval by Alternating Minimization With Random Initialization

  2018cites this paper
• Learning Compact Neural Networks with Regularization

  2018cites this paper
• Nonconvex Recovery of Low-complexity Models

  2018cites this paper
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?

  2018cites this paper
• End-to-end Learning of a Convolutional Neural Network via Deep Tensor Decomposition

  2018cites this paper
• Nonlinear Structured Signal Estimation in High Dimensions via Iterative Hard Thresholding

  2018cites this paper
• Gradient Methods for Submodular Maximization

  2017cites this paper
• Fast, Sample-Efficient Algorithms for Structured Phase Retrieval

  2017cites this paper
• Sparse Phase Retrieval via Sparse PCA Despite Model Misspecification: A Simplified and Extended Analysis

  2017cites this paper
• Solving Almost all Systems of Random Quadratic Equations

  2017cites this paper
• Learning ReLUs via Gradient Descent

  2017influential citation
• A flexible convex relaxation for phase retrieval

  2017cites this paper
• Lifting high-dimensional non-linear models with Gaussian regressors

  2017cites this paper
• Phase Retrieval Using Alternating Minimization in a Batch Setting

  2017cites this paper
• Solving Most Systems of Random Quadratic Equations

  2017cites this paper
• Optimal errors and phase transitions in high-dimensional generalized linear models

  2017cites this paper
• Sublinear-Time Algorithms for Compressive Phase Retrieval

  2017cites this paper
• Sample-Efficient Algorithms for Recovering Structured Signals From Magnitude-Only Measurements

  2017cites this paper
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution

  2017cites this paper
• Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks

  2017cites this paper
• Fourier Phase Retrieval: Uniqueness and Algorithms

  2017cites this paper
• Convolutional Phase Retrieval via Gradient Descent

  2017cites this paper
• Compressive Phase Retrieval via Reweighted Amplitude Flow

  2017cites this paper