• 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. Google Scholar

[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. Google Scholar

[3]

R. Baraniuk and P. Steeghs, Compressive radar imaging,, IEEE Radar Conference, (2007), 128. doi: 10.1109/RADAR.2007.374203. Google Scholar

[4]

R. Bixby, Z. Gu and E. Rothberg, Gurobi optimization,, , (): 2009. Google Scholar

[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. Google Scholar

[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. Google Scholar

[7]

D. Donoho, Compressed sensing,, IEEE Transactions on Information Theory, 52 (2006), 1289. doi: 10.1109/TIT.2006.871582. Google Scholar

[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. Google Scholar

[9]

M. Elad, Optimized projections for compressed sensing,, IEEE Transactions on Signal Processing, 55 (2007), 5695. doi: 10.1109/TSP.2007.900760. Google Scholar

[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. Google Scholar

[11]

R. M. Gray, Toeplitz and circulant matrices: A review,, Communications and Information Theory, 2 (2005), 155. doi: 10.1561/0100000006. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[16]

R. Marcia, Z. Harmany and R. Willett, Compressive coded aperture imaging,, in SPIE Electronic Imaging, (2009). Google Scholar

[17]

R. Marcia and R. Willett, Compressive coded aperture superresolution image reconstruction,, ICASSP, (2008), 833. doi: 10.1109/ICASSP.2008.4517739. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[24]

J. Romberg, Compressive sensing by random convolution,, SIAM Journal on Imaging Sciences, 2 (2009), 1098. doi: 10.1137/08072975X. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[28]

E. Van den Berg and M. P. Friedlander, SPGL1: A MATLAB solver for large-scale sparse reconstruction,, 2007. Available from: , (). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[32]

W. Yin, Analysis and generalizations of the linearized Bregman method,, SIAM Journal on Imaging Sciences, 3 (2010), 856. doi: 10.1137/090760350. Google Scholar

[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). Google Scholar

[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. Google Scholar

[35]

W. Yin, Gurobi mex: A matlab interface for gurobi,, 2009-2011. Available from: , (): 2009. Google Scholar

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. Google Scholar

[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. Google Scholar

[3]

R. Baraniuk and P. Steeghs, Compressive radar imaging,, IEEE Radar Conference, (2007), 128. doi: 10.1109/RADAR.2007.374203. Google Scholar

[4]

R. Bixby, Z. Gu and E. Rothberg, Gurobi optimization,, , (): 2009. Google Scholar

[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. Google Scholar

[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. Google Scholar

[7]

D. Donoho, Compressed sensing,, IEEE Transactions on Information Theory, 52 (2006), 1289. doi: 10.1109/TIT.2006.871582. Google Scholar

[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. Google Scholar

[9]

M. Elad, Optimized projections for compressed sensing,, IEEE Transactions on Signal Processing, 55 (2007), 5695. doi: 10.1109/TSP.2007.900760. Google Scholar

[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. Google Scholar

[11]

R. M. Gray, Toeplitz and circulant matrices: A review,, Communications and Information Theory, 2 (2005), 155. doi: 10.1561/0100000006. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[16]

R. Marcia, Z. Harmany and R. Willett, Compressive coded aperture imaging,, in SPIE Electronic Imaging, (2009). Google Scholar

[17]

R. Marcia and R. Willett, Compressive coded aperture superresolution image reconstruction,, ICASSP, (2008), 833. doi: 10.1109/ICASSP.2008.4517739. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[24]

J. Romberg, Compressive sensing by random convolution,, SIAM Journal on Imaging Sciences, 2 (2009), 1098. doi: 10.1137/08072975X. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[28]

E. Van den Berg and M. P. Friedlander, SPGL1: A MATLAB solver for large-scale sparse reconstruction,, 2007. Available from: , (). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[32]

W. Yin, Analysis and generalizations of the linearized Bregman method,, SIAM Journal on Imaging Sciences, 3 (2010), 856. doi: 10.1137/090760350. Google Scholar

[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). Google Scholar

[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. Google Scholar

[35]

W. Yin, Gurobi mex: A matlab interface for gurobi,, 2009-2011. Available from: , (): 2009. Google Scholar

[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, 2 (2) : 95-106. 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, 2 (2) : 127-147. 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

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (6)

Other articles
by authors

[Back to Top]