4.42857

4.4 | 7 ratings Rate this file 164 Downloads (last 30 days) File Size: 10.8 KB File ID: #32402
image thumbnail

CoSaMP and OMP for sparse recovery

by

 

01 Aug 2011 (Updated )

Orthogonal Matching Pursuit (OMP) and Compressive Sampling Matched Pursuit (CoSaMP).

| Watch this File

File Information
Description

Orthogonal matching Pursuit (OMP) and Compressive Sampling Matched Pursuit (CoSaMP) algorithm (see Needell and Tropp's 2008 paper http://arxiv.org/abs/0803.2392 ). This implementation allows several variants, and it also allows you to specify a matrix via function handles (useful if your matrix represents an FFT or similar).

A demo code shows how to use both the OMP.m and CoSaMP.m functions.

OMP and CoSaMP are useful for sparse recovery problems; in particular, they can be used for compressed sensing (aka compressive sampling), image denoising and deblurring, seismic tomography problems, MRI, etc.

Another good OMP implementation (C++, Matlab) is here:
http://www.di.ens.fr/willow/SPAMS/
(Updated, March 2012: SPAMS now has python and R bindings as well)

And a CoSaMP implementation (I haven't tested):
http://media.aau.dk/null_space_pursuits/2011/07/a-few-corrections-to-cosamp-and-sp-matlab.html
Edit: that CoSaMP implementation mentioned above is buggy. Read this:
http://media.aau.dk/null_space_pursuits/2011/08/cosamp-and-cosaomp.html

Update, Feb 2012: for a blog discussion of several way to implement CoSaMP, see this website:
http://media.aau.dk/null_space_pursuits/2012/02/speedups-in-omp-implementations.html

Acknowledgements

Toolbox Sparse Optmization, Greedy Algorithms Promoting Group Sparsity, and Orthogonal Least Squares Algorithms For Sparse Signal Reconstruction inspired this file.

Required Products MATLAB
MATLAB release MATLAB 7.10 (R2010a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (15)
05 May 2014 Yang

Thanks for this source code

09 Apr 2014 TDJIO

Thanks for sharing!

08 Apr 2014 sheng

Thank you very much for your share.

06 Sep 2013 Jason

How to estimate sparsity?

Works great if I know the sparse size exactly (by creating test data, for example), otherwise not such a great improvement over least squares (for my particular problem).

06 Sep 2013 Jason  
23 Jul 2013 Stephen Becker

Israa, I'm not exactly sure what you want to do, but if you wish to work with 2D images, then use vectorize (e.g. use vec = @(x) x(:) ) and reshape operators, so that the code only sees vectors. If done right, it will work just fine. Hope that helps a bit.
-Stephen

23 Jul 2013 israa tawfic

can i use this source code with an image,

08 Jun 2013 Stephen Becker

Robin, that's a typo. It's an unimportant default value that doesn't affect the code, so I will change it the next time I have a major update.

07 Jun 2013 Robin Longstride

Why do you use round with 2 nargin in CoSaMP line 97?

It doesn't work.

Thanks for this source code.

17 Apr 2013 Bo

Hi,
I just get it work.
Sorry for the 4 stars. It should be a five stars.
Thank you,
Bo Yuan

16 Apr 2013 Bo

Hi Stephan,

It seems your functions can only accept A which is square matrix? Do I miss anything or this function will not work for overcomplete frames?

Thank you!
Bo Yuan

12 Dec 2012 Stephen Becker

good catch Noam! I'm updating the fixed code. The new version also displays some more information for CoSaMP when using function handles and using LSQR.

12 Dec 2012 sasikala mr

thanks

14 Aug 2012 Noam Wagner

Hi Stephan,
Thank you very much for the very nice and useful OMP code.
I believe there might be a mistake in the orthogonalization loop of "atom_new", when working in fast mode. I think the equation:

atom_new = atom_new - (atom_new'*A_T(:,j))*A_T(:,j);

should be modified to:

atom_new = atom_new - (A_T(:,j)'*atom_new)*A_T(:,j);

This turns out significant when working with complex numbers. Otherwise, one may notice different behavior in slow and fast modes.
Thanks again!

20 Mar 2012 Arunima c.v.

HELPFUL

Updates
07 Oct 2011

Adding new links in the description, and updated the demo file slightly.

21 Mar 2012

editing description text a bit

20 Apr 2012

Fixing a bug that affected versions of Matlab prior to 2009b. See http://blogs.mathworks.com/loren/2009/09/11/matlab-release-2009b-best-new-feature-or/

12 Dec 2012

Fixing the bug for complex mode. Minor changes to the solvers. Added complex data test mode to the test script.

Contact us