Monday, April 07, 2008

Monday Morning Algorithm 14: A Comparison of the Reconstruction Capability of CoSaMP, OMP, Subspace Pursuit and Reweighted Lp in Compressive Sensing

Today's Monday Morning Algorithm is provided by David Mary a reader of this blog. David was interested in checking the reconstruction efficiency of different algorithms used in Compressed Sensing / Compressive Sensing (If you want to know more about Compressed Sensing check the Big Picture out). So he implemented several reconstruction algorithms and wrote a script (scripttf2dcosamp.m) that shows their capabilities with regards to the initial sparsity of the signal. It includes the following implementations:


The original signal is an image. It features pixels of various intensities laying on a dark background (think of stars at night). It is obviously sparse in the direct/image space.

The measurement matrix is a 2D Random Partial Fourier Transform.

The goal is to find a sparse approximation of u_true knowing that b=phi*u_true (+ noise)
  • b: obs vector,
  • phi : CS matrix,
  • u_true : target object

To see the results, download this zip file in a folder, then enter scripttf2dcosamp at the prompt. You should see something like this.

Pretty neat, uh ? Thank you David for sharing this. I will eventually put each of these implementations on the Compressed Sensing codes page.

I have also decided to create a disclaimer for all the codes produced/implemented here. In a former life, when my team competed for DARPA's Grand Challenge (we failed), I had decided to release some of our codes. This is the disclaimer we used:

# This code is released
# under the General
# Public Licence (GPL),
# DISCLAIMER : if you do not know
# what you are doing
# do not use this program on a
# motorized vehicle or any machinery
# for that matter. Even if you know
# what you are doing, we absolutely
# cannot be held responsible for your
# use of this program under ANY circumstances.
# The program is
# released for programming education
# purposes only i.e. reading
# the code will allow students
# to understand the flow of the program.
# We do not advocate nor condone
# the use of this program in
# any robotic systems. If you are thinking
# about including this software
# in a machinery of any sort, please don't do it.

Since this was focused on a robot, I have changed it a little to reflect other concerns as well.

DISCLAIMER : if you do not know what you are doing do not use this program. Do not use it on a motorized vehicle or any machinery for that matter. Even if you know what you are doing, we absolutely CANNOT be held responsible for your use of this program under ANY circumstances. The program is released for programming education purposes ONLY i.e. reading the code will allow students to understand the flow and the intent of an algorithm. The purpose of this code/program is to further human understanding in basic science.

We do not advocate nor condone the use of this program in any robotic systems nor in the implementation of any hardware. If you are thinking about including this software in a machinery or some larger software program of any sort, please don't do it , because you are on your own.
This disclaimer is now listed here. I know it sounds funny.

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported License.

4 comments:

SaHKa said...

I found the cosamp.m and cosamp2.m are heavy wrong. I put the corrected version at http://muziq.media.imit.chiba-u.jp/pub/cosamp_m.m
Good luck.

Igor said...

Hello Tomoya,

Can you please describe to me what it wrong with the current code ?

Thanks,

Igor.

SaHKa said...

The currect code works only for solutions with positive nonzeros. This is caused by "b=abs(pinv(phit)*u);" and
"Sest(T(z3(1:K)))=abs(b(z3(1:K)));".
.. now I found it was not so heavy problem though.

Igor said...

Dear Tomoya,

Thank you for your input, I'll feature it in my next entry.

Also, can you provide me with an e-mail for you ? you can send me an e-mail to igorcarron@gmail.com

Thanks and cheers,

Igor.

Printfriendly