Published 6 issues per year
ISSN Print: 2152-5080
ISSN Online: 2152-5099
Indexed in
EFFICIENT APPROXIMATION OF HIGH-DIMENSIONAL EXPONENTIALS BY TENSOR NETWORKS
ABSTRACT
In this work a general approach to compute a compressed representation of the exponential exp (h) of a high-dimensional function h is presented. Such exponential functions play an important role in several problems in uncertainty quantification, e.g., the approximation of log-normal random fields or the evaluation of Bayesian posterior measures. Usually, these high-dimensional objects are numerically intractable and can only be accessed pointwise in sampling methods. In contrast, the proposed method constructs a functional representation of the exponential by exploiting its nature as a solution of a partial differential equation. The application of a Petrov−Galerkin scheme to this equation provides a tensor train representation of the solution for which we derive an efficient and reliable a posteriori error estimator. This estimator can be used in conjunction with any approximation method and the differential equation may be adapted such that the error estimates are equivalent to a problem-related norm. Numerical experiments with log-normal random fields and Bayesian likelihoods illustrate the performance of the approach in comparison to other recent low-rank representations for the respective applications. Although the present work considers only a specific differential equation, the presented method can be applied in a more general setting. We show that the proposed method can be used to compute compressed representations of φ(h) for any holonomic function φ.
-
Le Maitre, O. and Knio, O.M., Spectral Methods for Uncertainty Quantification: With Applications to Computational Fluid Dynamics (Scientific Computation), Berlin: Springer, 2010.
-
Ghanem, R.G. and Spanos, P., Stochastic Finite Elements: A Spectral Approach, Berlin: Springer, 1990.
-
Eigel, M., Gittelson, C.J., Schwab, C., and Zander, E., Adaptive Stochastic Galerkin FEM, Comput. Methods Appl. Mech. Eng., 270:247-269,2014.
-
Eigel, M., Gittelson, C., Schwab, C., and Zander, E., A Convergent Adaptive Stochastic Galerkin Finite Element Method with Quasi-Optimal Spatial Meshes, Tech. Rep. 2014-01, Seminar for Applied Mathematics, ETH Zurich, Switzerland, 2014.
-
Stuart, A.M., Inverse Problems: A Bayesian Perspective, Acta Numer., 19:451-559, 2010.
-
Kaipio, J. and Somersalo, E., Statistical and Computational Inverse Problems, Vol. 160, Berlin: Springer Science & Business Media, 2006.
-
Farchmin, N., Hammerschmidt, M., Schneider, P.I., Wurm, M., Bodermann, B., Bar, M., and Heidenreich, S., Efficient Bayesian Inversion for Shape Reconstruction of Lithography Masks, J. Micro/Nanolithog. MEMS MOEMS, 19(02):1, 2020.
-
Mo, S., Zabaras, N., Shi, X., and Wu, J., Deep Autoregressive Neural Networks for High-Dimensional Inverse Problems in Groundwater Contaminant Source Identification, Water Resour. Res., 55(5):3856-3881, 2019.
-
Lassila, T., Manzoni, A., Quarteroni, A., and Rozza, G., A Reduced Computational and Geometrical Framework for Inverse Problems in Hemodynamics, Int. J. Numer. Methods Biomed. Eng., 29(7):741-776, 2013.
-
Dolgov, S., Anaya-Izquierdo, K., Fox, C., and Scheichl, R., Approximation and Sampling of Multivariate Probability Distributions in the Tensor Train Decomposition, Stat. Comput, 30(3):603-625,2019.
-
Eigel, M., Gruhlke, R., and Marschall, M., Low-Rank Tensor Reconstruction of Concentrated Densities with Application to Bayesian Inversion, Stat. Comput, 32:27, 2022.
-
Mugler, A., VerallgemeinertesPolynomielles Chaos zurLosung Stationarer Diffusionsprobleme mitZufalligenKoeffizienten, PhD, BTU Cottbus-Senftenberg, 2013.
-
Grasedyck, L., Kressner, D., and Tobler, C., A Literature Survey of Low-Rank Tensor Approximation Techniques, GAMM Mitt., 36(1):53-78, 2013.
-
Oseledets, I.V. and Tyrtyshnikov, E.E., Breaking the Curse of Dimensionality, or How to Use SVD in Many Dimensions, SIAMJ. Sci. Comput., 31(5):3744-3759, 2009.
-
Eigel, M., Marschall, M., Pfeffer, M., and Schneider, R., Adaptive Stochastic Galerkin FEM for Lognormal Coefficients in Hierarchical Tensor Representations, Numer. Math, 145(3):655-692, 2020.
-
Oseledets, I. and Tyrtyshnikov, E., TT-Cross Approximation for Multidimensional Arrays, Linear Algebra Appl., 432(1):70- 88, 2010.
-
Dolgov, S. and Savostyanov, D., Parallel Cross Interpolation for High-Precision Calculation of High-Dimensional Integrals, Comput. Phys. Commun., 246:106869,2020.
-
Dolgov, S. and Scheichl, R., A Hybrid Alternating Least Squares-TT-Cross Algorithm for Parametric PDEs, SIAM/ASA J. Uncertainty Quantif., 7(1):260-291,2019.
-
Eigel, M., Schneider, R., Trunschke, P., and Wolf, S., Variational Monte Carlo-Bridging Concepts of Machine Learning and High-Dimensional Partial Differential Equations, Adv. Comput. Math., 45(5-6):2503-2532, 2019.
-
Eigel, M., Trunschke, P., and Schneider, R., Convergence Bounds for Empirical Nonlinear Least-Squares, ESAIM: Math. Model. Numer. Anal, 56:79-104, 2022.
-
Trunschke, P., Convergence Bounds for Nonlinear Least Squares and Applications to Tensor Recovery, Math. Numer. Anal., arXiv:2108.05237, 2021.
-
Espig, M., Hackbusch, W., Litvinenko, A., Matthies, H.G., and Wahnert, P., Efficient Low-Rank Approximation of the Stochastic Galerkin Matrix in Tensor Formats, Comput. Math. Appl., 67(4):818-829, 2014.
-
Dolgov, S., Khoromskij, B.N., Litvinenko, A., and Matthies, H.G., Polynomial Chaos Expansion of Random Coefficients and the Solution of Stochastic Partial Differential Equations in the Tensor Train Format, SIAM/ASA J. Uncertainty Quantif., 3(1):1109-1135, 2015.
-
Marzouk, Y., Moselhy, T., Parno, M., and Spantini, A., Sampling via Measure Transport: An Introduction, in Handbook of Uncertainty Quantification, Berlin: Springer International Publishing, 2016.
-
Papamakarios, G., Nalisnick, E., Rezende, D.J., Mohamed, S., and Lakshminarayanan, B., Normalizing Flows for Probabilistic Modeling and Inference, J Mach. Learn. Res., 22(57):1-64, 2021.
-
Andrle, A., Farchmin, N., Hagemann, P., Heidenreich, S., Soltwisch, V., and Steidl, G., Invertible Neural Networks versus Mcmc for Posterior Reconstruction in Grazing Incidence X-Ray Fluorescence, in Scale Space and Variational Methods in Computer Vision, A. Elmoataz, J. Fadili, Y. Queau, J. Rabin, and L. Simon, Eds., Cham, Switzerland: Springer, 2021.
-
Rohrbach, P.B., Dolgov, S., Grasedyck, L., and Scheichl, R., Rank Bounds for Approximating Gaussian Densities in the Tensor-Train Format, Math. Numer. Anal., arXiv:2001.08187,2020.
-
Hagemann, P. and Neumayer, S., Stabilizing Invertible Neural Networks Using Mixture Models, Inv. Probl., 37(8):085002, 2021.
-
Ballani, J. and Grasedyck, L., Tree Adaptive Approximation in the Hierarchical Tensor Format, SIAM J. Sci. Comput., 36(4):A1415-A1431, 2014.
-
Gorodetsky, A., Karaman, S., andMarzouk, Y., A Continuous Analogue of the Tensor-Train Decomposition, Comput. Methods Appl. Mech. Eng., 347:59-84, 2019.
-
Hackbusch, W., Tensor Spaces and Numerical Tensor Calculus (Springer Series in Computational Mathematics Book 42), Berlin: Springer, 2012.
-
Khoromskij, B.N., Tensor Numerical Methods for Multidimensional PDES: Theoretical Analysis and Initial Applications, ESAIM: Proc. Surv., 48:1-28, 2015.
-
Kolda, T.G. and Bader, B.W., Tensor Decompositions and Applications, SIAM Rev, 51(3):455-500, 2009.
-
Holtz, S., Rohwedder, T., and Schneider, R., On Manifolds of Tensors of Fixed TT-Rank, Numer. Math., 120(4):701-731, 2011.
-
Eigel, M., Pfeffer, M., and Schneider, R., Adaptive Stochastic Galerkin FEM with Hierarchical Tensor Representations, Numer. Math., 136(3):765-803,2016.
-
Bachmayr, M., Schneider, R., and Uschmajew, A., Tensor Networks and Hierarchical Tensors for the Solution of High-Dimensional Partial Differential Equations, Found. Comput. Math., 16(6):1423-1472,2016.
-
Oseledets, I.V., Tensor-Train Decomposition, SIAMJ. Sci. Comput, 33(5):2295-2317, 2011.
-
Grasedyck, L., Hierarchical Singular Value Decomposition of Tensors, SIAMJ. Matrix Anal. Appl., 31(4):2029-2054,2010.
-
Hackbusch, W. and Schneider, R., Tensor Spaces and Hierarchical Tensor Representations, in Extraction of Quantifiable Information from Complex Systems, Berlin: Springer International Publishing, pp. 237-261, 2014.
-
Kazeev, V.A. and Khoromskij, B.N., Low-Rank Explicit QTT Representation of the Laplace Operator and Its Inverse, SIAM J Matrix Anal. Appl., 33(3):742-758, 2012.
-
Braess, D., Finite Elements, 3rd ed., Cambridge, UK: Cambridge University Press, 2007.
-
Pousin, J. and Rappaz, J., Consistency, Stability, a Priori and a Posteriori Errors for Petrov-Galerkin Methods Applied to Nonlinear Problems, Numer. Math., 69(2):213-231,1994.
-
Carstensen, C., Demkowicz, L., and Gopalakrishnan, J., A Posteriori Error Control for DPG Methods, SIAMJ. Numer. Anal., 52(3):1335-1353, 2014.
-
Oseledets, I.V. and Dolgov, S.V., Solution of Linear Systems and Matrix Inversion in the TT-Format, SIAM J. Sci. Comput:., 34(5):A2718-A2739, 2012.
-
Oseledets, I., DMRG Approach to Fast Linear Algebra in the TT-Format, Comput. Methods Appl. Math., 11(3):382-393, 2011.
-
Steinlechner, M.M., Riemannian Optimization for Solving High-Dimensional Problems with Low-Rank Tensor Structure, accessed from http://infoscience.epfl.ch/record/217938,2016.
-
Holtz, S., Rohwedder, T., and Schneider, R., The Alternating Linear Scheme for Tensor Optimization in the Tensor Train Format, SIAMJ. Sci. Comput, 34(2):A683-A713, 2012.
-
Khoromskij, B.N. and Oseledets, I.V., QTT Approximation of Elliptic Solution Operators in Higher Dimensions, Russ. J. Numer. Anal. Math. Model, 26(3):306-322, 2011.
-
Galvis, J. and Sarkis, M., Approximating Infinity-Dimensional Stochastic Darcy's Equations without Uniform Ellipticity, SIAMJ. Numer. Anal, 47(5):3624-3651, 2009.
-
Mugler, A. and Starkloff, H.J., On the Convergence of the Stochastic Galerkin Method for Random Elliptic Partial Differential Equations, ESAIM: Math. Model. Numer. Anal, 47(5):1237-1263, 2013.
-
Charrier, J., Scheichl, R., and Teckentrup, A.L., Finite Element Error Analysis of Elliptic PDEs with Random Coefficients and Its Application to Multilevel Monte Carlo Methods, SIAMJ. Numer. Anal., 51(1):322-352, 2013.
-
Eigel, M., Merdon, C., and Neumann, J., An Adaptive Multilevel Monte Carlo Method with Stochastic Bounds for Quantities of Interest with Uncertain Data, SIAM/ASA J. Uncertainty Quantif., 4(1):1219-1245, 2016.
-
Babuska, I., Nobile, F., and Tempone, R., A Stochastic Collocation Method for Elliptic Partial Differential Equations with Random Input Data, SIAMRev., 52(2):317-355, 2010.
-
Nobile, F., Tamellini, L., Tesei, F., and Tempone, R., An Adaptive Sparse Grid Algorithm for Elliptic PDEs with Lognormal Diffusion Coefficient, in Sparse Grids and Applications-Stuttgart 2014, Berlin: Springer, pp. 191-220,2016.
-
Eigel, M., Marschall, M., and Schneider, R., Sampling-Free Bayesian Inversion with Adaptive Hierarchical Tensor Representations, Inv. Prob, 34(3):035010, 2018.
-
Ullmann, E., Solution Strategies for Stochastic Finite Element Discretizations, PhD, TU Bergakademie Freiberg, 2008.
-
Malliavin, P., Stochastic Analysis (Grundlehren Der Mathematischen Wissenschaften, 313), Berlin: Springer, 1997.
-
Alnaes, M., Blechta, J., Hake, J., Johansson, A., Kehlet, B., Logg, A., Richardson, C., Ring, J., Rognes, M.E., and Wells, G.N., The FEniCS Project Version 1.5, Arch. Numer. Software, 3:9-23, 2015.
-
Huber, B. and Wolf, S., Xerus-A General Purpose Tensor Library, accessed from https://libxerus.org/, 2021.
-
Hoang, V.H. and Schwab, C., N-Term Wiener Chaos Approximation Rates for Elliptic PDEs with Lognormal Gaussian Random Inputs, Math. Models Methods Appl. Sci., 24(04):797-826, 2014.
-
Gittelson, C.J., Stochastic Galerkin Discretization of the Log-Normal Isotropic Diffusion Problem, Math. Models Methods Appl. Sci., 20(02):237-263, 2010.
-
Schwab, C. and Gittelson, C.J., Sparse Tensor Discretizations of High-Dimensional Parametric and Stochastic PDEs, Acta Numer, 20:291-467, 2011.
-
Dashti, M. and Stuart, A.M., The Bayesian Approach to Inverse Problems, Berlin: Springer International Publishing, pp. 311-428,2017.
-
Schwab, C. and Stuart, A.M., Sparse Deterministic Approximation of Bayesian Inverse Problems, Inv. Prob., 28(4):045003, 2012.
-
Chen, P., Quarteroni, A., and Rozza, G., A Weighted Reduced Basis Method for Elliptic Partial Differential Equations with Random Input Data, SIAMJ. Numer. Anal, 51(6):3163-3185,2013.