On the uniqueness of solutions for the basis pursuit in the continuum

DOI10.1088/1361-6420/AC9998zbMATH Open1504.94031arXiv2009.11855OpenAlexW4292162877MaRDI QIDQ5044980FDOQ5044980

Authors: Thomas Debarre, Quentin Denoyelle, Julien Fageot 

Publication date: 3 November 2022

Published in: Inverse Problems (Search for Journal in Brave)

Abstract: This paper studies the continuous-domain inverse problem of recovering Radon measures on the one-dimensional torus from low-frequency Fourier coefficients, where Kc is the cutoff frequency. Our approach consists in minimizing the total-variation norm among all Radon measures that are consistent with the observations. We call this problem the basis pursuit in the continuum (BPC). We characterize the solution set of (BPC) in terms of uniqueness and describe its sparse solutions which are sums of few signed Dirac masses. The characterization is determined by the spectrum of a Toeplitz and Hermitian-symmetric matrix that solely depends on the observations. More precisely, we prove that (BPC) has a unique solution if and only if this matrix is neither positive definite nor negative definite. If it has both a positive and negative eigenvalue, then the unique solution is the sum of at most 2Kc Dirac masses, with at least one positive and one negative weight. If this matrix is positive (respectively negative) semi-definite and rank deficient, then the unique solution is composed of a number of Dirac masses equal to the rank of the matrix, all of which have nonnegative (respectively nonpositive) weights. Finally, in cases where (BPC) has multiple solutions, we demonstrate that there are infinitely many solutions composed of Kc+1 Dirac masses, with nonnegative (respectively nonpositive) weights if the matrix is positive (respectively negative) definite.

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

Recommendations

• On the uniqueness of solutions to continuity equations
• On uniqueness guarantees of solution in convex regularized linear inverse problems
• On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery
• Unique continuation for solutions of \(p(x)\)-Laplacian equations
• scientific article; zbMATH DE number 825865
• On the uniqueness of continuous solutions of functional equations
• scientific article; zbMATH DE number 865589
• An alternative approach to the uniqueness of unconditional basis of \(\ell _p(c_{0})\) for \(0<p<1\)
• On the unique minimal monomial basis of Birkhoff interpolation problem
• Continuity of the null space basis and constrained optimization

zbMATH Keywords

uniquenesstotal variation normbasis pursuitdual certificatesPisarenko decomposition

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Radon transform (44A12) Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• The ML–EM algorithm in continuum: sparse measure solutions
• Nonlinear total variation based noise removal algorithms
• Title not available (Why is that?)
• TV-based reconstruction of periodic functions
• Convergence of a block coordinate descent method for nondifferentiable minimization
• A new approach to variable selection in least squares problems
• The Lasso problem and uniqueness
• Sparse and redundant representations. From theory to applications in signal and image processing.
• Compressed sensing
• Signal Recovery by Proximal Forward-Backward Splitting
• A mathematical introduction to compressive sensing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A semidefinite programming approach to the generalized problem of moments
• Atomic decomposition by basis pursuit
• Super-resolution from noisy data
• Prony methods for recovery of structured functions
• Towards a Mathematical Theory of Super‐resolution
• Title not available (Why is that?)
• Spike detection from inaccurate samplings
• Exact reconstruction using Beurling minimal extrapolation
• Super-resolution of point sources via convex programming
• Sampling signals with finite rate of innovation
• Exact support recovery for sparse spikes deconvolution
• Title not available (Why is that?)
• MultiDimensional Sparse Super-Resolution
• Exact Solutions to Super Resolution on Semi-Algebraic Domains in Higher Dimensions
• The generalized Lasso problem and uniqueness
• Inverse problems in spaces of measures
• The alternating descent conditional gradient method for sparse inverse problems
• The shaping of the Riesz representation theorem: A chapter in the history of analysis
• The sliding Frank-Wolfe algorithm and its application to super-resolution microscopy
• Sparse regularization on thin grids. I: The \textsc{Lasso}.
• Spline solutions to L\(^1\) extremal problems in one and several variables
• Stable super-resolution of images: theoretical study
• Sparsest piecewise-linear regression of one-dimensional data
• Splines are universal solutions of linear inverse problems with generalized TV regularization
• Functional penalised basis pursuit on spheres
• Representer Theorems for Sparsity-Promoting <inline-formula> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math> </inline-formula> Regularization
• On the linear convergence rates of exchange and continuous methods for total variation minimization
• Sparse non-negative super-resolution -- simplified and stabilised
• Sparse spikes super-resolution on thin grids II: the continuous basis pursuit
• Sparse optimization on measures with over-parameterized gradient descent
• A fast homotopy algorithm for gridless sparse recovery
• When does OMP achieve exact recovery with continuous dictionaries?
• Towards Generalized FRI Sampling With an Application to Source Resolution in Radioastronomy

Cited In (3)

• TV-based spline reconstruction with Fourier measurements: uniqueness and convergence of grid-based methods
• Analysis of basis pursuit via capacity sets
• Linear inverse problems with nonnegativity constraints: singularity of optimisers

Uses Software

• PDCO

This page was built for publication: On the uniqueness of solutions for the basis pursuit in the continuum

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