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

DOI10.1109/TIT.2019.2891653MaRDI QIDQ5223938zbMATH OpenOpenAlexWikidataFDO

Authors Mahdi Soltanolkotabi

Publication date 19 July 2019

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: This paper concerns the problem of recovering an unknown but structured signal $xin{R}^n$ from $m$ quadratic measurements of the form $y_r=|<a_r,x>{|}^2$ for $r=1,2,\mathrm{...},m$. We focus on the under-determined setting where the number of measurements is significantly smaller than the dimension of the signal ($m<<n$). 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 that 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 any constraint set (convex or nonconvex) providing convergence guarantees to the global optimum even when the objective function and constraint set is nonconvex. Furthermore, these results hold with a number of measurements that is 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 recent literature. In a companion paper we demonstrate favorable properties for the optimization problem that may enable similar results to continue to hold more globally (over the entire ambient space). Collectively these two papers utilize and develop powerful tools for uniform convergence of empirical processes that may have broader implications for rigorous understanding of constrained nonconvex optimization heuristics. The mathematical results in this paper also pave the way for a new generation of data-driven phase-less imaging systems that can utilize prior information to significantly reduce acquisition time and enhance image reconstruction, enabling nano-scale imaging at unprecedented speeds and resolutions.

Cited in

(21)

• Sparse power factorization: balancing peakiness and sample complexity
• Strong convergence of alternated inertial \(CQ\) relaxed method with application in signal recovery
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Complex phase retrieval from subgaussian measurements
• Fundamental limits of weak recovery with applications to phase retrieval
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Sparse signal recovery from phaseless measurements via hard thresholding pursuit
• Convex Recovery of a Structured Signal from Independent Random Linear Measurements
• scientific article; zbMATH DE number 1791060 (Why is no real title available?)
• Fast and reliable parameter estimation from nonlinear observations
• Toward a mathematical theory of the crystallographic phase retrieval problem
• A generalization of Wirtinger flow for exact interferometric inversion
• A block-iterative surrogate constraint splitting method for quadratic signal recovery
• On the Trade-Off Between Bit Depth and Number of Samples for a Basic Approach to Structured Signal Recovery From <inline-formula> <tex-math notation="LaTeX">$b$ </tex-math> </inline-formula>-Bit Quantized Linear Measurements
• Compressive phase retrieval: Optimal sample complexity with deep generative priors
• Riemannian thresholding methods for row-sparse and low-rank matrix recovery
• Provable sample-efficient sparse phase retrieval initialized by truncated power method
• Stability in phase retrieval: characterizing condition numbers and the optimal vector set
• Nonlinear tomographic reconstruction via nonsmooth optimization
• Sparse recovery from quadratic measurements with external field
• BranchHull: convex bilinear inversion from the entrywise product of signals with known signs

This page was built for publication: Structured Signal Recovery From Quadratic Measurements: Breaking Sample Complexity Barriers via Nonconvex Optimization

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