# 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.

• Have you tried your own literature search first? Google gave as a first result for 1) the paper infoscience.epfl.ch/record/131255/files/LocOMP.pdf For 2) some information can be found in citeseerx.ist.psu.edu/viewdoc/…, but complexity for iterative methods is a difficult issue because you'd need to estimate the number of iterations, which depends on a lot of factors. Feb 13 '16 at 9:51

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). Feb 13 '16 at 13:26
• You're right. Updated. 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. Feb 13 '16 at 16:32