# American Institute of Mathematical Sciences

• Previous Article
Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing
• IPI Home
• This Issue
• Next Article
Shape reconstruction from images: Pixel fields and Fourier transform
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 and 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-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.

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-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.
 [1] Hong Jiang, Wei Deng, Zuowei Shen. Surveillance video processing using compressive sensing. Inverse Problems and Imaging, 2012, 6 (2) : 201-214. doi: 10.3934/ipi.2012.6.201 [2] Armin Eftekhari, Michael B. Wakin, Ping Li, Paul G. Constantine. Randomized learning of the second-moment matrix of a smooth function. Foundations of Data Science, 2019, 1 (3) : 329-387. doi: 10.3934/fods.2019015 [3] Vikram Krishnamurthy, William Hoiles. Information diffusion in social sensing. Numerical Algebra, Control and Optimization, 2016, 6 (3) : 365-411. doi: 10.3934/naco.2016017 [4] Richard Archibald, Hoang Tran. A dictionary learning algorithm for compression and reconstruction of streaming data in preset order. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 655-668. doi: 10.3934/dcdss.2021102 [5] Yonggui Zhu, Yuying Shi, Bin Zhang, Xinyan Yu. Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing. Inverse Problems and Imaging, 2014, 8 (3) : 925-937. doi: 10.3934/ipi.2014.8.925 [6] Jian-Wu Xue, Xiao-Kun Xu, Feng Zhang. Big data dynamic compressive sensing system architecture and optimization algorithm for internet of things. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1401-1414. doi: 10.3934/dcdss.2015.8.1401 [7] Meixin Xiong, Liuhong Chen, Ju Ming, Jaemin Shin. Accelerating the Bayesian inference of inverse problems by using data-driven compressive sensing method based on proper orthogonal decomposition. Electronic Research Archive, 2021, 29 (5) : 3383-3403. doi: 10.3934/era.2021044 [8] Franziska Nestler, Martin Stoll, Theresa Wagner. Learning in high-dimensional feature spaces using ANOVA-based fast matrix-vector multiplication. Foundations of Data Science, 2022, 4 (3) : 423-440. doi: 10.3934/fods.2022012 [9] 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 [10] Baohuai Sheng, Huanxiang Liu, Huimin Wang. Learning rates for the kernel regularized regression with a differentiable strongly convex loss. Communications on Pure and Applied Analysis, 2020, 19 (8) : 3973-4005. doi: 10.3934/cpaa.2020176 [11] Shuhua Wang, Baohuai Sheng. Error analysis of kernel regularized pairwise learning with a strongly convex loss. Mathematical Foundations of Computing, 2022  doi: 10.3934/mfc.2022030 [12] Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1519-1526. doi: 10.3934/jimo.2019014 [13] Zhi-An Wang. A kinetic chemotaxis model with internal states and temporal sensing. Kinetic and Related Models, 2022, 15 (1) : 27-48. doi: 10.3934/krm.2021043 [14] Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics and Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117 [15] Christian Soize, Roger Ghanem. Probabilistic learning on manifolds. Foundations of Data Science, 2020, 2 (3) : 279-307. doi: 10.3934/fods.2020013 [16] Mauro Maggioni, James M. Murphy. Learning by active nonlinear diffusion. Foundations of Data Science, 2019, 1 (3) : 271-291. doi: 10.3934/fods.2019012 [17] Nicolás M. Crisosto, Christopher M. Kribs-Zaleta, Carlos Castillo-Chávez, Stephen Wirkus. Community resilience in collaborative learning. Discrete and Continuous Dynamical Systems - B, 2010, 14 (1) : 17-40. doi: 10.3934/dcdsb.2010.14.17 [18] Gernot Holler, Karl Kunisch. Learning nonlocal regularization operators. Mathematical Control and Related Fields, 2022, 12 (1) : 81-114. doi: 10.3934/mcrf.2021003 [19] Sriram Nagaraj. Optimization and learning with nonlocal calculus. Foundations of Data Science, 2022, 4 (3) : 323-353. doi: 10.3934/fods.2022009 [20] Shunfu Jin, Wuyi Yue, Shiying Ge. Equilibrium analysis of an opportunistic spectrum access mechanism with imperfect sensing results. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1255-1271. doi: 10.3934/jimo.2016071

2021 Impact Factor: 1.483