# Sharp Time--Data Tradeoffs for Linear Inverse Problems

arXiv: https://arxiv.org/abs/1507.04793 · HTML: https://mlsanity.com/paper/1507.04793/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2015.

## Built on by (most cited first, 8 of 8)

- [Stochastic Primal-Dual Deep Unrolling](https://mlsanity.com/paper/2110.10093/) (2021)
- [Gradient Descent Provably Solves Nonlinear Tomographic Reconstruction](https://mlsanity.com/paper/2310.03956/) (2023)
- [The Star Geometry of Critic-Based Regularizer Learning](https://mlsanity.com/paper/2408.16852/) (2024)
- [Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing](https://mlsanity.com/paper/2101.05113/) (2021)
- [DDPG-Driven Deep-Unfolding with Adaptive Depth for Channel Estimation with Sparse Bayesian Learning](https://mlsanity.com/paper/2201.08477/) (2022)
- [Equivariance Regularization for Image Reconstruction](https://mlsanity.com/paper/2202.05062/) (2022)
- [An Iteratively Reweighted Method for Sparse Optimization on Nonconvex ℓp Ball](https://mlsanity.com/paper/2104.02912/) (2021)
- [Constrained Optimization Involving Nonconvex ℓp Norms: Optimality Conditions, Algorithm and Convergence](https://mlsanity.com/paper/2110.14127/) (2021)

## Abstract (arXiv)

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.