×

zbMATH — the first resource for mathematics

Sparse approximation by greedy algorithms. (English) Zbl 06855382
Qian, Tao (ed.) et al., Mathematical analysis, probability and applications – plenary lectures. ISAAC congress, August 3–8, 2015, Macau, China. Cham: Springer (ISBN 978-3-319-41943-5/hbk; 978-3-319-41945-9/ebook). Springer Proceedings in Mathematics & Statistics 177, 183-215 (2016).
This paper surveys recent results on constructive sparse approximation in the following three aspects: (i) Lebesgue type inequalities for greedy algorithms w.r.t. a certain type of dictionaries; (ii) constructive sparse approximation w.r.t. trigonometric system; (iii) sparse approximation w.r.t dictionaries of tensor-product structure. The techniques employed are based on theory of greedy approximation. Some proofs are given.
For the entire collection see [Zbl 1352.35004].
MSC:
65J05 General theory of numerical analysis in abstract spaces
Software:
CoSaMP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 1. Bazarkhanov, D., Temlyakov, V.: Nonlinear tensor product approximation of functions. J. Complexity 31 , 867-884 (2015). · Zbl 1332.41026
[2] 2. Belinskii, E.S.: Decomposition theorems and approximation by a “floating” system of exponentials. Trans. Am. Math. Soc. 350 , 43-53 (1998) · Zbl 0907.42002
[3] 3. Dai, W., Milenkovic, O.: Subspace pursuit for compressive sensing signal reconstruction. IEEE Trans. Inf. Theory 55 , 2230-2249 (2009) · Zbl 1367.94082
[4] 4. Dahmen, W., DeVore, R., Grasedyck, L., Süli, E.: Tensor-sparsity of solutions to high-dimensional elliptic Partial Differential Equations, Manuscript, 23 July 2014
[5] 5. Davis, G., Mallat, S., Avellaneda, M.: Adaptive greedy approximations. Constr. Approx. 13 , 57-98 (1997) · Zbl 0885.41006
[6] 6. DeVore, R.A.: Nonlinear approximation. Acta Numerica 7 , 51-150 (1998) · Zbl 0931.65007
[7] 7. DeVore, R.A., Temlyakov, V.N.: Nonlinear approximation by trigonometric sums. J. Fourier Anal. Appl. 2 , 29-48 (1995) · Zbl 0886.42019
[8] 8. Dilworth, S.J., Kalton, N.J.: and Denka Kutzarova. On the existence of almost greedy bases in Banach spaces, Studia Math. 158 , 67-101 (2003) · Zbl 1056.46014
[9] 9. Dilworth, S.J., Kutzarova, D., Temlyakov, V.N.: Convergence of some Greedy Algorithms in Banach spaces. J. Fourier Anal. Appl. 8 , 489-505 (2002) · Zbl 1025.41021
[10] 10. Dilworth, S.J., Soto-Bajo, M., Temlyakov, V.N.: Quasi-greedy bases and Lebesgue-type inequalities. Stud. Math. 211 , 41-69 (2012) · Zbl 1264.41032
[11] 11. Garrigós, G., Hernández, E., Oikhberg, T.: Lebesgue type inequalities for quasi-greedy bases. Constr. Approx. 38 , 447-479 (2013) · Zbl 1284.41023
[12] 12. Gluskin, E.D.: Extremal properties of orthogonal parallelpipeds and their application to the geometry of Banach spaces. Math USSR Sbornik 64 , 85-96 (1989) · Zbl 0668.52002
[13] 13. Hackbusch, W.: Tensor Spaces and Numerical Tensor Calculus. Springer, Heidelberg (2012) · Zbl 1244.65061
[14] 14. Ismagilov, R.S.: Widths of sets in normed linear spaces and the approximation of functions by trigonometric polynomials. Uspekhi Mat. Nauk 29 , 161-178 (1974); English transl. in Russian Math. Surv. 29 (1974)
[15] 15. Kashin, B.S.: Widths of certain finite-dimensional sets and classes of smooth functions. Izv. AN SSSR 41 , 334-351 (1977); English transl. in Math. Izv. 11 (1977)
[16] 16. Kashin, B.S., Temlyakov, V.N.: On best · Zbl 0836.41008
[17] 17. Konyagin, S.V., Temlyakov, V.N.: A remark on greedy approximation in Banach spaces. East. J. Approx. 5 , 365-379 (1999) · Zbl 1084.46509
[18] 18. Livshitz, E.D., Temlyakov, V.N.: Sparse approximation and recovery by greedy algorithms, IEEE Trans. Inf. Theory 60 , 3989-4000 (2014). · Zbl 1360.94086
[19] 19. Maiorov, V.E.: Trigonometric diameters of the Sobolev classes · Zbl 0623.41024
[20] 20. Makovoz, Y.: On trigonometric · Zbl 0543.41027
[21] 21. Needell, D., Tropp, J.A.: CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmon. Anal. 26 , 301-321 (2009) · Zbl 1163.94003
[22] 22. Needell, D., Vershynin, R.: Uniform uncertainty principle and signal recovery via orthogonal matching pursuit. Found. Comput. Math. 9 , 317-334 (2009) · Zbl 1183.68739
[23] 23. Nielsen, M.: An example of an almost greedy uniformly bounded orthonormal basis for · Zbl 1146.46006
[24] 24. Romanyuk, A.S.: Best · Zbl 1066.42001
[25] 25. Shalev-Shwartz, S., Srebro, N., Zhang, T.: Trading accuracy for sparsity in optimization problems with sparsity constrains. SIAM J. Optim. 20 (6), 2807-2832 (2010) · Zbl 1208.68226
[26] 26. Schmidt, E.: Zur Theorie der linearen und nichtlinearen Integralgleichungen. I. Math. Ann. 63 , 433-476 (1907) · JFM 38.0377.02
[27] 27. Schneider, R., Uschmajew, A.: Approximation rates for the hierarchical tensor format in periodic Sobolev spaces. J. Complex. 30 , 56-71 (2014) · Zbl 1329.41033
[28] 28. Stechkin, S.B.: On absolute convergence of orthogonal series. Dokl. AN SSSR 102 , 37-40 (1955) (in Russian) · Zbl 0068.05104
[29] 29. Savu, D., Temlyakov, V.N.: Lebesgue-type inequalities for greedy approximation in Banach Spaces. IEEE Trans. Inf. Theory 58 , 1098-1106 (2013) · Zbl 1364.41006
[30] 30. Temlyakov, V.N.: Approximation of functions with bounded mixed derivative. Trudy MIAN 178 , 1-112 (1986). English transl. in Proc. Steklov Inst. Math. 1 (1989)
[31] 31. Temlyakov, V.N.: Approximation of periodic functions of several variables by bilinear forms. Izvestiya AN SSSR 50 , 137-155 (1986); English transl. in Math. USSR Izvestija 28 , 133-150 (1987) · Zbl 0607.42003
[32] 32. Temlyakov, V.N.: Estimates of the best bilinear approximations of functions of two variables and some of their applications. Mat. Sb. 134 , 93-107 (1987); English transl. in Math. USSR-Sb 62 , 95-109 (1989)
[33] 33. Temlyakov, V.N.: Estimates of best bilinear approximations of periodic functions. Trudy Mat. Inst. Steklov 181 , 250-267 (1988); English transl. Proc. Steklov Inst. Math. 4 , 275-293 (1989) · Zbl 0678.41026
[34] 34. Temlyakov, V.N.: Estimates of best bilinear approximations of functions and approximation numbers of integral operators. Matem. Zametki 51 , 125-134 (1992); English transl. in Math. Notes 51 , 510-517 (1992) · Zbl 0795.41021
[35] 35. Temlyakov, V.N.: Greedy algorithms with regard to multivariate systems with special structure. Constr. Approx. 16 , 399-425 (2000) · Zbl 0962.41007
[36] 36. Temlyakov, V.N.: Nonlinear Kolmogorov’s widths. Matem. Zametki 63 , 891-902 (1998)
[37] 37. Temlyakov, V.N.: Greedy algorithms in Banach spaces. Adv. Comput. Math. 14 , 277-292 (2001) · Zbl 0988.41022
[38] 38. Temlyakov, V.N.: Nonlinear method of approximation. Found. Comput. Math. 3 , 33-107 (2003) · Zbl 1039.41012
[39] 39. Temlyakov, V.N.: Greedy-type approximation in Banach Spaces and applications. Constr. Approx. 21 , 257-292 (2005) · Zbl 1070.41018
[40] 40. Temlyakov, V.N.: Greedy Approximation. Cambridge University Press (2011) · Zbl 1279.41001
[41] 41. Temlyakov, V.N.: Sparse approximation and recovery by greedy algorithms in Banach Spaces. Forum Math. Sigma 2 , e12, e26 (2014). · Zbl 1296.41030
[42] 42. Temlyakov, V.N.: An inequality for the entropy numbers and its application. J. Approx. Theory 173 , 110-121 (2013) · Zbl 1283.41021
[43] 43. Temlyakov, V.N.: Constructive sparse trigonometric approximation and other problems for functions with mixed smoothness. Math. Sbornik 206 , 131-160 (2015). · Zbl 1362.41009
[44] 44. Temlyakov, V.N.: Constructive sparse trigonometric approximation for functions with small mixed smoothness. · Zbl 1373.42009
[45] 45. Temlyakov, V.N., Yang, M., Ye, P.: Greedy approximation with regard to non-greedy bases. Adv. Comput. Math. 34 , 319-337 (2011) · Zbl 1217.41020
[46] 46. Wojtaszczyk, P.: Greedy algorithm for general biorthogonal systems. J. Approx. Theory 107 , 293-314 (2000) · Zbl 0974.65053
[47] 47. Zhang, T.: Sequential greedy approximation for certain convex optimization problems. IEEE Trans. Inf. Theory 49 (3), 682-691 (2003) · Zbl 1063.90040
[48] 48. Zhang, T.: Sparse recovery with orthogonal matching pursuit under RIP. IEEE Trans. Inf. Theory 57 , 6215-6221 (2011) · Zbl 1365.94091
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.