nach oben

Foundations of Computational Mathematics

Erschienen in:

01.08.2015

Adaptive Near-Optimal Rank Tensor Approximation for High-Dimensional Operator Equations

verfasst von: Markus Bachmayr, Wolfgang Dahmen

Erschienen in: Foundations of Computational Mathematics | Ausgabe 4/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider a framework for the construction of iterative schemes for operator equations that combine low-rank approximation in tensor formats and adaptive approximation in a basis. Under fairly general assumptions, we conduct a rigorous convergence analysis, where all parameters required for the execution of the methods depend only on the underlying infinite-dimensional problem, but not on a concrete discretization. Under certain assumptions on the rates for the involved low-rank approximations and basis expansions, we can also give bounds on the computational complexity of the iteration as a function of the prescribed target error. Our theoretical findings are illustrated and supported by computational experiments. These demonstrate that problems in very high dimensions can be treated with controlled solution accuracy.

Nächster Artikel Tight Tractability Results for a Model Second-Order Neumann Problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Alpert, B.: A class of bases in \(L^2\) for the sparse representation of integral operators. SIAM J. Math. Anal. 24(1), 246–262 (1991)

Bachmayr, M.: Adaptive low-rank wavelet methods and applications to two-electron Schrödinger equations. Ph.D. thesis, RWTH Aachen (2012)

Ballani, J., Grasedyck, L.: A projection method to solve linear systems in tensor format. Numer. Linear Algebra Appl. 20(1), 27–43 (2013)

Barinka, A.: Fast evaluation tools for adaptive wavelet schemes. Ph.D. thesis, RWTH Aachen (2005)

Beylkin, G., Mohlenkamp, M.J.: Numerical operator calculus in higher dimensions. PNAS 99(16), 10246–10251 (2002)

Beylkin, G., Mohlenkamp, M.J.: Algorithms for numerical analysis in high dimensions. SIAM J. Sci. Comput. 26(6), 2133–2159 (2005)

Cances, E., Ehrlacher, V., Lelievre, T.: Convergence of a greedy algorithm for high-dimensional convex nonlinear problems. Math. Models Methods Appl. Sci. 21(12), 2433–2467 (2011)

Cohen, A.: Numerical Analysis of Wavelet Methods, Studies in Mathematics and Its Applications, vol. 32. Elsevier, Amsterdam (2003)

Cohen, A., Dahmen, W., DeVore, R.: Adaptive wavelet methods for elliptic operator equations: Convergence rates. Math. Comput. 70(233), 27–75 (2001)

10.

Cohen, A., Dahmen, W., DeVore, R.: Adaptive wavelet methods II—beyond the elliptic case. Found. Comput. Math. 2(3), 203–245 (2002)

11.

Dahmen, W.: Wavelet and multiscale methods for operator equations. Acta Numer. 6, 55–228 (1997)

12.

DeVore, R., Petrova, G., Wojtaszczyk, P.: Approximation of functions of few variables in high dimensions. Constr. Approx. 33, 125–143 (2011)

13.

Dijkema, T.J., Schwab, C., Stevenson, R.: An adaptive wavelet method for solving high-dimensional elliptic PDEs. Constr. Approx. 30(3), 423–455 (2009)

14.

Falcó, A., Hackbusch, W.: On minimal subspaces in tensor representations. Found. Comput. Math. 12, 765–803 (2012)

15.

Falcó, A., Hackbusch, W., Nouy, A.: Geometric structures in tensor representations. Preprint 9/2013, Max Planck Institute of Mathematics in the Sciences, Leipzig (2013)

16.

Falcó, A., Nouy, A.: Proper generalized decomposition for nonlinear convex problems in tensor banach spaces. Numer. Math. 121, 503–530 (2012)

17.

Grasedyck, L.: Hierarchical singular value decomposition of tensors. SIAM J. Matrix Anal. Appl. 31(4), 2029–2054 (2010)

18.

Grasedyck, L., Kressner, D., Tobler, C.: A literature survey of low-rank tensor approximation techniques. GAMM-Mitt. 36, 53–78 (2013)

19.

