Computational Complexity versus Statistical Performance on Sparse Recovery Problems

Vincent Roulet, Nicolas Boumal, Alexandre d'Aspremont

We show that several classical quantities controlling compressed sensing performance directly match classical parameters controlling algorithmic complexity. We first describe linea…