Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

On decompositions of multivariate functions


Authors: F. Y. Kuo, I. H. Sloan, G. W. Wasilkowski and H. Wozniakowski
Journal: Math. Comp. 79 (2010), 953-966
MSC (2000): Primary 41A63, 41A99
DOI: https://doi.org/10.1090/S0025-5718-09-02319-9
Published electronically: November 20, 2009
MathSciNet review: 2600550
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present formulas that allow us to decompose a function $ f$ of $ d$ variables into a sum of $ 2^d$ terms $ f_{\mathbf{u}}$ indexed by subsets $ \mathbf{u}$ of $ \{1,\ldots,d\}$, where each term $ f_{\mathbf{u}}$ depends only on the variables with indices in $ \mathbf{u}$. The decomposition depends on the choice of $ d$ commuting projections $ \{P_j\}_{j=1}^d$, where $ P_j(f)$ does not depend on the variable $ x_j$. We present an explicit formula for $ f_{\mathbf{u}}$, which is new even for the ANOVA and anchored decompositions; both are special cases of the general decomposition. We show that the decomposition is minimal in the following sense: if $ f$ is expressible as a sum in which there is no term that depends on all of the variables indexed by the subset $ \mathbf{z}$, then, for every choice of $ \{P_j\}_{j=1}^d$, the terms $ f_{\mathbf{u}}=0$ for all subsets $ \mathbf{u}$ containing  $ \mathbf{z}$. Furthermore, in a reproducing kernel Hilbert space setting, we give sufficient conditions for the terms $ f_{\mathbf{u}}$ to be mutually orthogonal.


