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:

• IRLSregcomp : This script implements an(other) adaptation of the algorithm by Rick Chartrand and Valentina Staneva featured in Restricted isometry properties and nonconvex compressive sensing.
• OMP: this script is an implementation of the classical Orthogonal Matching Pursuit algorithm.
• OMPmod3 : this script is a modified version of OMP. It is a little more computationally expensive but it is also more efficient.
• CoSaMP : this script is an implementation of CoSaMP featured in CoSaMP: Iterative signal recovery from incomplete and inaccurate samples by Deanna Needell and Joel Tropp.
• SPA : this script is an(other) implementation of Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity by Wei Dai and Olgica Milenkovic.

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.

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