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.


1 Answer 1


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

  • $\begingroup$ 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). $\endgroup$ Feb 13, 2016 at 13:26
  • $\begingroup$ You're right. Updated. $\endgroup$ Feb 13, 2016 at 14:59
  • $\begingroup$ 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. $\endgroup$ Feb 13, 2016 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.