Renegar's Condition Number and Compressed Sensing Performance

Vincent Roulet (1, 2) , Nicolas Boumal (2, 1) , Alexandre d'Aspremont (1, 2)

1 LIENS - Laboratoire d'informatique de l'école normale supérieure
2 SIERRA - Statistical Machine Learning and Parsimony

Renegar's condition number is a data-driven computational complexity measure for convex programs, generalizing classical condition numbers in linear systems. We provide evidence 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 eigenvalue of the observation matrix, which controls compressed sensing performance. This means that, in these problems, a single parameter directly controls computational complexity and recovery performance.

Domaines: Recherche opérationnelle [math.OC]; Intelligence artificielle [cs.AI]; Machine Learning [stat.ML]

Vincent Roulet, Nicolas Boumal, Alexandre d'Aspremont. Renegar's Condition Number and Compressed Sensing Performance. 2015. ⟨hal-01239310⟩