Sharp Time–Data Tradeoffs for Linear Inverse Problems

DOI10.1109/TIT.2017.2773497zbMath1395.90205arXiv1507.04793OpenAlexW2964309963MaRDI QIDQ5375567

Benjamin Recht, Mahdi Soltanolkotabi, Samet Oymak

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)

Related Items (14)

\(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed? ⋮ Generalizing CoSaMP to signals from a union of low dimensional linear subspaces ⋮ Generic error bounds for the generalized Lasso with sub-exponential data ⋮ Fast and Reliable Parameter Estimation from Nonlinear Observations ⋮ 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 ⋮ A simple homotopy proximal mapping algorithm for compressive sensing ⋮ Heavy-ball-based optimal thresholding algorithms for sparse linear inverse problems ⋮ Noisy linear inverse problems under convex constraints: exact risk asymptotics in high dimensions ⋮ An Equivalence between Critical Points for Rank Constraints Versus Low-Rank Factorizations ⋮ Sharp oracle inequalities for least squares estimators in shape restricted regression ⋮ Precise statistical analysis of classification accuracies for adversarial training ⋮ On the Convergence Rate of Projected Gradient Descent for a Back-Projection Based Objective

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