Structurally random matrix toolbox ver 1.0

This package implements fast compressed sensing using structurally random matrices (SRM) described in [1] and [2]. As the package is still under development; any comments or bug reports are highly welcome.

1. Installation

1) Unpack the zip file into a directory in your hard drive;

2) Make available this directory and all subdirectories to MATLAB;

After the installation, you should be able to run all the test programs (with the file names test*.m) under the sub-directory \Examples;

2. Quick Tests

Below is a list of some quick test examples. We also present the approximate running time on a desktop computer with Intel Core™ 2 CPU 6700 @2.66 GHz and 3G RAM.

(1) test2d_1('lena256.bmp',25000);

This test compares the visual quality and PSNR of reconstructed 256256 lena images with 25k random measurements using the following sampling operators:

(a)Scrambled dense FFT [3];

(b)Scrambled 3232 block Walsh-Hadamard transform (WHT) [2];

(c)256256 block DCT with random sign reversal of input samples (the so-called local model in [1]);

Note that (b) is a highly sparse operator, while (c) offers full streaming capability for real-time applications, i.e., one does not need to sample the whole image at one. The sparsifying transform is the 9-7 wavelet transform used in the JPEG 2000 standard and the l1 optimizer is based on the GPSR program in [4].

Approx. running time:8-10 seconds;

(2) test2d_2('lena256.bmp');

This test compares the rate-distortion performance for the 3 sampling operators in “test2d_1.m” for an 256256 lena image.

Approx. running time:1.5 minutes;

(3)test2d_3('lena512.bmp') ;

This test aims to reproduce the results of Fig. 1 and in [1].

Approx. running time: 14 minutes;

(4) test1d;

For a length-256 signal with 30 non-zero elements in the DCT domain, this test compares the successful reconstruction rate for the following measurement operators:

(a) Gaussian i.i.d matrices;

(b) partial Hadamard matrices with random permutation (scrambled WHT);

(c) 88 block-diagonal Hadamard with random permutation;

(d) partial WHT with sign flipping;

Approx. running time: 5 minutes;

3. Brief Package Description

Below we provide a list of the description of sub-directory and core programs. For details on how to use them, use help or refer to test examples mentioned above.

List of sub-directory

Subdirectory / Description
Examples / Detailed examples of compressive sampling using structurally random matrices;
Measurements / Implementation of FFT-based and block -based sampling operators
Test images / 512512 and 256256 Lena and Boat images;
Transforms / /wavelet_routines: symmetric biorthogonal wavelet transform
more transforms will be added in future;
Reconstruction / GPSR_BB.m from [4]
OMP.m orthogonal matching pursuit

List of core programs

Sub-directory / Filename / Description
/Examples / fast_cs2d.m / Main program for spatial-domain CS of 2D images. The sparsifying transform is the linear-phase 9-7 wavelet transform and the l1 optimizer is based on the GPSR program [4].
pfft_cswt2d.m / Main program for compressive sampling of wavelet coefficients using the partial FFT measurement.
/Measurements / blk_f1d.m / implementation of the random block-based sensing operator (e.g., scrambled block Hadamard ensemble in [2]);
blk_t1d.m / implementation of the transpose of the random block-based sensing operator;
fft1d_f.m / implementation of dense FFT-based sampling operator (e.g., scrambled FFT or partial FFT etc.);
fft1d_t.m / implementation of the transpose of dense
FFT-based sampling operator

4. Coming up soon…

Applications of structurally random matrices in pattern recognition…;

5. Reference

[1] T. Do, T. D. Tran and L. Gan, “Fast compressive sampling using structurally random matrices”, in proc. of ICASSP 2008, Las Vegas, April, 2008

[2] L. Gan, T. Do and T. Tran, “Fast compressive imaging using scrambled block hadamard ensemble”, submitted to EUSIPCO 2008, available at

scrambled_blk_WHT.pdf

[3]E. Cand`es and J. Romberg, “Robust signal recovery from incompleteobservations,” in Proc. ICIP, 2006, pp. 1281–1284.

[4] M. A. T. Figueiredo, R. D. Nowak, and S. J. Wright, “Gradient projection for sparse reconstruction,” IEEE Journal on selected topics in Signal Processing, 2007, to appear, available at: