At the origin of compressive sampling/sensing (CS) stands the assertion that an image with a rare representation in a base can be reconstructed from relatively few samples, if they are well chosen. Rare representation means that a large number of coefficients are zero or close to zero, resulted by projecting the image in that base.

In classical compression, although these bases lead to rare representations, yet the coefficients are fully encoded, for the simple fact that the position of those different from zero is unknown. Compressive sam-pling eliminates this shortcoming by measuring, in certain conditions, a reduced number M = K log N of samples from which, one can estimate all the coefficients of K order followed by the reconstruction of the image f through reverse transformation.

CS provides an alternative to Shannon/Nyquist sampling for the acquisition of sparse or compressible signals that can be well approximated by just K<< N elements from an N-dimensional basis. Instead of taking periodic samples, CS measures inner products with M < N random vectors and then recovers the signal via a sparsity-seeking optimization or greedy algorithm.

*Greedy pursuits*: These methods build up an approximation one step at a time by making locally optimal choices at each step. Examples include Orthogonal Matching Pursuit (OMP), stagewise OMP (StOMP), and regularized OMP (ROMP).*Convex relaxation*: These techniques solve a convex program whose minimizer is known to approximate the target signal. Many algorithms have been proposed to complete the optimization, including interior-point methods, projected gradient methods, and iterative thresholding.*Combinatorial algorithms*: These methods acquire highly structured samples (measurements) of the signal that support rapid reconstruction via group testing. This class includes Fourier sampling, chaining pursuit, and HHS pursuit, as well as some algorithms of Cormode–Muthukrishnan and Iwen.

CoSaMP is a greedy pursuit algorithm that uses an approach inspired by the restricted isometry property. For an s-sparse signal x, the vector y = Φ

As input, the CoSaMP algorithm requires 4 pieces of information:

- access to the sampling operator Φ via matrix–vector multiplication
- a vector y of (noisy) samples of the unknown signal
- the sparsity s of the approximation to be produced
- a halting criterion

*Identification*. The algorithm forms a proxy of the residual from the current samples and locates the largest components of the proxy (steps 6 and 7 in the image bellow)*Support Merger*. The set of newly identified components is united with the set of components that appear in the current approximation (step 8)*Estimation*. The algorithm solves a least-squares problem to approximate the target signal on the merged set of components (step 9)*Pruning*. The algorithm produces a new approximation by retaining only the s largest entries in this least-squares signal approximation (step 10).*Sample Update*. Finally, the samples are updated so that they reflect the residual, the part of the signal that has not been approximated

The main goal was in finding the appropriate couple of Sensing matrix - Transform, for CS algorithm.

For this, the method of couple evaluation by Rate-Distortion curve was used. The experiments were carried out on two test images, namely,

As tested sensing matrices we recall: Binary Random, Binary Sparse, and Low Density Parity Code (LDPC); and as transform, we mention: Discrete Cosine Transform, Wavelet Transform, and Total Variation (TV).

The softwares used in these tests are CS Toolbox and L1 Magic.

The solution was to use LDPC as the Sensing Matrix and TV as the Transform.

- M. Unser,
*Sampling - 50 Years after Shannon*, Proc. of the IEEE, 88(4), 569–587 (2000) - R.Baraniuk, V.Cevher, M.Duarte,
*Model-Based Compressive Sensing*, IEEE Transactions on Information Theory 56(4) (2010) - R.Baraniuk, V.Cevher, Ma.Duarte, C.Hegde,
*Model-based Compressive Sensing Toolbox v1.1*. » Link to download the CS Toolbox, from Rice University - Needell, D., Tropp, J. A.,
*CoSaMP: Iterative signal recovery from incomplete and inaccurate samples*. ACM Technical Report 2008--01, California Institute of Technology, Pasadena (July 2008) - J. A. Tropp and A. C. Gilbert,
*Signal recovery from random measurements via orthogonal matching pursuit*, IEEE Trans. Info. Theory, 53(12), 4655–4666 (2007) - G. Cormode and S. Muthukrishnan,
*Combinatorial algorithms for compressed sensing*, Technical report, DIMACS (2005) - M. Iwen,
*A deterministic sub-linear time sparse Fourier algorithm via non-adaptive compressed sensing methods*, Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA) (2008) - Graeme Pope,
*Compressive Sensing. A Summary of Reconstruction Algorithms*, Masters Thesis, Department of Computer Science Eidgenossische Technische Hochschule, Zurich (2009)