Sharp Time–Data Tradeoffs for Linear Inverse Problems

DOI10.1109/TIT.2017.2773497MaRDI QIDQ5375567zbMATH OpenOpenAlexFDO

Authors Samet Oymak, Benjamin Recht, Mahdi Soltanolkotabi

Publication date 14 September 2018

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

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

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Derivative-free methods and methods using generalized derivatives (90C56) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20)

Abstract: In this paper we characterize sharp time-data tradeoffs for optimization problems used for solving linear inverse problems. We focus on the minimization of a least-squares objective subject to a constraint defined as the sub-level set of a penalty function. We present a unified convergence analysis of the gradient projection algorithm applied to such problems. We sharply characterize the convergence rate associated with a wide variety of random measurement ensembles in terms of the number of measurements and structural complexity of the signal with respect to the chosen penalty function. The results apply to both convex and nonconvex constraints, demonstrating that a linear convergence rate is attainable even though the least squares objective is not strongly convex in these settings. When specialized to Gaussian measurements our results show that such linear convergence occurs when the number of measurements is merely 4 times the minimal number required to recover the desired signal at all (a.k.a. the phase transition). We also achieve a slower but geometric rate of convergence precisely above the phase transition point. Extensive numerical results suggest that the derived rates exactly match the empirical performance.

Cited in

(18)

• Sharp oracle inequalities for least squares estimators in shape restricted regression
• Precise statistical analysis of classification accuracies for adversarial training
• Generalizing CoSaMP to signals from a union of low dimensional linear subspaces
• A simple homotopy proximal mapping algorithm for compressive sensing
• \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed?
• Generic error bounds for the generalized Lasso with sub-exponential data
• Data quality for the inverse lsing problem
• Fast and reliable parameter estimation from nonlinear observations
• Tradeoffs Between Convergence Speed and Reconstruction Accuracy in Inverse Problems
• An equivalence between critical points for rank constraints versus low-rank factorizations
• On the convergence rate of projected gradient descent for a back-projection based objective
• Sharp global convergence guarantees for iterative nonconvex optimization with random data
• A unified analysis of convex and non-convex \(\ell_p\)-ball projection problems
• A unified approach to uniform signal recovery from nonlinear observations
• Heavy-ball-based optimal thresholding algorithms for sparse linear inverse problems
• Noisy linear inverse problems under convex constraints: exact risk asymptotics in high dimensions
• Practical operator sketching framework for accelerating iterative data-driven solutions in linear inverse problems
• Minimization over the _p ball using a hybrid first-order method

This page was built for publication: Sharp Time–Data Tradeoffs for Linear Inverse Problems

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