Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-05T14:00:27.915Z Has data issue: false hasContentIssue false

THE RESTRICTED ISOMETRY PROPERTY FOR SIGNAL RECOVERY WITH COHERENT TIGHT FRAMES

Published online by Cambridge University Press:  19 August 2015

FEN-GONG WU*
Affiliation:
School of Mathematical Sciences, South China Normal University, Guangzhou 510631, China email [email protected]
DONG-HUI LI
Affiliation:
School of Mathematical Sciences, South China Normal University, Guangzhou 510631, China email [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper, we consider signal recovery via $l_{1}$-analysis optimisation. The signals we consider are not sparse in an orthonormal basis or incoherent dictionary, but sparse or nearly sparse in terms of some tight frame $D$. The analysis in this paper is based on the restricted isometry property adapted to a tight frame $D$ (abbreviated as $D$-RIP), which is a natural extension of the standard restricted isometry property. Assuming that the measurement matrix $A\in \mathbb{R}^{m\times n}$ satisfies $D$-RIP with constant ${\it\delta}_{tk}$ for integer $k$ and $t>1$, we show that the condition ${\it\delta}_{tk}<\sqrt{(t-1)/t}$ guarantees stable recovery of signals through $l_{1}$-analysis. This condition is sharp in the sense explained in the paper. The results improve those of Li and Lin [‘Compressed sensing with coherent tight frames via $l_{q}$-minimization for $0<q\leq 1$’, Preprint, 2011, arXiv:1105.3299] and Baker [‘A note on sparsification by frames’, Preprint, 2013, arXiv:1308.5249].

Type
Research Article
Copyright
© 2015 Australian Mathematical Publishing Association Inc. 

References

Baker, C., ‘A note on sparsification by frames’, Preprint, 2013, arXiv:1308.5249.Google Scholar
Bajwa, W., Calderbank, R. and Jafarpour, S., ‘Why Gabor frames? Two fundamental measures of coherence and their geometric significance’, J. Commun. Netw. 12 (2010), 289307.CrossRefGoogle Scholar
Candès, E. J., Eldar, Y. C., Needell, D. and Randall, P., ‘Compressed sensing with coherent and redundant dictionaries’, Appl. Comput. Harmon. Anal. 31 (2011), 5973.CrossRefGoogle Scholar
Candès, E. J., Romberg, J. and Tao, T., ‘Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information’, IEEE Trans. Inform. Theory 52 (2006), 489509.CrossRefGoogle Scholar
Candès, E. J., Romberg, J. K. and Tao, T., ‘Stable signal recovery from incomplete and inaccurate measurements’, Comm. Pure Appl. Math. 59 (2006), 12071223.CrossRefGoogle Scholar
Candès, E. J. and Tao, T., ‘Decoding by linear programming’, IEEE Trans. Inform. Theory 51 (2005), 42034215.CrossRefGoogle Scholar
Cai, T., Wang, L. and Xu, G., ‘New bounds for restricted isometry constants’, IEEE Trans. Inform. Theory 56 (2010), 43884394.CrossRefGoogle Scholar
Cai, T., Wang, L. and Xu, G., ‘Shifting inequality and recovery of sparse signals’, IEEE Trans. Signal Process. 58 (2010), 13001308.CrossRefGoogle Scholar
Cai, T. and Zhang, A., ‘Compressed sensing and affine rank minimization under restricted isometry’, IEEE Trans. Signal Process. 61 (2013), 32793290.CrossRefGoogle Scholar
Cai, T. and Zhang, A., ‘Sharp RIP bound for sparse signal and low-rank matrix recovery’, Appl. Comput. Harmon. Anal. 35 (2013), 7493.CrossRefGoogle Scholar
Cai, T. and Zhang, A., ‘Sparse representation of a polytope and recovery of sparse signals and low-rank matrices’, IEEE Trans. Inform. Theory 60 (2014), 122132.CrossRefGoogle Scholar
Donoho, D., ‘Compressed sensing’, IEEE Trans. Inform. Theory 52 (2006), 12891306.CrossRefGoogle Scholar
Foucart, S. and Lai, M. J., ‘Sparsest solutions of underdetermined linear systems via l q -minimization for 0 < q ≤ 1’, Appl. Comput. Harmon. Anal. 26 (2009), 395407.CrossRefGoogle Scholar
Li, S. and Lin, J., ‘Compressed sensing with coherent tight frames via l q -minimization for 0 < q ≤ 1’, Inverse Probl. Imaging 8 (2011), doi:10.3934/ipi.2014.8761.Google Scholar
Lin, J. and Li, S., ‘Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO’, Appl. Comput. Harmon. Anal. 37 (2014), 126139.CrossRefGoogle Scholar
Lin, J., Li, S. and Shen, Y., ‘New bounds for restricted isometry constants with coherent tight frames’, IEEE Trans. Signal Process. 61 (2013), 611621.CrossRefGoogle Scholar
Mo, Q. and Li, S., ‘New bounds on the restricted isometry constant 𝛿2k’, Appl. Comput. Harmon. Anal. 31 (2011), 460468.CrossRefGoogle Scholar
Rauhut, H., Schnass, K. and Vandergheynst, P., ‘Compressed sensing and redundant dictionaries’, IEEE Trans. Inform. Theory 54 (2008), 22102219.CrossRefGoogle Scholar
Tropp, J. A., ‘Greed is good: Algorithmic results for sparse approximation’, IEEE Trans. Inform. Theory 50 (2004), 22312242.CrossRefGoogle Scholar
Wu, G. and Xu, Z., ‘On the l 1 -norm invariant convex k-sparse decomposition of signals’, J. Oper. Res. Soc. China 1 (2013), 537541.Google Scholar