Learning circulant sensing kernels

Yangyang Xu; Wotao Yin; Stanley Osher

doi:10.3934/ipi.2014.8.901

Article Contents

2014, Volume 8, Issue 3: 901-923. Doi: 10.3934/ipi.2014.8.901

This issue Previous Article Shape reconstruction from images: Pixel fields and Fourier transform Next Article Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing

Learning circulant sensing kernels

1.
Department of Computational and Applied Mathematics, Rice University, Houston, TX 77005
2.
Department of Mathematics, University of California, Los Angeles, CA 90095-1555

Received: May 2013

Revised: October 2013

Published: August 2014

Abstract / Introduction Related Papers Cited by

Abstract

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. Motivated by recent work [8], we propose models to learn a circulant sensing matrix/operator for one and higher dimensional signals. Given the dictionary of the signal(s) to be sensed, the learned circulant sensing matrix/operator is more effective than a randomly generated circulant sensing matrix/operator, and even slightly so than a (non-circulant) Gaussian random sensing matrix. In addition, by exploiting the circulant structure, we improve the learning from the patch scale in [8] to the much large image scale. Furthermore, we test learning the circulant sensing matrix/operator and the nonparametric dictionary altogether and obtain even better performance. We demonstrate these results using both synthetic sparse signals and real images.

Keywords:

Mathematics Subject Classification: Primary: 94A08, 94A12; Secondary: 90C90.

Citation:

Related Papers

Cited by

References

