# American Institute of Mathematical Sciences

• Previous Article
Shape reconstruction from images: Pixel fields and Fourier transform
• IPI Home
• This Issue
• Next Article
Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing
August  2014, 8(3): 901-923. doi: 10.3934/ipi.2014.8.901

## Learning circulant sensing kernels

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

Received  May 2013 Revised  October 2013 Published  August 2014

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.
Citation: Yangyang Xu, Wotao Yin, Stanley Osher. Learning circulant sensing kernels. Inverse Problems & Imaging, 2014, 8 (3) : 901-923. doi: 10.3934/ipi.2014.8.901
##### 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. 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), (2007), 294. doi: 10.1109/SSP.2007.4301266. [3] R. Baraniuk and P. Steeghs, Compressive radar imaging,, IEEE Radar Conference, (2007), 128. doi: 10.1109/RADAR.2007.374203. [4] R. Bixby, Z. Gu and E. Rothberg, Gurobi optimization,, , (): 2009. [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. [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. doi: 10.1063/1.3078420. [7] D. Donoho, Compressed sensing,, IEEE Transactions on Information Theory, 52 (2006), 1289. 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. doi: 10.1109/TIP.2009.2022459. [9] M. Elad, Optimized projections for compressed sensing,, IEEE Transactions on Signal Processing, 55 (2007), 5695. 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. doi: 10.1109/TIP.2006.881969. [11] R. M. Gray, Toeplitz and circulant matrices: A review,, Communications and Information Theory, 2 (2005), 155. 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. 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. 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. [15] S. G. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries,, IEEE Transactions on Signal Processing, 41 (1993), 3397. 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. 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. 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. 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, 6 (2012), 15. 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. 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. 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. doi: 10.1016/j.acha.2011.05.001. [24] J. Romberg, Compressive sensing by random convolution,, SIAM Journal on Imaging Sciences, 2 (2009), 1098. 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. doi: 10.1109/23.819285. [26] J. Tropp, Greed is good: Algorithmic results for sparse approximation,, IEEE Transactions on Information Theory, 50 (2006), 2231. 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, (2006), 872. 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: , (). [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. [30] S. Wright, R. Nowak and M. Figueiredo, Sparse reconstruction by separable approximation,, IEEE Transactions on Signal Processing, 57 (2009), 2479. 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. doi: 10.1137/090777761. [32] W. Yin, Analysis and generalizations of the linearized Bregman method,, SIAM Journal on Imaging Sciences, 3 (2010), 856. 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. doi: 10.1137/070703983. [35] W. Yin, Gurobi mex: A matlab interface for gurobi,, 2009-2011. Available from: , (): 2009.

show all references

