On some aspects of approximation of ridge functions. (English) Zbl 1316.65023
Summary: We present effective algorithms for uniform approximation of multivariate functions satisfying some prescribed inner structure. We extend, in several directions, the analysis of recovery of ridge functions \(f(x) = g(\langle a, x \rangle)\) as performed earlier by one of the authors and his coauthors. We consider ridge functions defined on the unit cube \([- 1, 1]^d\) as well as recovery of ridge functions defined on the unit ball from noisy measurements. We conclude with the study of functions of the type \(f(x) = g(\parallel a - x \parallel_{l_2^d}^2)\).
MSC:
| 65D15 | Algorithms for approximation of functions |
| 41A25 | Rate of convergence, degree of approximation |
Keywords:
ridge functions; high-dimensional function approximation; noisy measurements; compressed sensing; Dantzig selector; algorithm; approximation of multivariate functionsReferences:
| [1] | Baraniuk, R.; Davenport, M.; DeVore, R.; Wakin, M., A simple proof of the restricted isometry property for random matrices, Constr. Approx., 28, 253-263 (2008) · Zbl 1177.15015 |
| [3] | Buhmann, M. D.; Pinkus, A., Identifying linear combinations of ridge functions, Adv. Appl. Math., 22, 103-118 (1999) · Zbl 0931.41011 |
| [4] | Candès, E., Harmonic analysis of neural networks, Appl. Comput. Harmon. Anal., 6, 197-218 (1999) · Zbl 0931.68104 |
| [5] | Candès, E., The restricted isometry property and its implications for compressed sensing, C. R. Acad. Sci., Paris I, 346, 589-592 (2008) · Zbl 1153.94002 |
| [6] | Candès, E.; Donoho, D. L., Ridgelets: a key to higher-dimensional intermittency?, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 357, 2495-2509 (1999) · Zbl 1082.42503 |
| [7] | Candès, E.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52, 489-509 (2006) · Zbl 1231.94017 |
| [8] | Candès, E.; Tao, T., Decoding by linear programming, IEEE Trans. Inform. Theory, 51, 4203-4215 (2005) · Zbl 1264.94121 |
| [9] | Candès, E.; Tao, T., The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\), Ann. Stat., 35, 2313-2351 (2007) · Zbl 1139.62019 |
| [10] | Cohen, A.; Dahmen, W.; DeVore, R., Compressed sensing and best \(k\)-term approximation, J. Amer. Math. Soc., 22, 211-231 (2009) · Zbl 1206.94008 |
| [11] | Cohen, A.; Daubechies, I.; DeVore, R.; Kerkyacharian, G.; Picard, D., Capturing ridge functions in high dimensions from point queries, Constr. Approx., 35, 225-243 (2012) · Zbl 1318.62286 |
| [12] | Davenport, M. A.; Duarte, M. F.; Eldar, Y. C.; Kutyniok, G., Introduction to Compressed Sensing. Compressed Sensing, 1-64 (2012), Cambridge Univ. Press: Cambridge Univ. Press Cambridge |
| [13] | DeVore, R.; Lorentz, G. G., Constructive Approximation, Grundlehren der Mathematischen Wissenschaften, vol. 303 (1993), Springer: Springer Berlin · Zbl 0797.41016 |
| [14] | DeVore, R.; Petrova, G.; Wojtaszczyk, P., Instance-optimality in probability with an \(\ell_1\)-minimization decoder, Appl. Comput. Harmon. Anal., 27, 275-288 (2009) · Zbl 1177.94104 |
| [15] | DeVore, R.; Petrova, G.; Wojtaszczyk, P., Approximation of functions of few variables in high dimensions, Constr. Approx., 33, 125-143 (2011) · Zbl 1210.41009 |
| [16] | Donoho, D. L., Compressed sensing, IEEE Trans. Inform. Theory, 52, 1289-1306 (2006) · Zbl 1288.94016 |
| [17] | Fornasier, M.; Rauhut, H., Compressive sensing, (Scherzer, Otmar, Handbook of Mathematical Methods in Imaging (2011), Springer), 187-228 · Zbl 1259.94017 |
| [18] | Fornasier, M.; Schnass, K.; Vybíral, J., Learning functions of few arbitrary linear parameters in high dimensions, Found. Comput. Math., 12, 229-262 (2012) · Zbl 1252.65036 |
| [19] | Foucart, S.; Rauhut, H., A mathematical introduction to compressive sensing, (Applied and Numerical Harmonic Analysis (2013), Birkhäuser: Birkhäuser Boston) · Zbl 1315.94002 |
| [20] | Hemant, T.; Cevher, V., Active learning of multi-index function models, (Advances in Neural Information Processing Systems 25 (2012)), 1475-1483, available at http://books.nips.cc/papers/files/nips25/NIPS2012_0701.pdf |
| [21] | Ledoux, M., (The Concentration of Measure Phenomenon. The Concentration of Measure Phenomenon, Mathematical Surveys and Monographs, vol. 89 (2001), American Mathematical Society: American Mathematical Society Providence) · Zbl 0995.60002 |
| [22] | Lin, V. Ya.; Pinkus, A., Fundamentality of ridge functions, J. Approx. Theory, 75, 295-311 (1993) · Zbl 0813.41017 |
| [23] | Litvak, A. E.; Pajor, A.; Rudelson, M.; Tomczak-Jaegermann, N., Smallest singular value of random matrices and geometry of random polytopes, Adv. Math., 195, 491-523 (2005) · Zbl 1077.15021 |
| [24] | Logan, B. P.; Shepp, L. A., Optimal reconstruction of a function from its projections, Duke Math. J., 42, 645-659 (1975) · Zbl 0343.41020 |
| [26] | Novak, E.; Woźniakowski, H., (Tractability of Multivariate Problems, Volume I: Linear Information. Tractability of Multivariate Problems, Volume I: Linear Information, EMS Tracts in Mathematics, vol. 6 (2008), Eur. Math. Soc. Publ. House: Eur. Math. Soc. Publ. House Zürich) · Zbl 1156.65001 |
| [27] | Novak, E.; Woźniakowski, H., Approximation of infinitely differentiable multivariate functions is intractable, J. Complexity, 25, 398-404 (2009) · Zbl 1180.41031 |
| [28] | Novak, E.; Woźniakowski, H., (Tractability of Multivariate Problems, Volume II: Standard Information for Functionals. Tractability of Multivariate Problems, Volume II: Standard Information for Functionals, EMS Tracts in Mathematics, vol. 12 (2010), Eur. Math. Soc. Publ. House: Eur. Math. Soc. Publ. House Zürich) · Zbl 1241.65025 |
| [29] | Novak, E.; Woźniakowski, H., (Tractability of Multivariate Problems, Volume III: Standard Information for Operators. Tractability of Multivariate Problems, Volume III: Standard Information for Operators, EMS Tracts in Mathematics, vol. 18 (2012), Eur. Math. Soc. Publ. House: Eur. Math. Soc. Publ. House Zürich) · Zbl 1359.65003 |
| [30] | Pinkus, A., Approximating by ridge functions, (Surface Fitting and Multiresolution Methods (1997)), 279-292 · Zbl 0937.65016 |
| [31] | Pinkus, A., Approximation theory of the MLP model in neural networks, Acta Numer., 8, 143-195 (1999) · Zbl 0959.68109 |
| [33] | Wojtaszczyk, P., Complexity of approximation of functions of few variables in high dimensions, J. Complexity, 27, 141-150 (2011) · Zbl 1343.65015 |
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.
