The Nonconvex Geometry of Linear Inverse Problems

Armin Eftekhari, Peyman Mohajerin EsfahaniarXiv 2021 · arXiv

Introduction

In the field of machine learning and signal processing, there exists a fundamental tension between the mathematical convenience of convexity and the geometric precision of nonconvexity. Traditional approaches to linear inverse problems rely heavily on convex relaxations, such as $\ell_1$ minimization, to recover sparse signals. However, these methods often suffer from "geometric blur," where the convex hull of the signal's alphabet is too coarse to capture fine-grained structures. This paper introduces the $gauge_p$ function, a nonconvex generalization of the classical gauge function that provides a tighter grip on sparsity and successfully recovers signals where traditional convex methods fail.

The Problem: Geometric Blur in Convex Relaxations

Linear inverse problems aim to recover a hidden signal $x^\sharp$ from noisy observations $y = \mathcal{L}(x^\sharp) + e$. We typically assume $x^\sharp$ is "simple," meaning it is a sparse combination of atoms from a known alphabet $\mathcal{A}$. The standard approach uses a convex gauge function (atomic norm) as a regularizer.

The authors argue that forcing the complexity measure to be convex often loses the essential geometry of the alphabet. For instance, in manifold learning or Sparse PCA, the convex hull of the alphabet can be significantly "fatter" than the set of sparse signals itself. This discrepancy leads to statistical failure because the convex machine cannot distinguish the true signal from other points within the large convex hull.

The spiral manifold illustrates how a convex hull (the shaded region) can be much larger than the actual signal set, leading to statistical failure.

The $gauge_p$ Learning Machine

To address these limitations, the paper proposes the $gauge_p$ function ($\mathcal{G}_{\mathcal{A},p}$). Unlike classical gauge functions that consider the entire convex hull, the $gauge_p$ function restricts its focus to "slices" of the convex hull formed by at most $p$ atoms.

The $gauge_p$ function considers low-dimensional slices (a) of the convex hull, distinguishing between exposed and hidden faces (b) to provide a tighter geometric fit.

Key features of this approach include:

  1. Tunable Complexity: By varying $p$, the function interpolates between the hard $\ell_0$-pursuit (small $p$) and the classical convex machine (large $p$).
  2. Guaranteed Sparsity: If the $gauge_p$ function is finite, the solution is guaranteed to be at most $p$-sparse by design.
  3. Computational Tractability: Although the problem is nonconvex and NP-hard, it can be reformulated as a Mixed-Integer Quadratic Program (MIQP), allowing the use of standard solvers for small-to-medium scale problems.

Theoretical Guarantees and the "Critical Angle"

The authors provide rigorous statistical guarantees for the $gauge_p$ machine using a nonconvex version of "dual certificates." They introduce the concept of the "critical angle"—the angle between the signal and the slices of the alphabet. If this angle is sufficiently sharp, the nonconvex machine can achieve exact recovery even with very few measurements.

Theorem 3.20 in the paper establishes a concrete bound on the number of measurements $m$ required for recovery, showing that $m$ scales with the sparsity $p$ and the metric entropy of the alphabet. This provides a theoretical foundation for why the $gauge_p$ machine outperforms convex methods in challenging geometric regimes.

Empirical Evidence

The paper validates the theory using synthetic datasets designed to highlight geometric challenges:

  • Spiral Manifold: Demonstrates how convex hulls fail to capture 1D manifold structures in 2D space.
  • Sparse PCA: Shows superior recovery of sparse, rank-1 "spikes" compared to convex relaxations.
  • Super-resolution: Successfully recovers signals below the diffraction limit where convex machines produce significant errors.

Conclusion

By moving beyond the "geometric blur" of convexity, the $gauge_p$ framework offers a powerful new tool for linear inverse problems. While computational scaling remains a challenge, the ability to provide guaranteed sparsity and tighter geometric fits marks a significant step forward in the study of nonconvex optimization for statistical learning. Future work may involve developing specialized first-order algorithms to handle larger datasets and extending the theory to "blind" inverse problems where the alphabet is unknown.

Summary updated

BibTeX
@misc{eftekhari2021nonconvex,
  author = {Armin Eftekhari and Peyman Mohajerin Esfahani},
  title = {{The Nonconvex Geometry of Linear Inverse Problems}},
  year = {2021},
  eprint = {2101.02776},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.02776},
}
Figure