×

Sparse representations and approximation theory. (English) Zbl 1211.94015

Author’s abstract: This paper is an attempt to both expound and expand upon, from an approximation theorist’s point of view, some of the theoretical results that have been obtained in the sparse representation (compressed sensing) literature. In particular, he consider in detail \(\ell^m_1\)-approximation, which is fundamental in the theory of sparse representations, and the connection between the theory of sparse representations and certain \(n\)-width concepts. He tries to illustrate how the theory of sparse representation leads to new and interesting problems in approximation theory, while the results and techniques of approximation theory can further add to the theory of sparse representations.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
41A30 Approximation by other special function classes
65F50 Computational methods for sparse matrices
42C40 Nontrigonometric harmonic analysis involving wavelets and other special systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bruckstein, A. M.; Donoho, D. L.; Elad, M., From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., 51, 34-81 (2009) · Zbl 1178.68619
[2] DeVore, R. A., Optimal computation, (Proceedings of the International Congress of Mathematicians, Madrid, Spain, 2006, vol. I (2007), EMS: EMS Zürich), 187-215 · Zbl 1126.65013
[3] DeVore, R., Deterministic constructions of compressed sensing matrices, J. Complexity, 23, 918-925 (2007) · Zbl 1134.94312
[4] Donoho, D. L., For most large underdetermined systems of equations, the minimal \(\ell_1\)-norm near-solution approximates the sparsest near-solution, Comm. Pure Appl. Math., 59, 907-934 (2006) · Zbl 1105.90068
[5] Donoho, D. L.; Elad, M., On the stability of the basis pursuit in the presence of noise, Signal Process., 86, 511-532 (2006) · Zbl 1163.94329
[6] Donoho, D. L.; Huo, X., Uncertainty principles and ideal atomic decomposition, IEEE Trans. Information Theory, 47, 2845-2862 (2001) · Zbl 1019.94503
[7] M. Elad, Sparse and Redundant Representations — From Theory to Applications in Signal and Image Processing, Springer, 2010.; M. Elad, Sparse and Redundant Representations — From Theory to Applications in Signal and Image Processing, Springer, 2010. · Zbl 1211.94001
[8] Elad, M.; Bruckstein, A. M., A generalized uncertainty principle and sparse representation in pairs of bases, IEEE Trans. Information Theory, 48, 2558-2567 (2002) · Zbl 1062.15001
[9] Feuer, A.; Nemirovski, A., On sparse representation in pairs of bases, IEEE Trans. Information Theory, 49, 1579-1581 (2003) · Zbl 1063.42018
[10] Foucart, S.; Pajor, A.; Rauhut, H.; Ullrich, T., The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\), J. Complexity, 26, 629-640 (2010) · Zbl 1204.41019
[11] Fuchs, J. J., On sparse representations in arbitrary redundant bases, IEEE Trans. Information Theory, 50, 1341-1344 (2004) · Zbl 1284.94018
[12] Garnaev, A. Yu.; Gluskin, E. D., The widths of a Euclidean ball, Dokl. Akad. Nauk SSSR, 277, 1048-1052 (1984) · Zbl 0588.41022
[13] Math. USSR Sb., 48, 173-182 (1984), transl. in · Zbl 0558.46013
[14] Gribonval, R.; Nielsen, M., Sparse decompositions in unions of bases, IEEE Trans. Information Theory, 49, 3320-3325 (2003) · Zbl 1286.94032
[15] Höllig, K., Approximationszahlen von Sobolev-Einbettungen, Math. Ann., 242, 273-281 (1979) · Zbl 0394.41011
[16] James, R. C., Orthogonality and linear functionals in normed linear spaces, Trans. Amer. Math. Soc., 61, 265-292 (1947) · Zbl 0037.08001
[17] Kashin, B., The widths of certain finite dimensional sets and classes of smooth functions, Izv. Akad. Nauk SSSR. Izv. Akad. Nauk SSSR, Math. USSR Izv., 11, 317-333 (1977), transl. in
[18] Kripke, B. R.; Rivlin, T. J., Approximation in the metric of \(L^1(X, \mu)\), Trans. Amer. Math. Soc., 119, 101-122 (1965) · Zbl 0135.35101
[19] Lemmens, P. W.H.; Seidel, J. J., Equiangular lines, J. Algebra, 24, 494-512 (1973) · Zbl 0255.50005
[20] Lorentz, G. G.; Golitschek, M.v.; Makovoz, Y., (Constructive Approximation: Advanced Problems. Constructive Approximation: Advanced Problems, Grundlehren, vol. 304 (1996), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0910.41001
[21] Melkman, A. A., \(n\)-widths of octahedra, (Quantitative Approximation (Proc. Internat. Sympos., Bonn, 1979) (1980), Academic Press: Academic Press New York, London), 209-216 · Zbl 0488.41023
[22] Melkman, A. A., The distance of a subspace of \(R^m\) from its axes and \(n\)-widths of octahedra, J. Approx. Theory, 42, 245-256 (1984) · Zbl 0556.41016
[23] Mendelson, S.; Pajor, A.; Rudelson, M., The geometry of random \(\{- 1, 1 \}\)-polytopes, Disc. Comput. Geom., 34, 365-379 (2005) · Zbl 1081.52005
[24] Mendelson, S.; Pajor, A.; Tomczak-Jaegermann, N., Reconstruction and subgaussian operators in asymptotic geometric analysis, Geom. Funct. Anal., 17, 1248-1282 (2007) · Zbl 1163.46008
[25] Pinchasi, R.; Pinkus, A., Dominating subsets under projections, SIAM J. Discrete Math., 24, 910-920 (2010) · Zbl 1222.41045
[26] Pinkus, A., \((n\)-Widths in Approximation Theory. \(n\)-Widths in Approximation Theory, Ergebnisse, vol. 7 (1985), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0551.41001
[27] Pinkus, A., Matrices and \(n\)-widths, Linear Algebra Appl., 27, 245-278 (1979) · Zbl 0437.41023
[28] Pinkus, A., (On \(L^1\)-Approximation. On \(L^1\)-Approximation, Cambridge Tracts in Mathematics, vol. 93 (1989), Cambridge University Press) · Zbl 0679.41022
[29] J.J. Seidel, A survey in 2-graphs, in: Proceedings Int. Colloq. Teorie Combinatorie, Accad. Naz. Lincei, Rome, 1976, pp. 481-511.; J.J. Seidel, A survey in 2-graphs, in: Proceedings Int. Colloq. Teorie Combinatorie, Accad. Naz. Lincei, Rome, 1976, pp. 481-511.
[30] Strohmer, T.; Heath, R. W., Grassmannian frames with applications to coding and communication, Applied and Computational Harmonic Analysis, 14, 257-275 (2003) · Zbl 1028.42020
[31] Tropp, J. A., Greed is good: algorithmic results for sparse approximation, IEEE Trans. Information Theory, 50, 2231-2242 (2004) · Zbl 1288.94019
[32] van Lint, J. H.; Seidel, J. J., Equilateral points sets in elliptic geometry, Indag. Math., 28, 335-348 (1966) · Zbl 0138.41702
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.