The geometry of off-the-grid compressed sensing

Clarice Poon, Nicolas Keriven, Gabriel Peyré

Research output: Contribution to journalArticle

6 Citations (SciVal)
110 Downloads (Pure)

Abstract

Compressed sensing (CS) ensures the recovery of sparse vectors from a number of randomized measurements proportional to their sparsity. The initial theory considers discretized domains, and the randomness makes the physical positions of the grid nodes irrelevant. Most imaging devices, however, operate over some continuous physical domain, and it makes sense to consider Dirac masses with arbitrary positions. In this article, we consider such a continuous setup and analyze the performance of the BLASSO algorithm, which is the continuous extension of the celebrated LASSO ℓ 1 regularization method. This approach is appealing from a numerical perspective because it avoids to discretize the domain of interest. Previous works considered translation-invariant measurements, such as randomized Fourier coefficients, in which it makes clear that the discrete theory should be extended by imposing a minimum distance separation constraint (often called “Rayleigh limit”) between the Diracs. These prior works, however, rule out many domains and sensing operators of interest, which are not translation invariant. This includes, for instance, Laplace measurements over the positive reals and Gaussian mixture models over the mean-covariance space. Our theoretical advances crucially rely on the introduction of a canonical metric associated with the measurement operator, which is the so-called Fisher geodesic distance. In the case of Fourier measurements, one recovers the Euclidean metric, but this metric can cope with arbitrary (possibly non-translation invariant) domains. Furthermore, it is naturally invariant under joint reparameterization of both the sensing operator and the Dirac locations. Our second and main contribution shows that if the Fisher distance between spikes is larger than a Rayleigh separation constant, then the BLASSO recovers in a stable way a stream of Diracs, provided that the number of measurements is proportional (up to log factors) to the number of Diracs. We measure the stability using an optimal transport distance constructed on top of the Fisher geodesic distance. Our result is (up to log factor) sharp and does not require any randomness assumption on the amplitudes of the underlying measure. Our proof technique relies on an infinite-dimensional extension of the so-called golfing scheme which operates over the space of measures and is of general interest.

Original languageEnglish
Pages (from-to)241-327
JournalFoundations of Computational Mathematics
Volume23
Early online date22 Oct 2021
DOIs
Publication statusPublished - 28 Feb 2023

Bibliographical note

Funding Information:
The work of Gabriel Peyré was supported by the ERC project NORIA and by the French government under management of Agence Nationale de la Recherche as part of the “Investissements d’avenir” program, reference ANR19-P3IA-0001 (PRAIRIE 3IA Institute).

Keywords

  • BLASSO
  • Compressed sensing
  • Fisher distance
  • LASSO
  • Off the grid
  • Wasserstein distance

ASJC Scopus subject areas

  • Analysis
  • Computational Mathematics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'The geometry of off-the-grid compressed sensing'. Together they form a unique fingerprint.

Cite this