MultiDimensional Sparse Super-Resolution

DOI10.1137/17M1147822zbMATH Open1456.94009arXiv1709.03157OpenAlexW2963169856MaRDI QIDQ4646932FDOQ4646932

Authors: Clarice Poon, Gabriel Peyré 

Publication date: 3 January 2019

Published in: SIAM Journal on Mathematical Analysis (Search for Journal in Brave)

Abstract: This paper studies sparse super-resolution in arbitrary dimensions. More precisely, it develops a theoretical analysis of support recovery for the so-called BLASSO method, which is an off-the-grid generalisation of l1 regularization (also known as the LASSO). While super-resolution is of paramount importance in overcoming the limitations of many imaging devices, its theoretical analysis is still lacking beyond the 1-dimensional (1-D) case. The reason is that in the 2-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 Hermite polynomial interpolation ideals. Polynomial bases for these ideals, 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.

Full work available at URL: https://arxiv.org/abs/1709.03157

Recommendations

• Image Super-Resolution Via Sparse Representation
• Superresolution via Sparsity Constraints
• Super-Resolution With Sparse Mixing Estimators
• Image Super-Resolution Based on Structure-Modulated Sparse Representation
• Multivariate super-resolution without separation
• Sparse non-negative super-resolution -- simplified and stabilised

zbMATH Keywords

sparsityconvex analysisinverse problemsimage processingpolynomial interpolationsuper-resolution

Mathematics Subject Classification ID

Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Numerical methods for inverse problems for integral equations (65R32)

Cites Work

• Title not available (Why is that?)
• Matching pursuits with time-frequency dictionaries
• Title not available (Why is that?)
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• Title not available (Why is that?)
• Computational Aspects of Polynomial Interpolation in Several Variables
• Matrix pencil method for estimating parameters of exponentially damped/undamped sinusoids in noise
• Title not available (Why is that?)
• On multivariate polynomial interpolation
• Atomic decomposition by basis pursuit
• Cadzow denoising upgraded: a new projection method for the recovery of Dirac pulses from noisy linear measurements
• Signal enhancement-a composite property mapping algorithm
• Superresolution via Sparsity Constraints
• Super-resolution from noisy data
• Towards a Mathematical Theory of Super‐resolution
• Spike detection from inaccurate samplings
• Exact reconstruction using Beurling minimal extrapolation
• Atomic Norm Denoising With Applications to Line Spectral Estimation
• Robust Recovery of Positive Stream of Pulses
• Exact support recovery for sparse spikes deconvolution
• MUSIC for single-snapshot spectral estimation: stability and super-resolution
• Multivariate Hermite interpolation by algebraic polynomials: A survey
• Super-resolution of positive sources: the discrete setup
• Statistical and Information-Theoretic Analysis of Resolution in Imaging
• Support recovery for sparse super-resolution of positive measures
• Linear Inversion of Band-Limited Reflection Seismograms
• Almost-sure identifiability of multidimensional harmonic retrieval
• Polynomial interpolation in several variables: lattices, differences, and ideals
• The least solution for the polynomial interpolation problem
• Performance of high resolution frequencies estimation methods compared to the Cramer-Rao bounds
• Exact Solutions to Super Resolution on Semi-Algebraic Domains in Higher Dimensions
• Prony's method in several variables
• A multivariate generalization of Prony's method
• Inverse problems in spaces of measures
• Super-resolution, extremal functions and the condition number of Vandermonde matrices
• The alternating descent conditional gradient method for sparse inverse problems
• Sparse regularization on thin grids. I: The \textsc{Lasso}.
• A Geometrical Study of Matching Pursuit Parametrization
• ESPRIT for Multidimensional General Grids

Cited In (29)

• Sparsest piecewise-linear regression of one-dimensional data
• Super-resolution by means of Beurling minimal extrapolation
• Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?
• Multi-kernel unmixing and super-resolution using the modified matrix pencil method
• The sliding Frank-Wolfe algorithm and its application to super-resolution microscopy
• Gridless super-resolution sparse recovery for non-sidelooking STAP using reweighted atomic norm minimization
• On the uniqueness of solutions for the basis pursuit in the continuum
• Short Communication: Weak Sparse Superresolution is Well-Conditioned
• Sparse spikes super-resolution on thin grids II: the continuous basis pursuit
• Multivariate super-resolution without separation
• When does OMP achieve exact recovery with continuous dictionaries?
• Point source super-resolution via non-convex \(L_1\) based methods
• A mathematical theory of super-resolution and two-point resolution
• A mathematical theory of computational resolution limit in multi-dimensional spaces
• Exact recovery of the support of piecewise constant images via total variation regularization
• Support recovery for sparse super-resolution of positive measures
• Improved resolution estimate for the two-dimensional super-resolution and a new algorithm for direction of arrival estimation with uniform rectangular array
• Approximation and interpolation of singular measures by trigonometric polynomials
• Multidimensional unstructured sparse recovery via eigenmatrix
• Mathematical foundation of sparsity-based multi-snapshot spectral estimation
• The geometry of off-the-grid compressed sensing
• Sparse non-negative super-resolution -- simplified and stabilised
• Matrix Structures and Parallel Algorithms for Image Superresolution Reconstruction
• Context-Aware Sparse Decomposition for Image Denoising and Super-Resolution
• A super-resolution framework for tensor decomposition
• Convergence rates of forward-Douglas-Rachford splitting method
• A sampling theorem for deconvolution in two dimensions
• A unifying representer theorem for inverse problems and machine learning
• Superresolution via Sparsity Constraints

Uses Software

• PDCO

This page was built for publication: MultiDimensional Sparse Super-Resolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4646932)