Computational complexity versus statistical performance on sparse recovery problems

DOI10.1093/IMAIAI/IAY020MaRDI QIDQ5006513zbMATH OpenOpenAlexFDO

Authors Nicolas Boumal, Alexandre d'Aspremont, Vincent Roulet

Publication date 16 August 2021

Published in Information and Inference: A Journal of the IMA (Search for Journal in Brave)

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

zbMATH Keywords

error boundsRenegar's condition numberrestartsharpnesssparse recovery

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Numerical optimization and variational techniques (65K10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We show that several classical quantities controlling compressed sensing performance directly match classical parameters controlling algorithmic complexity. We first describe linearly convergent restart schemes on first-order methods solving a broad range of compressed sensing problems, where sharpness at the optimum controls convergence speed. We show that for sparse recovery problems, this sharpness can be written as a condition number, given by the ratio between true signal sparsity and the largest signal size that can be recovered by the observation matrix. In a similar vein, Renegar's condition number is a data-driven complexity measure for convex programs, generalizing classical condition numbers for linear systems. We show that for a broad class of compressed sensing problems, the worst case value of this algorithmic complexity measure taken over all signals matches the restricted singular value of the observation matrix which controls robust recovery performance. Overall, this means in both cases that, in compressed sensing problems, a single parameter directly controls both computational complexity and recovery performance. Numerical experiments illustrate these points using several classical algorithms.

Recommendations

• An introduction to compressed sensing
• scientific article; zbMATH DE number 6312913
• A numerical exploration of compressed sampling recovery
• Simple bounds for recovering low-complexity models
• The restricted isometry property and its implications for compressed sensing

Cited in

(10)

• Analysis of sparse recovery algorithms via the replica method
• NESTANets: stable, accurate and efficient neural networks for analysis-sparse inverse problems
• Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation
• Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
• Computable Performance Bounds on Sparse Recovery
• Near-optimal bounds for phase synchronization
• WARPd: a linearly convergent first-order primal-dual algorithm for inverse problems with approximate sharpness conditions
• Sharpness, restart, and acceleration
• Critical point theory for sparse recovery
• Restarts subject to approximate sharpness: a parameter-free and optimal scheme for first-order methods

This page was built for publication: Computational complexity versus statistical performance on sparse recovery problems

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