Are good local minima wide in sparse recovery?

Michael Moeller, Otmar Loffeld, Juergen Gall, Felix KrahmerarXiv 2018 · arXiv

Abstract

Sparse recovery via Iterative Hard Thresholding (IHT) often settles in suboptimal local minima due to the non-convexity of the sparsity constraint. This paper investigates the geometric properties of these minima, hypothesizing that "good" minima (those with lower objective values) possess wider basins of attraction than "bad" ones. By introducing stochastic perturbations—specifically additive noise and dropout-inspired parametric updates—the authors demonstrate significant reductions in reconstruction error. Results show up to a 6x improvement in objective error, suggesting that the optimization landscape can be effectively navigated by exploiting these geometric differences.

Introduction

In compressed sensing, the objective is to recover a sparse signal $u$ from a limited number of linear measurements $f = Au$. This is typically formulated as a constrained optimization problem: $$\min_u \|Au - f\|^2 \quad \text{subject to} \quad \|u\|_0 \le s$$ Because the $\ell_0$ "norm" is non-convex, the resulting energy landscape is riddled with local minima. The Iterative Hard Thresholding (IHT) algorithm is a standard greedy approach for this problem, but it frequently converges to inferior local solutions. This study explores whether the geometry of these basins of attraction can be leveraged to improve recovery performance.

The Wide Minima Hypothesis

The central hypothesis of this work is that high-quality local minima in sparse recovery problems are "wider" than poor ones. In this context, "width" refers to the size of the basin of attraction. A narrow, steep-walled basin represents a "bad" local minimum that is easy to escape with a small perturbation, whereas a broad, deep valley represents a "good" minimum (often the global one) that is more robust to such "kicks."

Visualization of the optimization landscape showing a wide, deep 'good' minimum (blue) versus a narrower, shallower 'bad' minimum (orange).

Methodology

The authors compared three algorithmic variants:

  1. Classical IHT: The baseline gradient projection method with hard-thresholding.
  2. Noisy IHT: Standard IHT periodically perturbed with zero-mean Gaussian noise to facilitate escape from narrow local minima.
  3. Parametric IHT: A deep-learning-inspired approach where IHT iterations are treated as layers in a neural network. This version utilizes dropout (randomly zeroing 5% of entries) during training to provide structured exploration of the landscape.

Experiments were conducted using synthetic benchmarks with random Gaussian measurement matrices ($n=200$, $m \in [50, 120]$) and signals of varying relative sparsity.

Results and Discussion

The introduction of stochasticity led to substantial performance gains. As shown in the comparative heatmaps below, both perturbed methods significantly outperformed the classical baseline across various measurement and sparsity regimes.

Comparison of mean objective error across Classical IHT, Noisy IHT, and Parametric IHT for varying measurements and sparsity.

Quantitatively, Noisy IHT reduced the mean objective error by a factor of 3.4, while Parametric IHT achieved a 6x reduction. The parametric approach proved particularly robust in challenging regimes with fewer measurements.

Method Avg. $100 \cdot \|Au - f\|^2$
Classical IHT 2.0
Noisy IHT 0.59
Parametric IHT 0.33

Conclusion

This research provides empirical evidence that "good" local minima in sparse recovery are indeed wider than "bad" ones. While the Parametric IHT approach introduces higher computational costs (taking seconds vs. milliseconds), the dramatic increase in reconstruction accuracy and robustness suggests that geometric-aware optimization is a promising direction for non-convex signal recovery. Future work aims to provide a formal theoretical link between matrix properties (like RIP) and the width of these basins.

Summary updated

Abstract

The idea of compressed sensing is to exploit representations in suitable (overcomplete) dictionaries that allow to recover signals far beyond the Nyquist rate provided that they admit a sparse representation in the respective dictionary. The latter gives rise to the sparse recovery problem of finding the best sparse linear approximation of given data in a given generating system. In this paper we analyze the iterative hard thresholding (IHT) algorithm as one of the most popular greedy methods for solving the sparse recovery problem, and demonstrate that systematically perturbing the IHT algorithm by adding noise to intermediate iterates yields improved results. Further improvements can be obtained by entirely rephrasing the problem as a parametric deep-learning-type of optimization problem. By introducing perturbations via dropout, we demonstrate to significantly outperform the classical IHT algorithm, obtaining $3$ to $6$ times lower average objective errors.
BibTeX
@misc{moeller2018are,
  author = {Michael Moeller and Otmar Loffeld and Juergen Gall and Felix Krahmer},
  title = {{Are good local minima wide in sparse recovery?}},
  year = {2018},
  eprint = {1806.08296},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.08296},
}
Figure