TY - JOUR

T1 - Computational complexity versus statistical performance on sparse recovery problems

AU - Roulet, Vincent

AU - Boumal, Nicolas

AU - D'Aspremont, Alexandre

N1 - Funding Information:
European Research Council (project SIPA); AMX fellowship; National Science Foundation (DMS-1719558); Fonds AXA pour la Recherche and a Google Focused Award.
Publisher Copyright:
© 2019 The Author(s).

PY - 2020/3/1

Y1 - 2020/3/1

N2 - 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 programmes, 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.

AB - 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 programmes, 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.

KW - Error bounds

KW - Renegar's condition number

KW - Restart

KW - Sharpness

KW - Sparse recovery

UR - http://www.scopus.com/inward/record.url?scp=85084929176&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85084929176&partnerID=8YFLogxK

U2 - 10.1093/imaiai/iay020

DO - 10.1093/imaiai/iay020

M3 - Article

AN - SCOPUS:85084929176

VL - 9

SP - 1

EP - 32

JO - Information and Inference

JF - Information and Inference

SN - 2049-8772

IS - 1

ER -