Computational complexity versus statistical performance on sparse recovery problems

DOI10.1093/imaiai/iay020zbMath1470.94056arXiv1506.03295OpenAlexW2962784818MaRDI QIDQ5006513

Alexandre d'Aspremont, Nicolas Boumal, 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 boundssharpnesssparse recoveryrestartRenegar's condition number

Mathematics Subject Classification ID

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

Related Items (5)

WARPd: A Linearly Convergent First-Order Primal-Dual Algorithm for Inverse Problems with Approximate Sharpness Conditions ⋮ NESTANets: stable, accurate and efficient neural networks for analysis-sparse inverse problems ⋮ Near-Optimal Bounds for Phase Synchronization ⋮ Sharpness, Restart, and Acceleration ⋮ Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation

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