Sharp Time-Data Tradeoffs for Linear Inverse Problems

Samet Oymak, Benjamin Recht, Mahdi Soltanolkotabi

Abstract: This paper characterizes the sharp relationship between data complexity and computational efficiency in solving linear inverse problems. We focus on the minimization of a least-squares objective subject to constraints defined by a penalty function. Through a unified convergence analysis of the Projected Gradient Descent (PGD) algorithm, we demonstrate that linear convergence rates are attainable even in the absence of strong convexity, provided the number of measurements exceeds the signal's structural complexity. For Gaussian measurement ensembles, we show that linear convergence occurs when the number of measurements is approximately four times the theoretical minimum required for recovery. Our results extend to both convex and non-convex constraints, with numerical experiments confirming that our theoretical bounds closely match empirical performance.

1. Introduction

In signal processing and machine learning, a fundamental tension exists between data acquisition and computational cost. While the field of Compressed Sensing has extensively mapped the "Phase Transition"—the minimum number of measurements ($m$) required to recover a signal of complexity ($m_0$)—the computational time required to reach a solution has often been treated as a separate concern.

This research bridges that gap by providing a rigorous mathematical framework for the "time-data tradeoff." It reveals that the volume of data collected does not merely determine the feasibility of signal recovery; it directly dictates the speed at which optimization algorithms converge.

2. Problem Formulation

The study addresses linear inverse problems where the goal is to recover a structured signal $x \in \mathbb{R}^n$ from a set of noisy linear measurements:

$$y = Ax + w$$

where $A$ is the measurement matrix and $w$ is noise. The recovery is typically framed as a constrained optimization problem:

$$\min_x \frac{1}{2} \|y - Ax\|^2 \quad \text{subject to} \quad f(x) \leq R$$

Here, $f(x)$ is a penalty function (like the $\ell_1$ norm for sparsity) that captures the structural prior of the signal. Traditional optimization theory often yields pessimistic convergence bounds for these problems because the least-squares objective is not "strongly convex" in high-dimensional settings where $m < n$.

3. Methodology: Projected Gradient Descent (PGD)

The authors analyze the Projected Gradient Descent (PGD) algorithm, which iteratively updates the signal estimate by taking a gradient step to minimize the residual and then projecting the result back onto the constraint set defined by $f(x)$.

Unified Convergence Analysis

The novelty of this work lies in its use of high-dimensional geometry—specifically Gaussian width and Gordon’s Lemma—to analyze the "descent cone" of the penalty function. The analysis identifies three distinct regimes for the algorithm's step size:

  1. Greedy: Large steps that facilitate rapid linear convergence but require a higher data overhead.
  2. Conservative: Smaller steps that allow for recovery right at the theoretical phase transition but result in slower convergence.
  3. Structure-dependent: An optimized step size that balances data requirements with iteration speed.

4. Key Insights

Linear Convergence without Strong Convexity

A primary contribution of this paper is the proof that the structure of the signal (e.g., sparsity) acts as a surrogate for strong convexity. If the signal is sufficiently structured, the algorithm only needs to behave well within the directions of that structure, allowing for exponential (linear) convergence rates.

The "4x Rule"

For Gaussian measurement matrices, the authors establish a sharp threshold: when the number of measurements $m$ is approximately four times the minimal number required for recovery ($m \approx 4m_0$), the error of the PGD algorithm drops exponentially fast. This provides a practical heuristic for practitioners: collecting slightly more data can drastically reduce the required compute time.

Robustness to Non-Convexity

Surprisingly, the framework holds for non-convex constraints, such as $\ell_p$ balls where $p < 1$. The random nature of the measurement ensembles prevents the algorithm from being trapped in local optima, demonstrating that the time-data tradeoff is a universal property of these inverse problems.

5. Empirical Validation

The theoretical findings were validated through extensive simulations and real-world data tests:

  • Synthetic Data: Tests on signals with dimension $n=1000$ using Gaussian and Bernoulli matrices showed that theoretical predictions for convergence rates matched empirical results within a factor of 1.18.
  • Natural Images: The algorithm was tested on realistic datasets (e.g., the "Eram Garden" images) using the CBM3D denoiser as a projection operator. This demonstrated that the theory applies to complex, practical recovery pipelines.
  • Hardware-Friendly Matrices: Using Subsampled Orthogonal with Random Sign (SORS) matrices, the authors showed that increasing data complexity strictly decreases the total wall-clock time, as these matrices allow for fast computations via Fast Fourier Transforms (FFT).

6. Conclusion

This work establishes that in the regime of linear inverse problems, "more data" translates to "less work." By characterizing the sharp tradeoffs between measurements and iterations, the authors provide a roadmap for designing more efficient recovery systems. Future work remains to extend these sharp bounds to other optimization variants like Stochastic Gradient Descent (SGD) and more diverse loss functions.

Summary updated

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.
BibTeX
@article{oymak2018sharp,
  author = {Samet Oymak and Benjamin Recht and Mahdi Soltanolkotabi},
  title = {{Sharp Time-Data Tradeoffs for Linear Inverse Problems}},
  journal = {IEEE Trans. Information Theory},
  year = {2018},
  url = {https://openreview.net/forum?id=9-OlW2YwaTG},
}
Figure