View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
CoSaMP and OMP for sparse recovery

Join the 15-year community celebration.

Play games and win prizes!

» Learn more

4.22222
4.2 | 9 ratings Rate this file 85 Downloads (last 30 days) File Size: 10.7 KB File ID: #32402 Version: 1.7
image thumbnail

CoSaMP and OMP for sparse recovery

by

Stephen Becker (view profile)

 

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)
MATLAB Search Path
/
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (21)
31 Aug 2016 VMat

VMat (view profile)

Thanks Stephen. Testing some cs greedy techniques, ideally I wish to plot the input signal and the reconstructed one: could you please tell what is the input signal variable in OMP.m and CoSaMP.m codes ?

Comment only
13 Aug 2016 mpvae

mpvae (view profile)

good. thank you for sharing

05 Aug 2016 Stephen Becker

Stephen Becker (view profile)

Thanks for noticing the bug Pham. I've updated the code.
Regards,
Stephen

Comment only
05 Aug 2016 Pham Dang

Dear M. Becker,
I suspect a small mistake at line 65 of test_OMP_and_CoSaMP.m. The line is :
z = sigma*randn(M,1); if COMPLEX, z = (z + sigma*randn(M,1))/sqrt(2); end

Should not it be :
z = sigma*randn(M,1); if COMPLEX, z = (z + i1*sigma*randn(M,1))/sqrt(2); end

in order to get a complex value for z ?
Best regards

Comment only
22 Jan 2016 Joo

Joo (view profile)

how can i use this code with images and get the output does any one know

30 Dec 2014 fatemeh nj

I just have a bit problem, I receive this warning and my audio signal has not been recovered well, my warning is:
Warning: did not reach target size of residual

I also increase the number of 'K' but at the end the error was repeated!

my first question is that I know the k determined sparsity but how can i know the sparsity of unknown signal?

second question, could you also mention which paper you use for writing omp function?

Comment only
05 May 2014 Yang

Yang (view profile)

Thanks for this source code

09 Apr 2014 TDJIO

TDJIO (view profile)

Thanks for sharing!

08 Apr 2014 sheng

sheng (view profile)

Thank you very much for your share.

06 Sep 2013 Jason

Jason (view profile)

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

Comment only
06 Sep 2013 Jason

Jason (view profile)

 
23 Jul 2013 Stephen Becker

Stephen Becker (view profile)

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

Comment only
23 Jul 2013 israa tawfic

can i use this source code with an image,

08 Jun 2013 Stephen Becker

Stephen Becker (view profile)

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.

Comment only
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

Bo (view profile)

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

Comment only
16 Apr 2013 Bo

Bo (view profile)

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

Stephen Becker (view profile)

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.

Comment only
12 Dec 2012 sasikala mr

thanks

Comment only
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!

Comment only
20 Mar 2012 Arunima c.v.

HELPFUL

Comment only
Updates
07 Oct 2011 1.1

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

21 Mar 2012 1.2

editing description text a bit

20 Apr 2012 1.3

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 1.6

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

05 Aug 2016 1.7

Fixed bug with complex numbers (Aug 2016)

Contact us