Griebel, M., Harbrecht, H.: Approximation of two-variate functions: Singular value decomposition versus regular sparse grids. INS Preprint No. 1109, Universität Bonn (2011)

20.

Hackbusch, W.: Tensor Spaces and Numerical Tensor Calculus, Springer Series in Computational Mathematics, vol. 42. Springer, Berlin (2012)

21.

Hackbusch, W., Khoromskij, B., Tyrtyshnikov, E.: Approximate iterations for structured matrices. Numer. Math. 109, 119–156 (2008)

22.

Hackbusch, W., Kühn, S.: A new scheme for the tensor representation. J. Fourier Anal. Appl. 15(5), 706–722 (2009)

23.

Hitchcock, F.L.: Multiple invariants and generalized rank of a \(p\)-way matrix or tensor. J. Math. Phys. 7, 39–79 (1927)

24.

Khoromskij, B.N., Schwab, C.: Tensor-structured Galerkin approximation of parametric and stochastic elliptic PDEs. SIAM J. Sci. Comput. 33(1), 364–385 (2011)

25.

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

26.

Kressner, D., Tobler, C.: Preconditioned low-rank methods for high-dimensional elliptic PDE eigenvalue problems. Comput. Methods Appl. Math. 11(3), 363–381 (2011)

27.

Lathauwer, L.D., Moor, B.D., Vandewalle, J.: A multilinear singular value decomposition. SIAM J. Matrix Anal. Appl. 21(4), 1253–1278 (2000)

28.

Matthies, H.G., Zander, E.: Solving stochastic systems with low-rank tensor compression. Linear Algebra Appl. 436(10), 3819–3838 (2012)

29.

Metselaar, A.: Handling wavelet expansions in numerical methods. Ph.D. thesis, University of Twente (2002)

30.

Novak, E., Wozniakowski, H.: Approximation of infinitely differentiable multivariate functions is intractable. J. Complex. 25, 398–404 (2009)

31.

Oseledets, I., Tyrtyshnikov, E.: Breaking the curse of dimensionality, or how to use SVD in many dimensions. SIAM J. Sci. Comput. 31(5), 3744–3759 (2009)

32.

Oseledets, I., Tyrtyshnikov, E.: Tensor tree decomposition does not need a tree. Tech. Rep., RAS, Moscow 2009–08 (2009)

33.

Oseledets, I.V.: Tensor-train decomposition. SIAM J. Sci. Comput. 33(5), 2295–2317 (2011)

34.

Schneider, R., Uschmajew, A.: Approximation rates for the hierarchical tensor format in periodic Sobolev spaces. J. Complexity 30, 56–71 (2014)

35.

de Silva, V., Lim, L.H.: Tensor rank and the ill-posedness of the best low-rank approximation problem. SIAM J. Matrix Anal. Appl. 30(3), 1084–1127 (2008)

36.

Stevenson, R.: On the compressibility of operators in wavelet coordinates. SIAM J. Math. Anal. 35(5), 1110–1132 (2004)

37.

Tucker, L.R.: The extension of factor analysis to three-dimensional matrices. Contributions to Mathematical Psychology, pp. 109–127. Holt, Rinehart & Winston, New York (1964)

38.

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

39.

Uschmajew, A.: Well-posedness of convex maximization problems on Stiefel manifolds and orthogonal tensor product approximations. Numer. Math. 115, 309–331 (2010)

40.

Uschmajew, A.: Regularity of tensor product approximations to square integrable functions. Constr. Approx. 34, 371–391 (2011)

Titel: Adaptive Near-Optimal Rank Tensor Approximation for High-Dimensional Operator Equations
verfasst von: Markus Bachmayr
Wolfgang Dahmen
Publikationsdatum: 01.08.2015
Verlag: Springer US
Erschienen in: Foundations of Computational Mathematics / Ausgabe 4/2015
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-013-9187-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2015

Lagrange Interpolatory Subdivision Schemes in Chebyshev Spaces

Extensions of Gauss Quadrature Via Linear Programming

Tight Tractability Results for a Model Second-Order Neumann Problem

Finding Hidden Cliques of Size in Nearly Linear Time

Localization of Matrix Factorizations

A Well-Posedness Framework for Inpainting Based on Coherence Transport

Premium Partner