Renegar's Condition Number, Sharpness and Compressed Sensing Performance

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 (CS), researchers typically address two distinct questions: the statistical question of how many samples ($n$) are required to recover a signal of sparsity $k$, and the computational question of how many iterations an algorithm needs to find that signal. While empirical evidence has long suggested that "easier" recovery problems (those with more samples) are also faster to solve, a formal mathematical bridge between these two worlds was missing.

This paper establishes that bridge by demonstrating that a single parameter—a "condition number" related to the sharpness of the optimization problem—simultaneously dictates both the robustness of the solution and the convergence speed of first-order optimization methods. Central to this analysis is Renegar’s condition number, a measure of how far a mathematical program is from being "ill-posed" or unsolvable.

Methods and Theoretical Framework

Restart Schemes and Sharpness

The authors introduce a "restart" strategy for first-order methods, such as Nesterov’s accelerated gradient descent. By periodically restarting the algorithm based on the "sharpness" of the objective function, they achieve linear convergence (where error drops exponentially) rather than standard sub-linear rates.

Algorithm 1: Restart Scheme for first-order methods.

Sharpness refers to how quickly the objective value increases as one moves away from the solution. The authors prove that for $\ell_1$ minimization, the standard Nullspace Property implies a specific degree of sharpness at the optimal point. This sharpness is the key geometric property linking statistical recovery to algorithmic efficiency.

Renegar’s Condition Number

The research relates the "distance to infeasibility" of the optimization problem to the restricted eigenvalues of the sensing matrix. They show that Renegar’s condition number—originally a tool for general convex optimization—perfectly matches the restricted singular values used in compressed sensing theory. This unification allows a single geometric quantity to bound both recovery error and the number of iterations required by various solvers.

Key Results and Insights

The theoretical findings were validated using synthetic datasets consisting of random Gaussian sensing matrices and $k$-sparse signals. Key insights include:

  • Unified Parameter: The ratio between the true signal sparsity ($k$) and the maximum recoverable sparsity ($k_D$) explicitly controls the convergence rate.
  • Phase Transitions: Both computational time and recovery error undergo a "phase transition" at the same point. When the number of samples is just enough to recover a signal ($n \approx k \log p$), the condition number spikes, making the problem both statistically fragile and computationally grueling.
  • Numerical Correlation: Experiments show a striking alignment between the peaks in CPU time for solvers like LARS and the spikes in the estimated Renegar condition number. As the number of samples $n$ increases, the condition number drops, and algorithms speed up significantly.

Conclusion and Future Work

This work provides a rigorous link between the statistical and computational aspects of compressed sensing. By showing that sharpness and Renegar's condition number are common denominators, it opens doors for more efficient, data-aware solvers.

However, limitations remain. The current heuristic for estimating Renegar's condition number lacks global optimality guarantees for all types of cones. Furthermore, while the theory extends to general sparsity structures (like nuclear norms), the most detailed results focus on $\ell_1$ vector sparsity. Future work could involve designing solvers that adaptively sense this sharpness to accelerate convergence in practical, "easy" compressed sensing scenarios.

Summary updated

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.
BibTeX
@misc{roulet2015renegar,
  author = {Vincent Roulet and Nicolas Boumal and Alexandre d’Aspremont},
  title = {{Renegar's Condition Number, Sharpness and Compressed Sensing Performance}},
  year = {2015},
  eprint = {1506.03295},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1506.03295},
}
Figure