Computational Complexity versus Statistical Performance on Sparse\n Recovery Problems

Vincent Roulet, Nicolas Boumal, Alexandre d’Aspremont

Abstract

We show that several classical quantities controlling compressed sensing performance directly match classical parameters controlling algorithmic complexity. We first describe linearly convergent restart schemes on first-order methods solving a broad range of compressed sensing problems, where sharpness at the optimum controls convergence speed. We show that for sparse recovery problems, this sharpness can be written as a condition number, given by the ratio between true signal sparsity and the largest signal size that can be recovered by the observation matrix. In a similar vein, Renegar's condition number is a data-driven complexity measure for convex programs, generalizing classical condition numbers for linear systems. We show that for a broad class of compressed sensing problems, the worst case value of this algorithmic complexity measure taken over all signals matches the restricted singular value of the observation matrix which controls robust recovery performance. Overall, this means in both cases that, in compressed sensing problems, a single parameter directly controls both computational complexity and recovery performance. Numerical experiments illustrate these points using several classical algorithms.

Introduction

In the field of compressed sensing, research has traditionally been divided into two distinct perspectives. Statisticians focus on sample complexity—determining the minimum number of samples ($n$) required to recover a sparse signal of size $s$. Conversely, optimization theorists focus on iteration complexity—calculating how many steps an algorithm must take to reach a desired precision.

While practitioners have long observed that problems with ample samples are easier to solve numerically, a formal theoretical bridge between these two domains has been lacking. This paper establishes that link, proving that the geometric properties of an observation matrix that guarantee robust statistical recovery are the same properties that accelerate first-order optimization methods.

Theoretical Framework: Sharpness and Condition Numbers

The authors identify two primary geometric parameters that unify statistical and computational performance:

1. Sharpness and the Null Space Property

Sharpness describes how steeply an objective function rises away from its minimum. The authors demonstrate that in sparse recovery, sharpness is mathematically equivalent to the Null Space Property (NSP), a foundational condition used to guarantee exact recovery. By defining sharpness as a ratio between the true signal sparsity and the maximum recoverable signal size, the authors provide a physical intuition for an abstract optimization parameter.

2. Renegar’s Condition Number

Renegar’s condition number serves as a data-driven complexity measure for convex programs. The paper proves that for a broad class of compressed sensing problems, the worst-case value of this condition number matches the restricted singular value of the observation matrix. Because the restricted singular value is the standard metric for statistical robustness against noise, this finding implies that a single parameter governs both the algorithm's sensitivity to data perturbations and its computational speed.

Methods and Algorithmic Acceleration

To test these theoretical links, the authors utilize several key methodologies:

  • Restart Schemes: They apply a "restart" strategy to standard first-order methods (such as NESTA). By stopping and restarting the algorithm with updated parameters, they transform standard sub-linear convergence into much faster linear convergence, provided the problem exhibits sufficient sharpness.
  • Decomposable Norms: While the primary focus is on $\ell_1$ norm sparsity, the results are generalized to group norms and nuclear norms, extending the findings to matrix sparsity and low-rank recovery.
  • Synthetic Benchmarking: The study uses synthetic datasets consisting of random Gaussian observation matrices and sparse signals with varying noise levels to precisely control variables and observe phase transitions.

Key Insights: The "One Parameter" Rule

The most significant insight of this work is the "One Parameter" rule: a single geometric quantity (the minimal conically restricted singular value) controls both statistical robustness and computational speed. This leads to several critical observations:

  • Computational Phase Transitions: Just as there is a statistical phase transition where recovery becomes possible as samples increase, there is a corresponding computational phase transition. Algorithms struggle most and take the longest to converge near the boundary where recovery barely succeeds.
  • Oversampling as an Accelerator: Increasing the number of samples does more than just improve accuracy; it directly increases the rate of convergence. Numerical results confirm that as the oversampling ratio increases, the convergence slope becomes significantly steeper.

Results and Limitations

Numerical experiments confirm that the CPU time for solvers like L1-Homotopy and TFOCS peaks exactly at the statistical phase transition. Furthermore, the restarted NESTA algorithm successfully achieves linear convergence at a rate explicitly determined by the problem's sharpness.

However, some discrepancies remain in noisy scenarios. The authors noted that in the presence of noise, certain algorithms (like L1-Homotopy) showed relatively constant computation times regardless of sample count, suggesting the link in the "robust" case is not yet fully captured. Additionally, the optimal restart scheme requires knowing the sharpness constant $\gamma$, which is typically unknown in practice and currently requires heuristic estimation via grid-search.

Conclusion

By showing that statistical hardness and computational complexity are two sides of the same coin, this research provides a unified framework for understanding sparse recovery. Future work may involve quantifying these parameters for a broader class of functions using the Łojasiewicz inequality, potentially leading to more automated and efficient algorithm selection across diverse optimization problems.

Summary updated

Abstract

We show that several classical quantities controlling compressed sensing\nperformance directly match classical parameters controlling algorithmic\ncomplexity. We first describe linearly convergent restart schemes on\nfirst-order methods solving a broad range of compressed sensing problems, where\nsharpness at the optimum controls convergence speed. We show that for sparse\nrecovery problems, this sharpness can be written as a condition number, given\nby the ratio between true signal sparsity and the largest signal size that can\nbe recovered by the observation matrix. In a similar vein, Renegar's condition\nnumber is a data-driven complexity measure for convex programs, generalizing\nclassical condition numbers for linear systems. We show that for a broad class\nof compressed sensing problems, the worst case value of this algorithmic\ncomplexity measure taken over all signals matches the restricted singular value\nof the observation matrix which controls robust recovery performance. Overall,\nthis means in both cases that, in compressed sensing problems, a single\nparameter directly controls both computational complexity and recovery\nperformance. Numerical experiments illustrate these points using several\nclassical algorithms.\n
BibTeX
@misc{roulet2015computational,
  author = {Vincent Roulet and Nicolas Boumal and Alexandre d’Aspremont},
  title = {{Computational Complexity versus Statistical Performance on Sparse\textbackslash\{\}n Recovery Problems}},
  year = {2015},
  eprint = {1506.03295},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1506.03295},
}
Figure