The basins of attraction of the global minimizers of the non-convex sparse spike estimation problem

DOI10.1088/1361-6420/AB5AA3zbMATH Open1468.94026arXiv1811.12000OpenAlexW2990604797MaRDI QIDQ5000576FDOQ5000576

Authors: Yann Traonmilin, Jean-François Aujol 

Publication date: 14 July 2021

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

Abstract: The sparse spike estimation problem consists in estimating a number of off-the-grid impulsive sources from under-determined linear measurements. Information theoretic results ensure that the minimization of a non-convex functional is able to recover the spikes for adequately chosen measurements (deterministic or random). To solve this problem, methods inspired from the case of finite dimensional sparse estimation where a convex program is used have been proposed. Also greedy heuristics have shown nice practical results. However, little is known on the ideal non-convex minimization method. In this article, we study the shape of the global minimum of this non-convex functional: we give an explicit basin of attraction of the global minimum that shows that the non-convex problem becomes easier as the number of measurements grows. This has important consequences for methods involving descent algorithms (such as the greedy heuristic) and it gives insights for potential improvements of such descent methods.

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

Recommendations

• The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension
• An unbiased approach to compressed sensing
• Stability of the minimizers of least squares with a non-convex regularization. II: Global behavior
• A general theory of concave regularization for high-dimensional sparse estimation problems
• Minimization of non-smooth, non-convex functionals by iterative thresholding

zbMATH Keywords

non-convex optimizationsuper-resolutionsparse spikes

Mathematics Subject Classification ID

Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Numerical methods for mathematical programming, optimization and variational techniques (65K99)

Cites Work

• Convex analysis and monotone operator theory in Hilbert spaces
• Hilbert space embeddings and metrics on probability measures
• Super-resolution from noisy data
• Towards a Mathematical Theory of Super‐resolution
• Title not available (Why is that?)
• Atomic Norm Denoising With Applications to Line Spectral Estimation
• Compressed Sensing Off the Grid
• Exact support recovery for sparse spikes deconvolution
• Sampling and Reconstructing Signals From a Union of Linear Subspaces
• Exact Solutions to Super Resolution on Semi-Algebraic Domains in Higher Dimensions
• Fundamental Performance Limits for Ideal Decoders in High-Dimensional Linear Inverse Problems
• Inexact Gradient Projection and Fast Data Driven Compressed Sensing
• Sketching for large-scale learning of mixture models
• Sparse regularization on thin grids I: the Lasso
• Phase Retrieval With Random Gaussian Sensing Vectors by Alternating Projections
• Regularized gradient descent: a non-convex recipe for fast joint blind deconvolution and demixing
• Adapting to unknown noise level in sparse deconvolution
• Sparse spikes super-resolution on thin grids II: the continuous basis pursuit
• Through the haze: a non-convex approach to blind gain calibration for linear random sensing models

Cited In (9)

• Estimation of off-the grid sparse spikes with over-parametrized projected gradient descent: theory and application
• Sketched learning for image denoising
• On strong basins of attractions for non-convex sparse spike estimation: upper and lower bounds
• The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension
• Initialization of metaheuristics: comprehensive review, critical analysis, and research directions
• On the linear convergence rates of exchange and continuous methods for total variation minimization
• Title not available (Why is that?)
• A theory of optimal convex regularization for low-dimensional recovery
• Sparse optimization on measures with over-parameterized gradient descent

This page was built for publication: The basins of attraction of the global minimizers of the non-convex sparse spike estimation problem

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