# Mathematical Complexity of Sparse Solvers

For a system $\mathbf{x=Da}$, there exist a lot of algorithms to estimate sparse vector $\mathbf{a}$.

I wish to know the big-O mathematical complexity of

1) orthogonal matching pursuit (OMP) both with fixed sparsity and error tolerance criteria.

2) L1-magic (which is based on interior point methods) algorithms.

This paper and this one give a good overview of the complexity of different methods.

I find the feature sign search algorithm to be very fast, robust and useful. You could check it here, along with the paper :

Efficient sparse coding algorithms

Honglak Lee, Alexis Battle, Rajat Raina, and Andrew Y. Ng.

NIPS 2006

• I'm sorry, but that doesn't answer the question at all (unless that paper contains a comparison of the complexity of their algorithm with the two the OP is asking about, in which case please include the relevant information in your answer). – Christian Clason Feb 13 '16 at 13:26
• You're right. Updated. – Tolga Birdal Feb 13 '16 at 14:59
• Thanks! Extra points for a) giving a full citation for these papers in case the links go away at some point and b) including the big-O complexities given in the paper in the answer as well. – Christian Clason Feb 13 '16 at 16:32