Learning circulant sensing kernels


In signal acquisition, Toeplitz and circulant matrices are widely used as sensing operators. They correspond to discrete convolutions and are easily or even naturally realized in various applications. For compressive sensing, recent work has used random Toeplitz and circulant sensing matrices and proved their efficiency in theory, by computer simulations, as well as through physical optical experiments.

Learn the sensing kernel

One condition for sparse signal recovery from compressive sensing is incoherence between sensing matrix and sparsifying matrix. Given a sparsifying matrix or dictionary Psi, our method aims at learning a circulant sensing matrix/operator to achieve low coherence.

We use circulant matrix/operator is due to signal acquisition consideration particular for large-scale data. A circulant matrix can be written as C=Fmathrm{diag}(d)F^*, where F is discrete Fourier matrix, so performing C to a signal can be realized by a fast Fourier transform (FFT), an inverse FFT, and some component-wise multiplication. Similar argument applies to 2D circulant operator mathcal{C}_2 by noting it can be written as mathcal{C}_2=mathcal{F}_2circmathcal{V}circmathcal{F}_2^*, where mathcal{F}_2 is a 2D Fourier transform.

For one-dimensional signal, our method learns a partial circulant matrix by solving

 mathop{mathrm{minimize}}_Phi |Psi^*Phi^*PhiPsi-I|_F^2

where Phi=PC, C is a circulant matrix, and P is a row-selecting matrix.

For two-dimensional signal, it learns a partial circulant operator by solving

 mathop{mathrm{minimize}}_{mathcal{G}} |mathcal{Q}^*mathcal{G}^*mathcal{G}mathcal{Q}-mathcal{I}|^2

where mathcal{G}=mathcal{P}_Omegamathcal{C}_2, mathcal{C}_2 is a 2D circulant operator, and mathcal{P}_Omega is a downsampling operator.

The above learning processes are carried out in two steps. The first step learns a circulant matrix/operator, and the second step learns a downsampling matrix/operator. Learning a circulant matrix/operator is equivalent to learning a kernel, and thus it can be easily done. The two steps can be repeated many times. However, the optimization problem about the downsamplers is difficult. We only perform the two steps one time. One can also choose P or mathcal{P}_Omega randomly, which works well on signals without dominating frequency.

In addition, we learn Psi and Phi simultaneously by alternatively updating them. The coupled learning method can be found in Algorithm 2 of our paper.

Selected numerical results


Matlab codes

a test of 1D signal recovery with synthetic dictionaries and a randomly generated sparse signal

a test that illustrates how to apply a 2D circulant operator to image patches and recover a 2D image from circulant measurements

a test that demonstrates image recovery using a fullsize sensing operator and dictionary; see how to form an image-size dictionary


Y. Xu, W. Yin, and S. Osher. Learning circulant sensing kernels. Inverse Problems and Imaging, 8(3), 901–923.