Abstract
We investigate a problem of approximate non-linear sampling recovery of functions on the interval \(\mathbb I:=[0,1]\) expressing the adaptive choice of n sampled values of a function to be recovered, and of n terms from a given family of functions Φ. More precisely, for each function f on \(\mathbb I\), we choose a sequence \(\xi = \{\xi^s\}_{s =1}^n\) of n points in \(\mathbb I\), a sequence \(a = \{a_s\}_{s =1}^n\) of n functions defined on \(\mathbb R^n\) and a sequence \(\Phi_n = \{\varphi_{k_s}\}_{s =1}^n\) of n functions from a given family Φ. By this choice we define a (non-linear) sampling recovery method so that f is approximately recovered from the n sampled values f(ξ 1), f(ξ 2),..., f(ξ n), by the n-term linear combination
In searching an optimal sampling method, we study the quantity
where the infimum is taken over all sequences \(\xi = \{\xi^s\}_{s =1}^n\) of n points, \(a = \{a_s\}_{s =1}^n\) of n functions defined on \(\mathbb R^n\), and \(\Phi_n= \{\varphi_{k_s}\}_{s =1}^n\) of n functions from Φ. Let \(U^\alpha_{p,\theta}\) be the unit ball in the Besov space \(B^\alpha_{p,\theta},\) and M the set of centered B-spline wavelets
which do not vanish identically on \(\mathbb I\), where N r is the B-spline of even order r = 2ρ ≥ [α] + 1 with knots at the points 0,1,...,r. For \(1 \le p,q \le \infty, \ 0 < \theta \le \infty\) and α > 1, we proved the following asymptotic order
An asymptotically optimal non-linear sampling recovery method S * for \(\nu_n(U^\alpha_{p,\theta},{\bf M})_q\) is constructed by using a quasi-interpolant wavelet representation of functions in the Besov space in terms of the B-splines M k,s and the associated equivalent discrete quasi-norm of the Besov space. For 1 ≤ p < q ≤ ∞ , the asymptotic order of this asymptotically optimal sampling non-linear recovery method is better than the asymptotic order of any linear sampling recovery method or, more generally, of any non-linear sampling recovery method of the form R(H,ξ,f): = H(f(ξ 1),...,f(ξ n)) with a fixed mapping \(H:\mathbb R^n \to C(\mathbb I)\) and n fixed points \(\xi\!=\! \{\xi^s\}_{s \!=\!1}^n.\)
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Besov, O.V., Il’in, V.P., Nikol’skii, S.M.: Integral Representations of Functions and Embedding Theorems. V.H. Winston, Washington, D.C (1978)
Butzer, P.L., Schmidt, M.: Central factorial numbers and their role in finite difference calculus and approximation. In: Szabados, J., Tandory, K. (eds.) Approximation Theory. CMSB, vol. 58. NH, pp. 127–150 (1990)
Butzer, P.L., Schmidt, M., Stark, E.L., Vogt, L.: Central factorial numbers, their main properties and some applications. Numer. Funct. Anal. Optim. 10, 419–488 (1989)
Chui, C.K.: An Introduction to Wavelets. Academic, New York (1992)
Chui, C.K., Diamond, H.: A natural formulation of quasi-interpolation by multivariate splines. Proc. Amer. Math. Soc. 99, 643–646 (1987)
de Boor, C., Fix, G.J.: Spline approximation by quasiinterpolants. J. Approx. Theory 8, 19–45 (1973)
Dahlke, S., Novak, E., Sickel, W.: Optimal approximation of elliptic problems by linear and nonlinear mappings I. Complexity 22, 29–49 (2006)
Dahlke, S., Novak, E., Sickel, W.: Optimal approximation of elliptic problems by linear and nonlinear mappings II. Complexity 22, 549–603 (2006)
de Boor, C., Höllig, K., Riemenschneider, S.: Box Spline. Springer, Berlin (1993)
DeVore, R.A.: Nonlinear approximation. Acta Numer. 7, 51–150 (1998)
DeVore, R.A., Lorentz, G.G.: Constructive Approximation. Springer, New York (1993)
DeVore, R.A., Popov, V.A.: Interpolation of Besov spaces. Trans. Amer. Math. Soc. 305, 397–413 (1988)
Dung, D.: On interpolation recovery for periodic functions. In: Koshi, S. (ed.) Functional Analysis and Related Topics, pp. 224–233. World Scientific, Singapore (1991)
Dung, D.: On nonlinear n-widths and n-term approximation. Vietnam Math. J. 26, 165–176 (1998)
Dung, D.: Continuous algorithms in n-term approximation and non-linear n-widths. J. Approx. Theory 102, 217–242 (2000)
Dung, D.: Using quasi-interpolant wavelet representations for non-linear sampling recovery. Vietnam Math. J. 35, 331–338 (2007)
Kydryatsev, S.N.: The best accuracy of reconstruction of finitely smooth functions from their values at a given number of points. Izv. Math. 62, 19–53 (1998)
Nikol’skii, S.: Approximation of Functions of Several Variables and Embedding Theorems. Springer, Berlin (1975)
Novak, E.: Deterministic and Stochastic Error Bounds in Numerical Analysis. Lecture Notes in Mathematics, vol. 1349. Springer, Berlin (1988)
Novak, E., Triebel, H.: Function spaces in Lipschitz domains and optimal rates of convergence for sampling. Constr. Approx. 23, 325–350 (2006)
Sablonnière, P.: Recent progress on univariate and multivariate polynomial and spline quasi-interpolants. In: de Bruin, M.G., Mache, D.H., Szabados, J. (eds.) Trends and applications in constructive approximation. Int. Ser. Numer. Math. 151, 229–245 (2005)
Schoenberg, I.J.: Cardinal spline interpolation. CBMS-NSF Regional Conferences Series in Applied Mathematics, vol. 12. SIAM, Philadelphia (1973)
Temlyakov, V.: Approximation of Periodic Functions. Nova Science, New York (1993)
Temlyakov, V.: Nonlinear methods of approximation. Fund. Comput. Math. 3, 33–107 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Juan Manuel Peña.
Rights and permissions
About this article
Cite this article
Dũng, D. Non-linear sampling recovery based on quasi-interpolant wavelet representations. Adv Comput Math 30, 375–401 (2009). https://doi.org/10.1007/s10444-008-9074-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10444-008-9074-7
Keywords
- Non-linear sampling recovery
- Quasi-interpolant wavelet representation
- Adaptive choice
- B-spline
- Besov space