##### 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. 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), (2007), 294. doi: 10.1109/SSP.2007.4301266. [3] R. Baraniuk and P. Steeghs, Compressive radar imaging,, IEEE Radar Conference, (2007), 128. doi: 10.1109/RADAR.2007.374203. [4] R. Bixby, Z. Gu and E. Rothberg, Gurobi optimization,, , (): 2009. [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. [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. doi: 10.1063/1.3078420. [7] D. Donoho, Compressed sensing,, IEEE Transactions on Information Theory, 52 (2006), 1289. 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. doi: 10.1109/TIP.2009.2022459. [9] M. Elad, Optimized projections for compressed sensing,, IEEE Transactions on Signal Processing, 55 (2007), 5695. 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. doi: 10.1109/TIP.2006.881969. [11] R. M. Gray, Toeplitz and circulant matrices: A review,, Communications and Information Theory, 2 (2005), 155. 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. 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. 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. [15] S. G. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries,, IEEE Transactions on Signal Processing, 41 (1993), 3397. 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. 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. 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. 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, 6 (2012), 15. 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. 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. 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. doi: 10.1016/j.acha.2011.05.001. [24] J. Romberg, Compressive sensing by random convolution,, SIAM Journal on Imaging Sciences, 2 (2009), 1098. 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. doi: 10.1109/23.819285. [26] J. Tropp, Greed is good: Algorithmic results for sparse approximation,, IEEE Transactions on Information Theory, 50 (2006), 2231. 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, (2006), 872. 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: , (). [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. [30] S. Wright, R. Nowak and M. Figueiredo, Sparse reconstruction by separable approximation,, IEEE Transactions on Signal Processing, 57 (2009), 2479. 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. doi: 10.1137/090777761. [32] W. Yin, Analysis and generalizations of the linearized Bregman method,, SIAM Journal on Imaging Sciences, 3 (2010), 856. 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. doi: 10.1137/070703983. [35] W. Yin, Gurobi mex: A matlab interface for gurobi,, 2009-2011. Available from: , (): 2009.
 [1] Hong Jiang, Wei Deng, Zuowei Shen. Surveillance video processing using compressive sensing. Inverse Problems & Imaging, 2012, 6 (2) : 201-214. doi: 10.3934/ipi.2012.6.201 [2] Vikram Krishnamurthy, William Hoiles. Information diffusion in social sensing. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 365-411. doi: 10.3934/naco.2016017 [3] Yonggui Zhu, Yuying Shi, Bin Zhang, Xinyan Yu. Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing. Inverse Problems & Imaging, 2014, 8 (3) : 925-937. doi: 10.3934/ipi.2014.8.925 [4] Jian-Wu Xue, Xiao-Kun Xu, Feng Zhang. Big data dynamic compressive sensing system architecture and optimization algorithm for internet of things. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1401-1414. doi: 10.3934/dcdss.2015.8.1401 [5] Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics & Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117 [6] Nicolás M. Crisosto, Christopher M. Kribs-Zaleta, Carlos Castillo-Chávez, Stephen Wirkus. Community resilience in collaborative learning. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 17-40. doi: 10.3934/dcdsb.2010.14.17 [7] Steven L. Brunton, Joshua L. Proctor, Jonathan H. Tu, J. Nathan Kutz. Compressed sensing and dynamic mode decomposition. Journal of Computational Dynamics, 2015, 2 (2) : 165-191. doi: 10.3934/jcd.2015002 [8] Minlong Lin, Ke Tang. Selective further learning of hybrid ensemble for class imbalanced increment learning. Big Data & Information Analytics, 2017, 2 (1) : 1-21. doi: 10.3934/bdia.2017005 [9] Ning Zhang, Qiang Wu. Online learning for supervised dimension reduction. Mathematical Foundations of Computing, 2019, 0 (0) : 0-0. doi: 10.3934/mfc.2019008 [10] Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-8. doi: 10.3934/jimo.2019014 [11] Yang Wang, Zhengfang Zhou. Source extraction in audio via background learning. Inverse Problems & Imaging, 2013, 7 (1) : 283-290. doi: 10.3934/ipi.2013.7.283 [12] Wei Xue, Wensheng Zhang, Gaohang Yu. Least absolute deviations learning of multiple tasks. Journal of Industrial & Management Optimization, 2018, 14 (2) : 719-729. doi: 10.3934/jimo.2017071 [13] G. Calafiore, M.C. Campi. A learning theory approach to the construction of predictor models. Conference Publications, 2003, 2003 (Special) : 156-166. doi: 10.3934/proc.2003.2003.156 [14] Miguel A. Dumett, Roberto Cominetti. On the stability of an adaptive learning dynamics in traffic games. Journal of Dynamics & Games, 2018, 5 (4) : 265-282. doi: 10.3934/jdg.2018017 [15] Mikhail Langovoy, Akhilesh Gotmare, Martin Jaggi. Unsupervised robust nonparametric learning of hidden community properties. Mathematical Foundations of Computing, 2019, 0 (0) : 0-0. doi: 10.3934/mfc.2019010 [16] Tieliang Gong, Qian Zhao, Deyu Meng, Zongben Xu. Why curriculum learning & self-paced learning work in big/noisy data: A theoretical perspective. Big Data & Information Analytics, 2016, 1 (1) : 111-127. doi: 10.3934/bdia.2016.1.111 [17] Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321 [18] Shunfu Jin, Wuyi Yue, Shiying Ge. Equilibrium analysis of an opportunistic spectrum access mechanism with imperfect sensing results. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1255-1271. doi: 10.3934/jimo.2016071 [19] A Voutilainen, Jari P. Kaipio. Model reduction and pollution source identification from remote sensing data. Inverse Problems & Imaging, 2009, 3 (4) : 711-730. doi: 10.3934/ipi.2009.3.711 [20] Haruki Katayama, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Effect of spectrum sensing overhead on performance for cognitive radio networks with channel bonding. Journal of Industrial & Management Optimization, 2014, 10 (1) : 21-40. doi: 10.3934/jimo.2014.10.21

2017 Impact Factor: 1.465