References [Enhancements On Off] (What's this?)

  • 1. N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc., 68, 337-404 (1950). MR 0051437 (14:479c)
  • 2. R. E. Caflisch, W. Morokoff, and A. Owen, Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension, J. Comput. Finance 1, 27-46 (1997).
  • 3. J. Dick and F. Pillichshammer, Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules, J. Complexity 23, 436-453 (2007). MR 2372007 (2008m:65067)
  • 4. J. Dick, I. H. Sloan, X. Wang, and H. Woźniakowski, Liberating the weights, J. Complexity 20, 593-623 (2004). MR 2086942 (2005h:65008)
  • 5. M. Griebel, Sparse grids and related approximation schemes for higher dimensional problems, Foundations of Computational Mathematics, Santander 2005 (L. M. Pardo, A. Pinkus, E. Süli, M. J. Todd, eds.), Cambridge University Press, London, 2006, pp. 106-161. MR 2277104 (2007k:65206)
  • 6. M. Griebel, F. Y. Kuo and I. H. Sloan, The smoothing effect of the ANOVA decomposition, submitted.
  • 7. F. J. Hickernell, I. H. Sloan, and G. W. Wasilkowski, On tractability of weighted integration over bounded and unbounded regions in $ \mathbb{R}^s$, Math. Comp., 73, 1885-1901 (2004). MR 2059741 (2005c:65018)
  • 8. F. J. Hickernell, I. H. Sloan, and G. W. Wasilkowski, The strong tractability of multivariate integration using lattice rules, Monte Carlo and Quasi-Monte Carlo Methods 2002 (H. Niederreiter, ed.), Springer-Verlag, Berlin, 2004, pp. 259-273. MR 2076938
  • 9. F. Y. Kuo and I. H. Sloan, Lifting the curse of dimensionality, Notices Amer. Math. Soc. 52, 1320-1329 (2005). MR 2183869 (2006j:65061)
  • 10. F. Y. Kuo, I. H. Sloan, G. W. Wasilkowski, and H. Woźniakowski, Liberating the dimension, submitted.
  • 11. G. Li, J. Schoendorf, T.-S. Ho, and H. Rabitz, Multicut-HDMR with an application to an ionospheric model, J. Comput. Chem. 25, 1149-1156 (2004).
  • 12. G. Li, J. Hu, S.-W. Wang, P. G. Georgopoulos, J. Schoendorf, and H. Rabitz, Random sampling-high dimensional model representation (RS-HDMR) and orthogonality of its different order component functions, J. Phys. Chem. A 110, 2474-2485 (2006).
  • 13. G. Li and H. Rabitz, Ratio control variate method for efficiently determining high-dimensional model representations, J. Comput. Chem. 27, 1112-1118 (2006).
  • 14. R. Liu and A. Owen, Estimating mean dimensionality of analysis of variance decompositions, J. Amer. Statist. Assoc. 101, 712-721 (2006). MR 2281247
  • 15. H. Rabitz, O. F. Alis, J. Shorter and K. Shim, Efficient input-output model representation, Comput. Phys. Commun. 117, 11-20 (1999).
  • 16. I. H. Sloan, X. Wang, and H. Woźniakowski, Finite-order weights imply tractability of multivariate integration, J. Complexity 20, 46-74 (2004). MR 2031558 (2004j:65034)
  • 17. I. M. Sobol$ '$, Multidimensional Quadrature Formulas and Haar Functions, Nauka, Moscow, 1969 (in Russian). MR 0422968 (54:10952)
  • 18. I. M. Sobol$ '$, Sensitivity estimates for nonlinear mathematical models, Matematicheskoe Modelirovanie, 1990, V. 2, N 1, 112-118 (in Russian), English translation in: Mathematical Modeling and Computational Experiment, 407-414 (1993). MR 1335161 (96a:65010)
  • 19. I. M. Sobol$ '$, Theorems and examples on high dimensional model representation, Reliability Engrg. and System Safety 79, 187-193 (2003).
  • 20. G. Wahba, Spline Models for Observational Data, SIAM-NSF Regional Conference Series in Appl. Math., Vol. 59, SIAM, Philadelphia, 1990. MR 1045442 (91g:62028)
  • 21. X. Wang and K.-T. Fang, Effective dimension and quasi-Monte Carlo integration, J. Complexity 19, 101-124 (2003). MR 1966664 (2003m:62016)
  • 22. X. Wang and I. H. Sloan, Brownian bridge and principal component analysis, IMA J. Numer. Anal. 27, 631-654 (2007). MR 2371825 (2009a:62248)
  • 23. G. W. Wasilkowski and H. Woźniakowski, Tractability of approximation and integration for weighted tensor product problems over unbounded domains, Monte Carlo and Quasi-Monte Carlo Methods 2000, (K.-T. Fang, F. J. Hickernell, H. Niederreiter, eds.), Springer, Berlin, 2002, pp. 497-522. MR 1958877 (2004b:65222)
  • 24. G. W. Wasilkowski and H. Woźniakowski, Finite-order weights imply tractability of linear multivariate problems, J. Approx. Theory 130, 57-77 (2004). MR 2086810 (2005d:41048)
  • 25. G. W. Wasilkowski and H. Woźniakowski, Polynomial-time Algorithms for Multivariate Linear Problems with Finite-order Weights: Worst Case Setting, Found. Comput. Math., 5, 451-491 (2005). MR 2189546 (2006i:65037)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 41A63, 41A99

Retrieve articles in all journals with MSC (2000): 41A63, 41A99


Additional Information

F. Y. Kuo
Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia
Email: f.kuo@unsw.edu.au

I. H. Sloan
Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia
Email: i.sloan@unsw.edu.au

G. W. Wasilkowski
Affiliation: Department of Computer Science, University of Kentucky, Lexington, Kentucky 40506
Email: greg@cs.uky.edu

H. Wozniakowski
Affiliation: Department of Computer Science, Columbia University, New York, New York 10027, and Institute of Applied Mathematics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland
Email: henryk@cs.columbia.edu

DOI: https://doi.org/10.1090/S0025-5718-09-02319-9
Received by editor(s): May 2, 2008
Received by editor(s) in revised form: October 16, 2008, and February 12, 2009
Published electronically: November 20, 2009
Article copyright: © Copyright 2009 American Mathematical Society

American Mathematical Society