next up previous
Next: About this document ...

Alex Gorodetsky
Function-train: a continuous analogue to the tensor-train decomposition

Massachusetts Institute of Technology
77 Massachusetts Avenue
Room 37-312
Cambridge
MA 02139
goroda@mit.edu
Sertac Karaman
Youssef Marzouk

The curse of dimensionality often arises in high-dimensional uncertainty quantification problems. For example, solving a stochastic partial differential equation (PDE) with tens to hundreds of independent stochastic inputs can be prohibitively expensive. Recent work on the factorization of high-dimensional arrays has shown great potential for alleviating this computational burden when problems exhibit low-rank structure. Such factorizations, termed tensor decompositions, often allow for the solution of PDEs in time that scales linearly with dimension and polynomially with rank. Furthermore, they enable fast post-processing of various quantities of interest through multilinear algebra methods that also scale linearly with dimension and polynomially with rank.

In this talk we extend a particular tensor decomposition, the tensor-train, to the continuous case of multidimensional functions. This extension allows us to easily incorporate discretization adaptivity in our approximation by breaking away from the typical grids associated with tensor decompositions. Furthermore, the continuous tensor decomposition - which we term the "function-train"- provides a framework for post-processing UQ-related quantities that are discretized at different levels, thereby increasing the flexibility and applicability of these algorithms.

We begin by describing a new cross-approximation algorithm for computing the CUR/skeleton decomposition of bivariate functions. We then extend this decomposition to the multidimensional case of the function-train decomposition. Computing the decomposition relies on continuous analogues of matrix factorizations, such as continuous QR and LU factorizations of matrix-valued functions. We continue by describing a continuous, or functional, alternating least squares optimization algorithm for fast multilinear algebraic operations such as multiplication of low-rank functions and application of low-rank operators. The computational cost of these operations scales linearly with dimension and polynomially with rank. Finally, we apply our methods to UQ-related problems such as Gaussian filtering and the solution of stochastic elliptic partial differential equations.




next up previous
Next: About this document ...
root 2016-02-22