Some Bounds and the Conditional Maximum Bound for Restricted Isometry Constants

Year 2014, Volume: 27 Issue: 4, 1021 - 1030, 24.11.2014

Shiqing Wang , Limin Su

Abstract

Compressed sensing seeks to recover an unknown sparse signal with  entries by making far fewer than  measurements. The restricted isometry Constants (RIC) has become a dominant tool used for such cases since if RIC satisfies some bound then sparse signals are guaranteed to be recovered exactly when no noise is present and sparse signals can be estimated stably in the noisy case. During the last few years, a great deal of attention has been focused on bounds of RIC, see, e. g., Candes (2008), Foucart et al (2009), Foucart (2010), Cai et al (2010), Mo et al (2011), Ji et al (2012). Finding bounds of RIC has theoretical and applied significance. In this paper, we obtain a bound of RIC. It improves the results by Cai et al (2010) and Ji et al (2012). Further, we discuss the problems related larger bound of RIC, and give the conditional maximum bound.

Keywords

Compressed sensing, Lminimization, restricted isometry property, sparse signal recovery

References

• Donoho, D. L. and Huo, X., “Uncertainty principles and ideal atomic decomposition”, IEEE Trans. Inf. Theory, 47: 2845-2862, (2001).
• Donoho, D. L., “Compressed sensing”, IEEE Trans. Inf. Theory, 52: 1289-1306, (2006).
• Candes, E. J. and Tao, T., “Decoding by linear programming”, IEEE Trans. Inf. Theory, 51, 4203-4215, (2005).
• Candes, E. J., Romberg, J. and Tao, T., “Stable signal recovery from incomplete and inaccurate measurements”, Comm. Pure Appl. Math., 59, 1207-1223, (2006a).
• Candes, E. J. and Tao, T., “Near-optimal signal recovery from random projections: Universal encoding strategies”, IEEE Trans. Inf. Theory, 52, 5406-5425, (2006b).
• Candes, E. J. and Tao, T., “The Dantzig selector: Statistical estimation when p is much larger than n (with discussion)”, Ann. Stat., 35, 2313-2351, (2007).
• Cai, T., Wang, L. and Xu, G., “Shifting inequality and recovery of sparse signals”, IEEE Trans. Signal Process., 58: 1300-1308, (2010a).
• Cai, T., Wang, L. and Xu, G., “Stable recovery of sparse signals and an oracle inequality”, IEEE Trans. Inf. Theory, 56: 3516-3522, (2010b).
• Bickel, P. J., Ritov, Y. and Tsybakov A. B., “Simultaneous analysis of Lasso and Dantzig selector”, Ann. Stat., 37: 1705-1732, (2009).
• Wang, S. Q. and Su, L. M., “The oracle inequalities on simultaneous Lasso and Dantzig selector in high dimensional nonparametric regression”, Math. Probl. Eng., (2013). doi:10.1155/2013/571361
• Wang, S. Q. and Su, L. M. (2013b). “Recovery of high-dimensional spares signals via L1-minimization”, J. Appl. Math., (2013).
• Wang, S. Q. and Su, L. M., “Simultaneous Lasso and Dantzig selector in high dimensional nonparametric regression”, Int. J. Appl. Math. Stat.,42: 103-118, (2013). [13] Cai, T., Xu, G. and Zhang, J., “On recovery of sparse signals via L minimization”, IEEE Trans. Inf. Theory, 1L 55: 3388-3397, (2009).
• Baraniuk, R., Davenport, M., DeVore, R. and Wakin, M., “A simple proof of the restricted isometry property for random matrices”, Constr. Approx., 28: 253-263. (2008).
• Davies, M. E. and Gribonval, R., “Restricted isometry constants where L sparse recovery can fail p
• for 0< ≤ ”, IEEE Trans. Inf. Theory, 55: 203-2214, 1 p (2009).
• Candes, E. J., “The restricted isometry property and its implications for compressed sensing”, Comptes Rendus Mathematique, 346: 589-592, (2008).
• Foucart, S. and Lai, M., “Sparsest solutions of underdetermined linear systems via L minimization for q
• 0< ≤ ”, Appl. Comput. Harmon. Anal., 26: 395-407, q1 (2009).
• Foucart, S., “A note on guaranteed sparse recovery via L minimization”, Appl. Comput. Harmon. Anal., 29: 97-103, (2010).
• Mo, Q. and Li, S., “New bounds on the restricted isometry constantδ 2k
• ”, Appl. Comput. Harmon. Anal., 31: 460-468, (2011).
• Cai, T., Wang, L. and Xu, G., “New bounds for restricted isometry constants”, IEEE Trans. Inf. Theory, 56: 4388-4394, (2010c).
• Ji, J. and Peng, J., “Improved Bounds for Restricted Isometry Constants”, Discrete Dyn. Nat. Soc., (2012). doi:10.1155/2012/841261