Capturing ridge functions in high dimensions from point queries. (English) Zbl 1318.62286

Summary: Constructing a good approximation to a function of many variables suffers from the “curse of dimensionality”. Namely, functions on \({\mathbb{R}}^{N}\) with smoothness of order \(s\) can in general be captured with accuracy at most \(O(n^{-s/N})\) using linear spaces or nonlinear manifolds of dimension \(n\). If \(N\) is large and \(s\) is not, then \(n\) has to be chosen inordinately large for good accuracy. The large value of \(N\) often precludes reasonable numerical procedures. On the other hand, there is the common belief that real world problems in high dimensions have as their solution, functions which are more amenable to numerical recovery. This has led to the introduction of models for these functions that do not depend on smoothness alone but also involve some form of variable reduction. In these models it is assumed that, although the function depends on \(N\) variables, only a small number of them are significant. Another variant of this principle is that the function lives on a low dimensional manifold. Since the dominant variables (respectively the manifold) are unknown, this leads to new problems of how to organize point queries to capture such functions. The present paper studies where to query the values of a ridge function \(f(x) = g(a \cdot x)\) when both \(a \in {\mathbb{R}}^{N}\) and \(g \in C[0,1]\) are unknown. We establish estimates on how well \(f\) can be approximated using these point queries under the assumptions that \(g \in C^{s}[0,1]\). We also study the role of sparsity or compressibility of \(a\) in such query problems.


62M45 Neural nets and related approaches to inference from stochastic processes
62G08 Nonparametric regression and quantile regression
65D05 Numerical interpolation
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
Full Text: DOI


[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 · doi:10.1007/s00365-007-9003-x
[2] Belkin, M., Niyogi, P.: Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput. 15, 1373–1396 (2003) · Zbl 1085.68119 · doi:10.1162/089976603321780317
[3] Candès, E., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59, 1207–1223 (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124
[4] Chi, Z.: On 1-regularized estimation for nonlinear models that have sparse underlying linear structures. ArXiv e-prints, Nov. (2009)
[5] Cohen, A., Dahmen, W., DeVore, R.: Compressed sensing and best k term approximation. J. Am. Math. Soc. 22, 211–231 (2009) · Zbl 1206.94008 · doi:10.1090/S0894-0347-08-00610-3
[6] Cohen, A., DeVore, R., Schwab, C.: Convergence rates of best n term Galerkin approximations for a class of elliptic SPDEs. Found. Comput. Math. 10(6), 615–646 (2010) · Zbl 1206.60064 · doi:10.1007/s10208-010-9072-2
[7] Coifman, R., Maggioni, M.: Diffusion wavelets. Appl. Comput. Harmon. Anal. 21(1), 53–94 (2006) · Zbl 1095.94007 · doi:10.1016/j.acha.2006.04.004
[8] DeVore, R.: Nonlinear approximation. Acta Numer. 7, 51–150 (1998) · Zbl 0931.65007 · doi:10.1017/S0962492900002816
[9] DeVore, R., Lorentz, G.G.: Constructive Approximation. Grundlehren der mathematischen Wissenschaften, vol. 303. Springer, New York (1993) · Zbl 0797.41016
[10] DeVore, R., Petrova, G., Wojtaszczyk, P.: Instance optimality in probability with an 1-minimization decoder. Appl. Comput. Harmon. Anal. 27, 275–288 (2009) · Zbl 1177.94104 · doi:10.1016/j.acha.2009.05.001
[11] DeVore, D., Petrova, G., Wojtaszczyk, P.: Approximating functions of few variables in high dimensions. Constr. Approx. 33, 125–143 (2011) · Zbl 1210.41009 · doi:10.1007/s00365-010-9105-8
[12] Foucart, S., Pajor, A., Rauhut, H., Ullrich, T.: The Gelfand widths of p balls for 0<p. Preprint · Zbl 1204.41019
[13] Gaiffas, S., Lecue, G.: Optimal rates and adaptation in the single-index model using aggregation. Electron. J. Stat. 1, 538 (2007) · Zbl 1320.62091 · doi:10.1214/07-EJS077
[14] Golubev, G.K.: Asymptotically minimax estimation of a regression function in an additive model. Probl. Pereda. Inf. 28, 101–112 (1992)
[15] Haupt, J., Castro, R., Nowak, R.: Distilled sensing: Adaptive sampling for sparse detection and estimation. Preprint (2010) · Zbl 1365.94177
[16] Juditsky, A., Lepski, O., Tsybakov, A.: Nonparametric estimation of composite functions. Ann. Stat. 37(3), 1360–1404 (2009) · Zbl 1160.62030 · doi:10.1214/08-AOS611
[17] Li, K.-C.: Sliced inverse regression for dimension reduction. J. Am. Stat. Assoc. 86(414), 316–327 (1991) · Zbl 0742.62044 · doi:10.1080/01621459.1991.10475035
[18] Lorentz, G.G., Von Golitschek, M., Makovoz, Y.: Constructive Approximation–Advances Problems. Grundlehren der mathematischen Wissenschaften, vol. 304. Springer, New York (1996) · Zbl 0910.41001
[19] Maathuis, M.H., Kalisch, M., Buhlmann, P.: Estimating high-dimensional intervention effects from observational data. Ann. Stat. 37, 3133–3164 (2009) · Zbl 1191.62118 · doi:10.1214/09-AOS685
[20] Stone, C.J.: Additive regression and other nonparametric models. Ann. Stat. 13, 689–705 (1985) · Zbl 0605.62065 · doi:10.1214/aos/1176349548
[21] Traub, J., Wozniakowski, H.: A General Theory of Optimal Algorithms. Academic Press, New York (1980) · Zbl 0441.68046
[22] Traub, J., Wassilkowski, G., Wozniakowski, H.: Information-Based Complexity. Academic Press, New York (1988)
[23] Wainwright, M.J.: Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting. IEEE Trans. Inf. Theory 55, 5728–5741 (2009) · Zbl 1367.94106 · doi:10.1109/TIT.2009.2032816
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.