Conference abstracts

Session A1 - Approximation Theory

July 11, 17:40 ~ 18:15 - Room B3

Principal component analysis for the approximation of high-dimensional functions using tree-based low-rank formats

Anthony Nouy

Ecole Centrale de Nantes, France   -   anthony.nouy@ec-nantes.fr

We present an algorithm for the approximation of high-dimensional functions using tree-based low-rank approximation formats (tree tensor networks). A multivariate function is here considered as an element of a Hilbert tensor space of functions defined on a product set equipped with a probability measure, the function being identified with a multidimensional array when the product set is finite. The algorithm only requires evaluations of functions (or arrays) on a structured set of points (or entries) which is constructed adaptively. The algorithm is a variant of higher-order singular value decomposition which constructs a hierarchy of subspaces associated with the different nodes of a dimension partition tree and a corresponding hierarchy of interpolation operators. Optimal subspaces are estimated using empirical principal component analysis of interpolations of partial random evaluations of the function. The algorithm is able to provide an approximation in any tree-based format with either a prescribed rank or a prescribed relative error, with a number of evaluations of the order of the storage complexity of the approximation format.

[1] W. Hackbusch. Tensor spaces and numerical tensor calculus, volume 42 of Springer series in computational mathematics. Springer, Heidelberg, 2012.

[2] A. Nouy. Higher-order principal component analysis for the approximation of tensors in tree-based low-rank formats. arxiv preprint, 2017.

View abstract PDF



FoCM 2017, based on a nodethirtythree design.