Skip to main content
SpringerLink
Log in

Adaptive Cross Approximation of Multivariate Functions

  • Published:
Constructive Approximation Aims and scope

Abstract

In this article we present and analyze a new scheme for the approximation of multivariate functions (d=3,4) by sums of products of univariate functions. The method is based on the Adaptive Cross Approximation (ACA) initially designed for the approximation of bivariate functions. To demonstrate the linear complexity of the schemes, we apply it to large-scale multidimensional arrays generated by the evaluation of functions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Babaev, M.-B.A.: Best approximation by bilinear forms. Mat. Zametki 46(2), 21–33 (1989)

    MathSciNet  Google Scholar 

  2. Babaev, M.-B.A.: Exact annihilators and their applications in approximation theory. Trans. Acad. Sci. Azerb. Ser. Phys.-Tech. Math. Sci. 20(1), 17–24 (2000)

    MathSciNet  MATH  Google Scholar 

  3. Bebendorf, M.: Approximation of boundary element matrices. Numer. Math. 86(4), 565–589 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bebendorf, M.: In: Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems. Lecture Notes in Computational Science and Engineering (LNCSE), vol. 63. Springer, Berlin (2008). ISBN 978-3-540-77146-3

    Google Scholar 

  5. Bebendorf, M., Grzhibovskis, R.: Accelerating Galerkin BEM for linear elasticity using adaptive cross approximation. Math. Methods Appl. Sci. 29, 1721–1747 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bebendorf, M., Rjasanow, S.: Adaptive low-rank approximation of collocation matrices. Computing 70(1), 1–24 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  7. Beylkin, G., Monzón, L.: On approximation of functions by exponential sums. Appl. Comput. Harmon. Anal. 19(1), 17–48 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  8. Braess, D., Hackbusch, W.: Approximation of 1/x by exponential sums in [1,∞). IMA J. Numer. Anal. 25(4), 685–697 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  9. Braess, D., Hackbusch, W.: On the efficient computation of high-dimensional integrals and the approximation by exponential sums. Technical Report 3, Max-Planck-Institute MiS (2009)

  10. Bungartz, H.-J., Griebel, M.: Sparse grids. Acta Numer. 13, 147–269 (2004)

    Article  MathSciNet  Google Scholar 

  11. Carroll, J. Douglas, Chang, J.-J.: Analysis of individual differences in multidimensional scaling via an n-way generalization of “Eckart-Young” decomposition. Psychometrika 35(3), 283–319 (1970)

    Article  MATH  Google Scholar 

  12. Eckart, G., Young, G.: The approximation of one matrix by another of lower rank. Psychometrika 1, 211–218 (1936)

    Article  Google Scholar 

  13. Espig, M.: Effiziente Bestapproximation mittels Summen von Elementartensoren in hohen Dimensionen. PhD thesis, University of Leipzig (2007)

  14. Flad, H.-J., Khoromskij, B.N., Savostyanov, D.V., Tyrtyshnikov, E.E.: Verification of the cross 3D algorithm on quantum chemistry data. Russ. J. Numer. Anal. Math. Model. 23(4), 329–344 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  15. Hackbusch, W., Kühn, S.: A new scheme for the tensor representation. Technical Report 2, Max-Planck-Institute MiS (2009)

  16. Hoeffding, W.: A class of statistics with asymptotically normal distribution. Ann. Math. Stat. 19, 293–325 (1948)

    Article  MathSciNet  MATH  Google Scholar 

  17. Ibraghimov, I.: Application of the three-way decomposition for matrix compression. Numer. Linear Algebra Appl. 9(6–7), 551–565 (2002) Preconditioned robust iterative solution methods, PRISM ’01 (Nijmegen)

    Article  MathSciNet  MATH  Google Scholar 

  18. Khoromskij, B.N.: Structured rank-(r 1,…,r d ) decomposition of function-related tensors in ℝd. Comput. Methods Appl. Math. 6(2), 194–220 (2006) (electronic)

    MathSciNet  MATH  Google Scholar 

  19. Khoromskij, B.N., Khoromskaia, V.: Multigrid accelerated tensor approximation of function related multidimensional arrays. SIAM J. Sci. Comput. 31(4), 3002–3026 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  20. Kolda, T.G.: A counterexample to the possibility of an extension of the Eckart-Young low-rank approximation theorem for the orthogonal rank tensor decomposition. SIAM J. Matrix Anal. Appl. 24(3), 762–767 (2003) (electronic)

    Article  MathSciNet  MATH  Google Scholar 

  21. Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51(3), 455–500 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kroonenberg, P.M., de Leeuw, J.: Principal component analysis of three-mode data by means of alternating least squares algorithms. Psychometrika 45(1), 69–97 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  23. Oseledets, I.V., Savostianov, D.V., Tyrtyshnikov, E.E.: Tucker dimensionality reduction of three-dimensional arrays in linear time. SIAM J. Matrix Anal. Appl. 30(3), 939–956 (2008)

    Article  MathSciNet  Google Scholar 

  24. Oseledets, I.V., Tyrtyshnikov, E.E.: TT-cross approximation for multidimensional arrays. Technical Report 5, Institute of Numerical Mathematics, Russian Academy of Sciences (June 2009)

  25. Pospelov, V.V.: Approximation of functions of several variables by products of functions of a single variable. Akad. Nauk SSSR Inst. Prikl. Mat. 32, 75 (1978)

    MathSciNet  Google Scholar 

  26. Rassias, T.M., Šimša, J.: Finite Sums Decompositions in Mathematical Analysis. Pure and Applied Mathematics. (New York). Wiley, Chichester (1995). A Wiley–Interscience Publication

    MATH  Google Scholar 

  27. Schmidt, E.: Zur Theorie der linearen und nichtlinearen Integralgleichungen. Math. Ann. 63(4), 433–476 (1907)

    Article  MathSciNet  Google Scholar 

  28. Schneider, J.: Error estimates for two-dimensional cross approximation. Technical Report 5, Max-Planck-Institute MiS (2009)

  29. Šimša, J.: The best L 2-approximation by finite sums of functions with separable variables. Aeq. Math. 43(23), 248–263 (1992)

    MATH  Google Scholar 

  30. ten Berge, J.M.F., de Leeuw, J., Kroonenberg, P.M.: Some additional results on principal components analysis of three-mode data by means of alternating least squares algorithms. Psychometrika 52(2), 183–191 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  31. Tucker, L.R.: Some mathematical notes on three-mode factor analysis. Psychometrika 31, 279–311 (1966)

    Article  MathSciNet  Google Scholar 

  32. Zenger, C.: Sparse grids. In: Hackbusch, W. (ed.) Parallel Algorithms for Partial Differential Equations. Notes on Numerical Fluid Mechanics, vol. 31, pp. 241–251. Vieweg, Wiesbaden (1991)

    Google Scholar 

  33. Zhang, T., Golub, G.H.: Rank-one approximation to high order tensors. SIAM J. Matrix Anal. Appl. 23(2), 534–550 (2001) (electronic)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Numerische Simulation, Rheinische Friedrich-Wilhelms-Universität Bonn, Wegelerstrasse 6, 53115, Bonn, Germany

    M. Bebendorf

Authors
  1. M. Bebendorf
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. Bebendorf.

Additional information

Communicated by Wolfgang Dahmen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bebendorf, M. Adaptive Cross Approximation of Multivariate Functions. Constr Approx 34, 149–179 (2011). https://doi.org/10.1007/s00365-010-9103-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00365-010-9103-x

Keywords

Mathematics Subject Classification (2000)

Search

Navigation