Rice University logo

Random Teoplitz / Circulant / Convolution


Sensing matrix A = [Downsample]*[Circulant Matrix]

Note that a Toeplitz matrix can be turned into a circulant matrix by adding zeros. Also, multiplying with a circulant matrix is equivalent to circular convolution with its first row.

Benefits for Compressive Sensing

  • Easy to realize by hardware.
  • Effective encoding. The compression ratio is as good as i.i.d. Gaussian random matrices.
  • Faster decoding.

Performance comparisons: See here or this paper.

1D Matlab Demo: Version 2010/05/29, Download Link.

To install, (i) download and install YALL1; (ii) put yall1.m in the search path, and then the demo is ready to run.

2D Matlab Solver / Demo: See here. Blog in English / Chinese.

Discussions and Q&As: link.

Contributors: Junfeng Yang and Wotao Yin