Multi-Dimensional Sparse Super-Resolution

Clarice Poon, Gabriel Peyré

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

This paper studies sparse super-resolution in arbitrary dimensions. More precisely, it develops a theoretical analysis of support recovery for the so-called beurling least angle regression (BLASSO) method, which is an off-the-grid generalization of ℓ 1 regularization (also known as the least angle regression). While super-resolution is of paramount importance in overcoming the limitations of many imaging devices, its theoretical analysis is still lacking beyond the one-dimensional case. The reason is that in the two-dimensional (2-D) case and beyond, the relative position of the spikes enters the picture, and different geometrical configurations lead to different stability properties. Our first main contribution is a connection, in the limit where the spikes cluster at a given point, between solutions of the dual of the BLASSO problem and the least interpolant space for Hermite polynomial interpolation. This interpolation space, introduced by De Boor, can be computed by Gaussian elimination and lead to an algorithmic description of limiting solutions to the dual problem. With this construction at hand, our second main contribution is a detailed analysis of the support stability and super-resolution effect in the case of a pair of spikes. This includes in particular a sharp analysis of how the signal-to-noise ratio should scale with respect to the separation distance between the spikes. Lastly, numerical simulations on different classes of kernels show the applicability of this theory and highlight the richness of super-resolution in 2-D.

Original languageEnglish
Pages (from-to)1-44
Number of pages44
JournalSiam Journal on Mathematical Analysis
Volume51
Issue number1
Early online date2 Jan 2019
DOIs
Publication statusPublished - 2019

Keywords

  • Convex analysis
  • Image processing
  • Inverse problems
  • Polynomial interpolation
  • Sparsity
  • Super-resolution

ASJC Scopus subject areas

  • Analysis
  • Computational Mathematics
  • Applied Mathematics

Cite this

Multi-Dimensional Sparse Super-Resolution. / Poon, Clarice; Peyré, Gabriel.

In: Siam Journal on Mathematical Analysis, Vol. 51, No. 1, 2019, p. 1-44.

Research output: Contribution to journalArticle

Poon, Clarice ; Peyré, Gabriel. / Multi-Dimensional Sparse Super-Resolution. In: Siam Journal on Mathematical Analysis. 2019 ; Vol. 51, No. 1. pp. 1-44.
@article{31afa4ea2a9a4a7593e360d8ce003faf,
title = "Multi-Dimensional Sparse Super-Resolution",
abstract = "This paper studies sparse super-resolution in arbitrary dimensions. More precisely, it develops a theoretical analysis of support recovery for the so-called beurling least angle regression (BLASSO) method, which is an off-the-grid generalization of ℓ 1 regularization (also known as the least angle regression). While super-resolution is of paramount importance in overcoming the limitations of many imaging devices, its theoretical analysis is still lacking beyond the one-dimensional case. The reason is that in the two-dimensional (2-D) case and beyond, the relative position of the spikes enters the picture, and different geometrical configurations lead to different stability properties. Our first main contribution is a connection, in the limit where the spikes cluster at a given point, between solutions of the dual of the BLASSO problem and the least interpolant space for Hermite polynomial interpolation. This interpolation space, introduced by De Boor, can be computed by Gaussian elimination and lead to an algorithmic description of limiting solutions to the dual problem. With this construction at hand, our second main contribution is a detailed analysis of the support stability and super-resolution effect in the case of a pair of spikes. This includes in particular a sharp analysis of how the signal-to-noise ratio should scale with respect to the separation distance between the spikes. Lastly, numerical simulations on different classes of kernels show the applicability of this theory and highlight the richness of super-resolution in 2-D.",
keywords = "Convex analysis, Image processing, Inverse problems, Polynomial interpolation, Sparsity, Super-resolution",
author = "Clarice Poon and Gabriel Peyr{\'e}",
year = "2019",
doi = "10.1137/17M1147822",
language = "English",
volume = "51",
pages = "1--44",
journal = "Siam Journal on Mathematical Analysis",
issn = "0036-1410",
publisher = "SIAM",
number = "1",

}

TY - JOUR

T1 - Multi-Dimensional Sparse Super-Resolution

AU - Poon, Clarice

AU - Peyré, Gabriel

PY - 2019

Y1 - 2019

N2 - This paper studies sparse super-resolution in arbitrary dimensions. More precisely, it develops a theoretical analysis of support recovery for the so-called beurling least angle regression (BLASSO) method, which is an off-the-grid generalization of ℓ 1 regularization (also known as the least angle regression). While super-resolution is of paramount importance in overcoming the limitations of many imaging devices, its theoretical analysis is still lacking beyond the one-dimensional case. The reason is that in the two-dimensional (2-D) case and beyond, the relative position of the spikes enters the picture, and different geometrical configurations lead to different stability properties. Our first main contribution is a connection, in the limit where the spikes cluster at a given point, between solutions of the dual of the BLASSO problem and the least interpolant space for Hermite polynomial interpolation. This interpolation space, introduced by De Boor, can be computed by Gaussian elimination and lead to an algorithmic description of limiting solutions to the dual problem. With this construction at hand, our second main contribution is a detailed analysis of the support stability and super-resolution effect in the case of a pair of spikes. This includes in particular a sharp analysis of how the signal-to-noise ratio should scale with respect to the separation distance between the spikes. Lastly, numerical simulations on different classes of kernels show the applicability of this theory and highlight the richness of super-resolution in 2-D.

AB - This paper studies sparse super-resolution in arbitrary dimensions. More precisely, it develops a theoretical analysis of support recovery for the so-called beurling least angle regression (BLASSO) method, which is an off-the-grid generalization of ℓ 1 regularization (also known as the least angle regression). While super-resolution is of paramount importance in overcoming the limitations of many imaging devices, its theoretical analysis is still lacking beyond the one-dimensional case. The reason is that in the two-dimensional (2-D) case and beyond, the relative position of the spikes enters the picture, and different geometrical configurations lead to different stability properties. Our first main contribution is a connection, in the limit where the spikes cluster at a given point, between solutions of the dual of the BLASSO problem and the least interpolant space for Hermite polynomial interpolation. This interpolation space, introduced by De Boor, can be computed by Gaussian elimination and lead to an algorithmic description of limiting solutions to the dual problem. With this construction at hand, our second main contribution is a detailed analysis of the support stability and super-resolution effect in the case of a pair of spikes. This includes in particular a sharp analysis of how the signal-to-noise ratio should scale with respect to the separation distance between the spikes. Lastly, numerical simulations on different classes of kernels show the applicability of this theory and highlight the richness of super-resolution in 2-D.

KW - Convex analysis

KW - Image processing

KW - Inverse problems

KW - Polynomial interpolation

KW - Sparsity

KW - Super-resolution

UR - http://www.scopus.com/inward/record.url?scp=85063012493&partnerID=8YFLogxK

U2 - 10.1137/17M1147822

DO - 10.1137/17M1147822

M3 - Article

VL - 51

SP - 1

EP - 44

JO - Siam Journal on Mathematical Analysis

JF - Siam Journal on Mathematical Analysis

SN - 0036-1410

IS - 1

ER -