zbMATH — the first resource for mathematics

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.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
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.

94A12Signal theory (characterization, reconstruction, filtering, etc.)
41A29Approximation with constraints
65T99Numerical methods in Fourier analysis
94A20Sampling theory
Full Text: DOI arXiv
[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<q?1, Appl. comput. Harmon. anal. 26, No. 3, 395-407 (2009) · Zbl 1171.90014 · doi:10.1016/j.acha.2008.09.001
[26] A.C. Gilbert, M. Muthukrishnan, M.J. Strauss, Approximation of functions over redundant dictionaries using coherence, in: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, Jan. 2003. · Zbl 1094.41500
[27] A. Hinrichs, J. Vybiral, Johnson-Lindenstrauss lemma for circulant matrices, 2010, submitted for publication.
[28] A. Khajehnejad, W. Xu, S. Avestimehr, B. Hassibi, Improved sparse recovery thresholds with two-step reweighted \ell 1 minimization, in: IEEE Int. Symposium on Information Theory (ISIT), 2010.
[29] F. Krahmer, R. Ward, New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property, 2010, submitted for publication. · Zbl 1247.15019
[30] Mallat, S.: A wavelet tour of signal processing, (1999) · Zbl 0998.94510
[31] Mallat, S.; Zhang, Z.: Matching pursuits with time-frequency dictionaries, IEEE trans. Signal process. 41, No. 12, 3397-3415 (1993) · Zbl 0842.94004 · doi:10.1109/78.258082
[32] Mendelson, S.; Pajor, A.; Tomczak-Jaegermann, N.: Uniform uncertainty principle for Bernoulli and subgaussian ensembles, Constr. approx. 28, No. 3, 277-289 (2008) · Zbl 1230.46011
[33] D. Needell, Noisy signal recovery via iterative reweighted \ell 1-minimization, in: Proceedings of the 43rd Ann. Asilomar Conf. Signals, Systems, and Computers, 2009.
[34] Needell, D.; Tropp, J. A.: Cosamp: iterative signal recovery from noisy samples, Appl. comput. Harmon. anal. 26, No. 3, 301-321 (2008) · Zbl 1163.94003
[35] P. Randall, Sparse recovery via convex optimization, Ph.D. dissertation, California Institute of Technology, 2009.
[36] Ron, A.; Shen, Z.: Affine systems in $L2(Rd)$: the analysis of the analysis operator, J. funct. Anal. 148, 408-447 (1997) · Zbl 0891.42018 · doi:10.1006/jfan.1996.3079
[37] Rudelson, M.; Vershynin, R.: On sparse reconstruction from Fourier and Gaussian measurements, Comm. pure appl. Math. 61, 1025-1045 (2008) · Zbl 1149.94010 · doi:10.1002/cpa.20227
[38] Rauhut, H.; Schnass, K.; Vandergheynst, P.: Compressed sensing and redundant dictionaries, IEEE trans. Inform. theory 54, No. 5, 2210-2219 (2008) · Zbl 05516893
[39] Starck, J. -L.; Elad, M.; Donoho, D. L.: Redundant multiscale transforms and their application for morphological component analysis, Adv. imag. Elect. phys. 132 (2004)
[40] Starck, J. -L.; Fadili, J.; Murtagh, F.: The undecimated wavelet decomposition and its reconstruction, IEEE trans. Signal process. 16, No. 2, 297-309 (2007)
[41] Tropp, J. A.: Greed is good: algorithmic results for sparse approximation, IEEE trans. Inform. theory 50, No. 10, 2231-2242 (2004) · Zbl 1288.94019
[42] Tropp, J. A.; Gilbert, A. C.: Signal recovery from random measurements via orthogonal matching pursuit, IEEE trans. Inform. theory 53, No. 12, 4655-4666 (2007) · Zbl 1288.94022