Sharp Time-Data Tradeoffs for Linear Inverse Problems

Samet Oymak, Benjamin Recht, Mahdi Soltanolkotabi

TL;DR

This paper provides a precise mathematical characterization of how the amount of available data directly dictates the speed of optimization algorithms. The authors prove that for linear inverse problems, having "extra" data doesn't just improve accuracy—it enables Projected Gradient Descent (PGD) to converge at a fast linear rate, even for non-convex constraints where global convergence is usually not guaranteed.

What Problem Does This Paper Address?

In the world of high-dimensional sensing (like MRI or compressed sensing), we often try to recover a structured signal (like a sparse image) from a limited number of noisy linear measurements ($y = Ax + w$). While researchers have long known the "phase transition"—the minimum amount of data required to make recovery possible—we have lacked a precise understanding of how data size affects computational runtime.

Standard optimization theory often provides "pessimistic" bounds for these problems because the objectives are typically not "strongly convex" or "smooth" in the traditional sense. This paper fills that gap by providing sharp, non-asymptotic bounds on the convergence rate of the Projected Gradient Descent (PGD) algorithm, showing exactly how the number of measurements ($m$) trades off against the number of iterations ($\tau$) needed to reach a solution.

Methods

The authors focus on the Projected Gradient Descent (PGD) algorithm applied to a least-squares objective subject to a structural constraint (e.g., sparsity).

The key technical innovation is the use of cone-restricted eigenvalues and Gaussian width. Instead of looking at the properties of the measurement matrix $A$ across the entire space, they analyze how $A$ behaves when restricted to the "descent cone" of the signal's structure.

The paper analyzes three learning parameter regimes:

  1. Greedy: $\mu \approx 1/m$, leading to fast linear convergence but requiring more data.
  2. Conservative: $\mu \approx 1/n$, ensuring convergence right at the phase transition but at a slower geometric rate.
  3. Structure-dependent: A tuned step size that balances data efficiency and speed.

The analysis covers several random measurement ensembles:

  • Gaussian matrices: The primary focus, yielding the sharpest constants.
  • Isotropic Sub-Gaussian matrices: Generalizing the results to a broader class of random data.
  • SORS (Subsampled Orthogonal with Random Sign): Computationally efficient matrices (like subsampled Fourier transforms) used in real-world applications.

Datasets

The authors validate their theory using both synthetic and real-world data:

  • Synthetic Sparse Signals: Randomly generated signals of dimension $n=1000$ with varying sparsity levels ($s$).
  • Natural Images: The "Eram Garden" (Shiraz) and "Fine nerve fibres" images were used to demonstrate image recovery from under-sampled DCT measurements.
  • CBM3D Denoiser: While not a "dataset" per se, the authors used the state-of-the-art CBM3D image denoiser as a "proximal operator" within their PGD framework to show that their theory extends to complex, non-mathematically-explicit structural constraints.

Key Insights and Ideas

  • "More Data, Less Work": This is the central "aha moment." For Gaussian measurements, once you have roughly 4 times the minimum data required for recovery (the phase transition), PGD achieves a fast linear convergence rate. Increasing data further continues to reduce the number of iterations needed for a target accuracy.
  • Linear Convergence without Strong Convexity: Usually, linear convergence requires the objective function to be "strongly convex." The authors show that the structure of the signal (the constraint set) provides a "restricted" version of this property, allowing for fast convergence even in under-determined systems.
  • Non-Convexity is Not a Barrier: Surprisingly, the results apply to non-convex constraints (like $\ell_p$ balls for $p < 1$). The authors prove that PGD will not get trapped in local optima and will converge to the global solution under similar data-complexity conditions as the convex case.
  • Computational Sweet Spot: For Gaussian matrices, the total computational complexity (time) decreases as you add more data, up to a point ($m \approx 21.75 m_0$). Beyond that, the cost of processing each iteration (applying the matrix $A$) starts to outweigh the benefit of needing fewer iterations.

Key Results

  • Sharp Theoretical Bounds: The derived convergence rates match empirical performance within a factor of 1.18.
  • The 4x Rule: For convex problems with Gaussian measurements, linear convergence is guaranteed when $m > 4m_0$ (where $m_0$ is the phase transition point).
  • Image Recovery: In natural image experiments, the authors showed that 30-40% under-sampling was sufficient to recover high-quality images (relative error < 5%) using a PGD-like algorithm (Proximal Gradient) with the CBM3D denoiser.
  • SORS Efficiency: For Fourier-based measurements, the "more data, less work" effect is even more pronounced because the cost of applying the matrix (via FFT) doesn't increase linearly with the number of measurements.

Limitations and Future Work

  • Optimal Tuning: Much of the analysis assumes the constraint level $R$ (the "budget" for the penalty function) is perfectly tuned to the true signal. While they discuss stability to mis-tuning, practical implementation often requires cross-validation.
  • Non-Gaussian Constants: While the theory holds for sub-Gaussian and SORS matrices, the constants are not as "sharp" as the Gaussian case, often involving extra logarithmic factors.
  • General Loss Functions: The current paper focuses primarily on the least-squares ($\ell_2$) loss. The authors suggest that extending this to other loss functions (like $\ell_1$ or robust losses) is a promising direction for future research.
  • Update Strategies: The work focuses on PGD; extending these sharp tradeoffs to other popular algorithms like ADMM or stochastic gradient descent remains an open area.

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 four times the minimal number required to recover the desired signal at all (also known as 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},
}

Loading related content...

Figure