We explore the stability of image reconstruction algorithms under deterministic compressed sensing. Recently, we have proposed [ 1-3 ] deterministic compressed sensing algorithms for 2D images. These algorithms are suitable when Daubechies wavelets are used as the sparsifying basis. In the initial work, we have shown that the algorithms perform well for images with sparse wavelets coefficients. In this work, we address the question of robustness and stability of the algorithms, specifically, if the image is not sparse and/or if noise is present. We show that our algorithms perform very well in the presence of a certain degree of noise. This is especially important for MRI and other real world applications where some level of noise is always present.
K. Ni, P. Mahanti, S. Datta, S. Roudenko and D. Cochran, “Image Reconstruction by Deterministic Compressive Sensing with Chirp Matrices,” Proceedings of SPIE, Vol. 7497, 2009. doi:10.1117/12.832649
K. Ni, S. Datta, P. Mahanti, S. Roudenko and D. Cochran, “Using Reed-Muller Codes as Deterministic Compressive Sensing Matrices for Image Reconstruction,” Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, Dallas, 2010, pp. 465-468.
K. Ni, S. Datta, P. Mahanti, S. Roudenko and D. Cochran, “Efficient Deterministic Compressed Sensing for Images with Chirps and Reed-Muller Sequences,” SIAM Journal in Imaging and Sciences, Vol. 4, No. 3, 2011, pp. 931-953.
E. J. Candès, “Compressive Sampling,” Proceedings of the International Congress of Mathematicians, Madrid, 2006, pp. 1433-1452.
E. J. Candès, J. Romberg and T, Tao, “Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information,” IEEE Transactions on Information Theory, Vol. 52, No. 2, 2006, pp. 489-509. doi:10.1109/TIT.2005.862083
D. L. Donoho, “Compressed Sensing,” IEEE Transactions on Information Theory, Vol. 52, No. 4, 2006, pp. 1289-1306. doi:10.1109/TIT.2006.871582
M. Lustig, D. Donoho and J. M. Pauly, “Sparse MRI: The Application of Compressed Sensing for Rapid MR Imaging,” Magnetic Resonance in Medicine, Vol. 58, No. 6, 2007, pp. 1182-1195. doi:10.1002/mrm.21391
W. U. Bajwa, J. Haupt, A. M. Sayeed and R. Nowak, “Compressed Channel Sensing: A New Approach to Estimating Sparse Multipath Channels,” Proceedings of IEEE, June 2010, pp. 1058-1076.
M. Mishali and Y. C. Eldar, “Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals,” IEEE Transactions on Signal Processing, Vol. 57, No. 30, 2009, pp. 993-1009.
T. Lin and F. J. Herrmann, “Compressed Wavefield Extrapolation,” Geophysics, Vol. 72, No. 5, 2007, pp. SM77-SM93. doi:10.1190/1.2750716
E. J. Candès and T. Tao, “Near Optimal Signal Recovery from Random Projections: Universal Encoding Strategies?” IEEE Transactions on Information Theory, Vol. 52, No. 12, 2006, pp. 5406-5425. doi:10.1109/TIT.2006.885507
E. J. Candès, J. Romberg and T. Tao, “Stable Signal Recovery from Incomplete and Inaccurate Measurements,” Communications on Pure and Applied Mathematics, Vol. 59, No. 8, 2006, pp. 1207-1223. doi:10.1002/cpa.20124
E. J. Candès and J. K. Romberg, “Signal Recovery from Random Projections,” Proceedings of SPIE, Vol. 5674, 2005, pp. 76-86.
R. DeVore, “Deterministic Constructions of Compressed Sensing Matrices,” Journal of Complexity, Vol. 23, No. 4-6, 2007, pp. 918-925. doi:10.1016/j.jco.2007.04.002
L. Applebaum, S. D. Howard, S. Searle and R. Calderbank, “Chirp Sensing Codes: Deterministic Compressed Sensing Measurements for Fast Recovery,” Applied and Computational Harmonic Analysis, Vol. 26, No. 2, 2009, pp. 283-290. doi:10.1016/j.acha.2008.08.002
S. D. Howard, A. R. Calderbank and S. J. Searle, “A Fast Reconstruction Algorithm for Deterministic Compressive Sensing using Second Order Reed-Muller Codes,” Proceedings of the Conference on Information Sciences and Systems, Princeton, 2008, pp. 11-15.
R. Calderbank, S. Howard and S. Jafarpour, “Construction of a Large Class of Deterministic Matrices that Satisfy a Statistical Isometry Property,” IEEE Journal on Selected Topics in Signal Processing, Vol. 29, No. 4, 2009, pp. 358-374.
P. Indyk, “Near-Optimal Sparse Recovery in the L1 Norm,” 49th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, 25-28 October 2008, pp. 199-207.
E. J. Candès and J. Romberg, “Sparsity and Incoherence in Compressive Sampling,” Inverse Problems, Vol. 23, No. 3, 2007, pp. 969-985. doi:10.1088/0266-5611/23/3/008
D. Baron, M. F. Duarte, S. Sarvotham, M. B. Wakin and R. G. Baraniuk, “An Information-Theoretic Approach to Distribute Compressed Sensing,” Proceedings of the 43rd Allerton Conference on Cozmmunications, Control, and Computing, Allerton, September 2005.
W. O. Alltop, “Complex Sequences with Low Periodic Correlations,” IEEE Transactions on Information Theory, Vol. 26, No. 3, 1980, pp. 350-354. doi:10.1109/TIT.1980.1056185
K. J. Horadam, “Hadamard Matrices and Their Applications,” Princeton University Press, Princeton, 2007.
A. Roger Hammons Jr., P. Vijay Kumar, A. R. Calderbank, N. J. A. Sloane and P. Solé, “The -Linearity of Kerdock, Preparata, Goethals, and Related Codes,” IEEE Transactions on Information Theory, Vol. 40, No. 2, 1994, pp. 301-319. doi:10.1109/18.312154
R. Calderbank, “Personal Communication,” 2009.
A. M. Kerdock, “A Class of Low Rate Nonlinear Binary Codes,” Information and Control, Vol. 20, No. 2, 1972, pp. 182-187. doi:10.1016/S0019-9958(72)90376-2
C. C. Paige and M. A. Saunders, “LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares,” ACM Transactions on Mathematical Software, Vol. 8, No. 1, 1982, pp. 43-71.
T. Faktor, Y. C. Eldar and M. Elad, “Exploiting Statistical Dependencies in Sparse Representations for Signal Recovery,” IEEE Transactions on Signal Processing, Vol. 60, No. 5, 2012, pp. 2286-2303.
C. La and M. N. Do, “Tree-Based Orthogonal Matching Pursuit Algorithm for Signal Reconstruction,” 2006 IEEE International Conference on Image Processing, Atlanta, 8-11 October 2006, pp. 1277-1280.
Y. C. Eldar and M. Mishali, “Robust Recovery of Signals from a Structured Union of Subspaces,” IEEE Transactions on Information Theory, Vol. 55, No. 11, 2009, pp. 5302-5316. doi:10.1109/TIT.2009.2030471
Y. C. Eldar, P. Kuppinger and H. Bolcskei, “Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery,” 2010. arXiv:0906.3173
J. Romberg, “Imaging via Compressive Sampling,” IEEE Signal Processing Magazine, Vol. 25, No. 2, 2008, pp. 14-20.