Support Localization and the Fisher Metric for off-the-grid Sparse Regularization

Clarice Poon, Nicolas Keriven, Gabriel Peyré

Abstract

Sparse regularization is a central technique for both machine learning—enabling supervised feature selection and unsupervised mixture learning—and imaging sciences, where it facilitates super-resolution. This paper provides a theoretical breakthrough for "off-the-grid" sparse recovery by proving that the Fisher-Rao distance, rather than the standard Euclidean distance, is the natural metric for defining the separation between signal spikes. By utilizing this geometry-aware metric, the authors provide the first rigorous support recovery guarantees for complex, non-translation-invariant problems such as Laplace transform inversion and Gaussian Mixture Model (GMM) estimation.

Introduction

In fields ranging from super-resolution microscopy to unsupervised machine learning, researchers often seek to recover a sparse set of continuous parameters from a limited number of noisy, randomized observations. This is known as "off-the-grid" sparse recovery, as the parameters (or "spikes") reside in a continuous space rather than on a predefined discrete grid.

To guarantee that algorithms like the Beurling-LASSO (BLASSO)—the infinite-dimensional, continuous analogue of the $L_1$ LASSO—can successfully recover these spikes, theoretical proofs typically require a "minimum separation condition." This condition stipulates that the underlying spikes must not be too close to one another. Historically, this separation has been measured using standard Euclidean distance. However, Euclidean distance is an ad-hoc choice that ignores the underlying geometry of the measurement process. While sufficient for translation-invariant problems (such as standard Fourier measurements), it yields sub-optimal or even meaningless results for spatially varying operators, such as data-dependent kernels or the Laplace transform.

Methodology: The Fisher-Rao Geometry

The authors analyze the BLASSO optimization problem through the framework of dual certificates. To overcome the limitations of Euclidean distance, they introduce the Fisher Information Matrix (FIM) associated with the measurement features to define a Riemannian metric on the parameter space.

This approach induces the Fisher-Rao geodesic distance, which is invariant to how the parameter space is parameterized. This invariance is crucial because it aligns the metric with the mathematical structure of the BLASSO problem itself. The authors define a new class of "admissible kernels" based on this Fisher metric and construct a mathematical proxy known as a "limit precertificate." By applying the Implicit Function Theorem, they prove that if the true spikes are separated by a sufficient Fisher-Rao distance, the BLASSO will stably recover the exact number of spikes, even in the presence of sub-sampled measurements and noise.

Key Insights and Theoretical Results

Geometry-Aware Recovery

The primary insight of this work is that the Fisher-Rao distance naturally captures the geometry of the sparse recovery problem. For translation-invariant kernels (like Fourier), the Fisher metric simplifies to a scaled Euclidean metric, explaining why previous Euclidean-based proofs were successful in those specific cases. However, for non-translation-invariant kernels—where the metric tensor varies across the space—the Fisher metric provides the first meaningful way to guarantee sparse recovery.

Support Stability and Sample Complexity

The authors establish several key theoretical bounds:

  • Support Stability: Theorem 1 proves that if the underlying spikes are separated by a minimum Fisher-Rao distance, the BLASSO uniquely recovers exactly $s$ spikes.
  • Sample Complexity: To achieve recovery with high probability, the number of random measurements $m$ must scale linearly with the number of spikes ($m = \mathcal{O}(s \log(\dots))$), assuming the amplitudes have random signs (a Steinhaus sequence). If the signs are arbitrary, the requirement is $m = \mathcal{O}(s^{3/2} \log(\dots))$.
  • Noise Tolerance: The recovery remains robust to noise levels up to $\mathcal{O}(1/s)$.

Non-Asymptotic GMM Model Selection

When applied to learning Gaussian Mixture Models (GMMs), the BLASSO yields exactly the right number of components (support stability) with a sample complexity that is polynomial in the number of spikes ($s$) and dimensions ($d$). This represents a rare, non-asymptotic guarantee for model selection, contrasting with classical likelihood methods that typically only guarantee the correct number of components as the number of samples approaches infinity.

Applications

The authors successfully derive quantitative bounds for sample complexity and noise tolerance across several domains:

  1. Discrete Fourier Sampling: Multi-dimensional recovery from sub-sampled Fourier data.
  2. Continuous Gaussian Fourier Sampling: Relevant for GMMs and signal processing.
  3. Laplace Sampling: Providing a theoretical foundation for the notoriously difficult problem of Laplace transform inversion.

Limitations and Future Directions

While this work marks a significant advancement, several open questions remain. The optimal sample complexity of $\mathcal{O}(s)$ currently relies on the assumption of random signs for spike amplitudes; removing this requirement for arbitrary signs remains a challenge. Additionally, the GMM results assume a known and shared covariance matrix among components. Extending this to unknown or varying covariances is difficult, as the Fisher metric in those cases lacks a closed-form expression. Finally, while 1D research suggests that the separation condition might be unnecessary for purely positive spikes, extending "separation-free" recovery to multi-dimensional spaces using the Fisher metric is a promising area for future study.

Summary updated

Abstract

Sparse regularization is a central technique for both machine learning (to achieve supervised features selection or unsupervised mixture learning) and imaging sciences (to achieve super-resolution)...
BibTeX
@inproceedings{poon2019support,
  author = {Clarice Poon and Nicolas Keriven and Gabriel Peyré},
  title = {{Support Localization and the Fisher Metric for off-the-grid Sparse Regularization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=oeUjuPEzvpS},
}
Figure