# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Compressed sensing with coherent and redundant dictionaries. (English) Zbl 1215.94026
Summary: This article presents novel results concerning the recovery of signals from undersampled data in the common situation where such signals are not sparse in an orthonormal basis or incoherent dictionary, but in a truly redundant dictionary. This work thus bridges a gap in the literature and shows not only that compressed sensing is viable in this context, but also that accurate recovery is possible via an $\ell _{1}$-analysis optimization problem. We introduce a condition on the measurement/sensing matrix, which is a natural generalization of the now well-known restricted isometry property, and which guarantees accurate recovery of signals that are nearly sparse in (possibly) highly overcomplete and coherent dictionaries. This condition imposes no incoherence restriction on the dictionary and our results may be the first of this kind. We discuss practical examples and the implications of our results on those applications, and complement our study by demonstrating the potential of $\ell _{1}$-analysis for such problems.

##### MSC:
 94A12 Signal theory (characterization, reconstruction, filtering, etc.) 41A29 Approximation with constraints 65T99 Numerical methods in Fourier analysis 94A20 Sampling theory
Full Text:
##### References:
 [1] Zoubir, A. M.; Iskander, D. R.: Bootstrap methods in signal processing, IEEE signal process. Mag. 24, No. 4 (2007) · Zbl 1058.94005 [2] Baraniuk, R.; Candès, E.; Nowak, R.; Vetterli, M.: Sensing, sampling, and compression, IEEE signal process. Mag. 25, No. 2 (2008) [3] Ailon, N.; Chazelle, B.: The fast Johnson-lindenstrauss transform and approximate nearest neighbors, SIAM J. Comput. 39, 302-322 (2009) · Zbl 1185.68327 · doi:10.1137/060673096 [4] N. Ailon, E. Liberty, An almost optimal unrestricted fast Johnson-Lindenstrauss transform, in: ACM-SIAM Symposium on Discrete Algorithms, 2011. · Zbl 1301.68233 [5] W. Bajwa, R. Calderbank, S. Jafarpour, Why Gabor frames? Two fundamental measures of coherence and their geometric significance, IEEE Trans. Signal Process. (2008), in press. [6] Baraniuk, R.; Davenport, M.; Devore, R.; Wakin, M.: A simple proof of the restricted isometry property for random matrices, Constr. approx. 28, No. 3, 253-263 (2008) · Zbl 1177.15015 · doi:10.1007/s00365-007-9003-x [7] Blumensath, T.; Davies, M. E.: Iterative hard thresholding for compressed sensing, Appl. comput. Harmon. anal. 27, No. 3, 265-274 (2009) · Zbl 1174.94008 · doi:10.1016/j.acha.2009.04.002 [8] Cai, J. -F.; Osher, S.; Shen, Z.: Split Bregman methods and frame based image restoration, Multiscale model. Simul. 8, No. 2, 337-369 (2009) · Zbl 1189.94014 · doi:10.1137/090753504 [9] Candès, E. J.: The restricted isometry property and its implications for compressed sensing, C. R. Math. acad. Sci. Paris 346, 589-592 (2008) · Zbl 1153.94002 · doi:10.1016/j.crma.2008.03.014 [10] Candès, E. J.; Demanet, L.; Donoho, D. L.; Ying, L.: Fast discrete curvelet transforms, Multiscale model. Simul. 5, 861-899 (2000) · Zbl 1122.65134 · doi:10.1137/05064182X [11] Candès, E. J.; Donoho, D. L.: New tight frames of curvelets and optimal representations of objects with piecewise C2 singularities, Comm. pure appl. Math. 57, No. 2, 219-266 (2004) · Zbl 1038.94502 · doi:10.1002/cpa.10116 [12] Candès, E. J.; Plan, Y.: Near-ideal model selection by $\ell 1$ minimization, Ann. statist. 37, 2145-2177 (2007) · Zbl 1173.62053 · doi:10.1214/08-AOS653 [13] Candès, E. J.; Romberg, J.; Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete Fourier information, IEEE trans. Inform. theory 52, No. 2, 489-509 (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083 [14] Candès, E. J.; Romberg, J.; Tao, T.: Stable signal recovery from incomplete and inaccurate measurements, Comm. pure appl. Math. 59, No. 8, 1207-1223 (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124 [15] Candès, E. J.; Tao, T.: Decoding by linear programming, IEEE trans. Inform. theory 51, 4203-4215 (2005) · Zbl 1264.94121 [16] Candès, E. J.; Tao, T.: Near optimal signal recovery from random projections: universal encoding strategies?, IEEE trans. Inform. theory 52, No. 12, 5406-5425 (2006) · Zbl 1309.94033 [17] Candès, E. J.; Wakin, M.; Boyd, S.: Enhancing sparsity by reweighted $\ell 1$ minimization, J. Fourier anal. Appl. 14, No. 5, 877-905 (2008) · Zbl 1176.94014 · doi:10.1007/s00041-008-9045-x [18] Donoho, D. L.: Compressed sensing, IEEE trans. Inform. theory 52, No. 4, 1289-1306 (2006) · Zbl 1288.94016 [19] D.L. Donoho, G. Kutyniok, Microlocal analysis of the geometric separation problem, 2010, submitted for publication. · Zbl 1261.94007 [20] Dutilleux, P.: An implementation of the ”algorithme à trous” to compute the wavelet transform, Wavelets: time-frequency methods and phase-space (1989) · Zbl 0850.94022 [21] Elad, M.; Milanfar, P.; Rubinstein, R.: Analysis versus synthesis in signal priors, Inverse problems 23, No. 3, 947-968 (2007) · Zbl 1138.93055 · doi:10.1088/0266-5611/23/3/007 [22] , Gabor analysis and algorithms (1998) · Zbl 0890.42004 [23] Fornasier, M.; Rauhut, H.: Iterative thresholding algorithms, Appl. comput. Harmon. anal. 25, No. 2, 187-208 (2008) · Zbl 1149.65038 · doi:10.1016/j.acha.2007.10.005 [24] Foucart, S.: A note on guaranteed sparse recovery via $\ell 1$-minimization, Appl. comput. Harmon. anal. 29, No. 1, 97-103 (2010) · Zbl 1198.41011 · doi:10.1016/j.acha.2009.10.004 [25] Foucart, S.; Lai, M. -J.: Sparsest solutions of undetermined linear systems via $\ell$q-minimization for 0