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, 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
 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
 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
 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.
 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.
 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
 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