Mathematical Complexity of Sparse Solvers

Question

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. — Christian Clason, Feb 13, 2016 at 9:51

Tolga Birdal · Accepted Answer · 2016-02-13 14:59:27Z

4

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

answered Feb 13, 2016 at 12:56

Tolga Birdal

2,14911 silver badges23 bronze badges

$\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$
– Christian Clason
Feb 13, 2016 at 13:26
$\begingroup$ You're right. Updated. $\endgroup$
– Tolga Birdal
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$
– Christian Clason
Feb 13, 2016 at 16:32

Add a comment |

1 Answer 1