[1]	M. Aharon, M. Elad and A. Bruckstein, K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation, IEEE Transactions on Signal Processing, 54 (2006), 4311-4322.doi: 10.1109/TSP.2006.881199.
[2]	W. Bajwa, J. Haupt, G. Raz, S. Wright and R. Nowak, Toeplitz-structured compressed sensing matrices, IEEE Workshop on Statistical Signal Processing (SSP), Madison, Wisconsin, August 2007, (2007), 294-298.doi: 10.1109/SSP.2007.4301266.
[3]	R. Baraniuk and P. Steeghs, Compressive radar imaging, IEEE Radar Conference, Waltham, Massachusetts, (2007), 128-133.doi: 10.1109/RADAR.2007.374203.
[4]	R. Bixby, Z. Gu and E. Rothberg, Gurobi optimization, http://www.gurobi.com, 2009-2011.
[5]	E. Candes, J. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate information, Communications on Pure and Applied Mathematics, 59 (2006), 1207-1223.
[6]	M. Combescure, Block-circulant matrices with circulant blocks, weil sums, and mutually unbiased bases. II. The prime power case, Journal of Mathematical Physics, 50 (2009), 1-12.doi: 10.1063/1.3078420.
[7]	D. Donoho, Compressed sensing, IEEE Transactions on Information Theory, 52 (2006), 1289-1306.doi: 10.1109/TIT.2006.871582.
[8]	J. M. Duarte-Carvajalino and G. Sapiro, Learning to sense sparse signals: Simultaneous sensing matrix and sparsifying dictionary optimization, IEEE Transactions on Image Processing, 18 (2009), 1395-1408.doi: 10.1109/TIP.2009.2022459.
[9]	M. Elad, Optimized projections for compressed sensing, IEEE Transactions on Signal Processing, 55 (2007), 5695-5702.doi: 10.1109/TSP.2007.900760.
[10]	M. Elad and M. Aharon, Image denoising via sparse and redundant representations over learned dictionaries, IEEE Transactions on Image Processing, 15 (2006), 3736-3745.doi: 10.1109/TIP.2006.881969.
[11]	R. M. Gray, Toeplitz and circulant matrices: A review, Communications and Information Theory, 2 (2005), 155-239.doi: 10.1561/0100000006.
[12]	J. Haupt, W. U. Bajwa, G. Raz and R. D. Nowak, Toeplitz compressed sensing matrices with applications to sparse channel estimation, IEEE Transactions on Information Theory, 56 (2010), 5862-5875.doi: 10.1109/TIT.2010.2070191.
[13]	M. A. Herman and T. Strohmer, High-resolution radar via compressed sensing, IEEE transactions on signal processing, 57 (2009), 2275-2284.doi: 10.1109/TSP.2009.2014277.
[14]	D. Liang, G. Xu, H. Wang, K. F. King and L. Ying, Toeplitz random encoding MR imaging using compressed sensing, IEEE International Symposium on Biomedical Imaging: From Nano to Macro, (2009), 270-273.
[15]	S. G. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Transactions on Signal Processing, 41 (1993), 3397-3415.doi: 10.1109/78.258082.
[16]	R. Marcia, Z. Harmany and R. Willett, Compressive coded aperture imaging, in SPIE Electronic Imaging, 2009.
[17]	R. Marcia and R. Willett, Compressive coded aperture superresolution image reconstruction, ICASSP, (2008), 833-836.doi: 10.1109/ICASSP.2008.4517739.
[18]	D. Martin, C. Fowlkes, D. Tal and J. Malik, A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics, ICCV, 2 (2001), 416-423.doi: 10.1109/ICCV.2001.937655.
[19]	J. Meng, Y. Li, N. Nguyen, W. Yin and Z. Han, High resolution OFDM channel estimation with low speed ADC using compressive sensing, IEEE ICC 2011 Signal Processing for Communications Symposium, (2011), 1-6.doi: 10.1109/icc.2011.5962563.
[20]	J. Meng, W. Yin, Y. Li, N. Nguyen and Z. Han, Compressive sensing based high resolution channel estimation for {OFDM} system, IEEE Journal of Selected Topics in Signal Processing, Special Issue on Robust Measures and Tests Using Sparse Data for Detection and Estimation, 6 (2012), 15-25.doi: 10.1109/JSTSP.2011.2169649.
[21]	J. F. Murray and K. Kreutz-Delgado, Sparse image coding using learned overcomplete dictionaries, in Proceedings of the 2004 14th IEEE Signal Processing Society Workshop, 2004, 579-588.doi: 10.1109/MLSP.2004.1423021.
[22]	B. A. Olshausen and D. J. Field, Emergence of simple-cell receptive field properties by learning a sparse code for natural images, Nature, 381 (1996), 607-609.doi: 10.1038/381607a0.
[23]	H. Rauhut, J. Romberg and J. A. Tropp, Restricted isometries for partial random circulant matrices, Applied and Computational Harmonic Analysis, 32 (2012), 242-254.doi: 10.1016/j.acha.2011.05.001.
[24]	J. Romberg, Compressive sensing by random convolution, SIAM Journal on Imaging Sciences, 2 (2009), 1098-1128.doi: 10.1137/08072975X.
[25]	A. C. Sauve, A. O. Hero III, W. L. Rogers, S. J. Wilderman and N. H. Clinthorne, 3D image reconstruction for a compton spect camera model, IEEE Transactions on Nuclear Science, 46 (1999), 2075-2084.doi: 10.1109/23.819285.
[26]	J. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Transactions on Information Theory, 50 (2006), 2231-2242.doi: 10.1109/TIT.2004.834793.
[27]	J. Tropp, M. Wakin, M. Duarte, D. Baron and R. Baraniuk, Random filters for compressive sampling and reconstruction, in Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 3, Toulouse, France, 2006, 872-875.doi: 10.1109/ICASSP.2006.1660793.
[28]	E. Van den Berg and M. P. Friedlander, SPGL1: A MATLAB solver for large-scale sparse reconstruction, 2007. Available from: http://www.cs.ubc.ca/labs/scl/index.php/main/spgl1.
[29]	R. M. Willett, R. F. Marcia and J. M. Nichols, Compressed sensing for practical optical imaging systems: A tutorial, Optical Engineering, 50 (2011), 1-13.
[30]	S. Wright, R. Nowak and M. Figueiredo, Sparse reconstruction by separable approximation, IEEE Transactions on Signal Processing, 57 (2009), 2479-2493.doi: 10.1109/TSP.2009.2016892.
[31]	J. Yang and Y. Zhang, Alternating direction algorithms for $l_1 $-problems in compressive sensing, SIAM Journal on Scientific Computing, 33 (2011), 250-278.doi: 10.1137/090777761.
[32]	W. Yin, Analysis and generalizations of the linearized Bregman method, SIAM Journal on Imaging Sciences, 3 (2010), 856-877.doi: 10.1137/090760350.
[33]	W. Yin, S. P. Morgan, J. Yang and Y. Zhang, Practical compressive sensing with Toeplitz and circulant matrices, in Proceedings of Visual Communications and Image Processing (VCIP), 2010.
[34]	W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM Journal on Imaging Sciences, 1 (2008), 143-168.doi: 10.1137/070703983.
[35]	W. Yin, Gurobi mex: A matlab interface for gurobi, 2009-2011. Available from: http://www.convexoptimization.com/wikimization/index.php/gurobi_mex.