Fast and Efficient Compressive Sampling using Structurally Random Matrices


The Basic Framework    

    We introduce a novel framework of fast and efficient CS. The sampling algorithm contains 3 steps that is illustrated in the diagram below: 

(i) pre-randomizing a signal 

(ii) applying some fast transform to the randomized signal  and finally 

(iii) randomly subsampling the transform coefficients to get compressed measurements. 

    Note that the above sampling algorithm/operator can be mathematically represented as a product of 3 matrices: A = DFR, where 

(i) R, the randomizer, is a random permutation matrix (denoted as the global randomizer) or a random diagonal matrix of Bernoulli i.i.d entries (denoted as the local randomizer)

(ii) F is some fast computable transform such as the FFT, the DCT, the WHT, ect 

(iii) D, the random downsampler, is a matrix composed of nonzero rows of a random diagonal matrix whose diagonal entries Dii are i.i.d binary random variables with P(D_ii = 1) = M/N, where M is the number of measurements. 

A is called a structurally random matrix (SRM). One instance of a SRM is illustrated in the figure below

    Note that  a fast transform can be some block-diagonal transform that is appropriate for streaming applications or very low complexity systems.  

    The reconstruction algorithm can be any l-1 minimization (Basis Pursuit) or  greedy pursuit algorithm (OMP, SP, CoSaMP, SAMP, etc). As the sampling operator A and its adjoint A' own fast implementations, the reconstruction algorithm is highly efficient. The following figure depicts a reconstructed 512x512 Lena image from 25 percents of compressed measurements (we use the GPSR software [4] for reconstruction)

     The SRM framework can be viewed as a universally structured sensing method that owns provably optimal performance and highly efficient implementation, making it a very promising candidate for large-scale, real-time compressed sensing applications.

Extension of the SRMs

SRMs using a deterministic downsampler: replacing the above uniform random downsampler by some irregular sampling lattice such as the quasicrystal one [5] that was also mentioned here and here

In simulations, the SRMs using quasicrystal sampling lattice have performance comparable to that of original SRMs. The following figure depicts the performance curve of the original SRM and SRM using the quasicrystal lattice of sampling. The input image is the 512x512 Lena image and both SRMs use the global randomizer and the DCT as the corresponding fast transform.

2D Separably Structurally Random Operator for Compressive Imaging [6] : A faster and more structured sampling operator for 2D signals such as natural images. Unlike all other existing sampling methods, this operator is designed to sample a natural image efficiently without a need of vectorizing it first . Roughly speaking, this method samples an image by sampling rows and  columns of the image separably after applying a separable preprocessing operator to spread out energy of the image equally to all rows and columns.

Other applications of the SRMs 

Remarkably, besides a direct application in compressed sensing, the SRMs also own a wide range of other applications in realizing other fast and efficient algorithms/transforms for applications of machine learning [7] and control theory [8], etc



1. T. T. Do, L. Gan, N. H. Nguyen and T. D. Tran , Fast and efficient compressive sampling using structurally random matrices,  IEEE Trans. on Signal Processing, to appear

2.  T. T. Do, T. D. Tran, and L. Gan, Fast compressive sampling with structurally random matrices, Proceedings of Acoustics, Speech and Signal Processing, 2008. ICASSP 2008, pp. 3369– 3372, May 2008

3. Lu Gan, Thong Do, Trac D. Tran, Fast compressive imaging using scrambled block Hadamard ensemble, (European Signal Processing Conf. (EUSIPCO), Lausanne, Switzerland, August 2008) 

4. Mário A. T. Figueiredo, Robert D. Nowak, and Stephen J. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. (IEEE Journal of Selected Topics in Signal Processing: Special Issue on Convex Optimization Methods for Signal Processing, 1(4), pp. 586-598, 2007)

5. B. Matei and Y. Meyer, A variant on the compressed sensing of Emmanuel Candès. (Preprint, 2008)

6. T. T. Do, L. Gan and T. D. Tran, "2D Separably Structurally Random Operator for Compressive Imaging" , In preparation.

7. T. T. Do, Y. Chen, N. Nguyen, L. Gan and T. D. Tran, "A Fast and Efficient Heuristic Nuclear Norm Algorithm for Rank Minimization ", submitted to ICASSP 2009, Taipei. 

8. T. T. Do, L. Gan, Y. Chen, N. Nguyen and T. D. Tran, "Fast and Efficient Dimensionality Reduction using Structurally Random Matrices,", submitted to ICASSP 2009, Taipei.


Link to the presentation at ICASSP, Las Vegas, 2008

Link to the Matlab Code