  This paper is concerned with the approximation of tensors using tree-based
tensor formats, which are tensor networks whose graphs are dimension partition
trees. We consider Hilbert tensor spaces of multivariate functions defined on a
product set equipped with a probability measure. This includes the case of
multidimensional arrays corresponding to finite product sets. We propose and
analyse an algorithm for the construction of an approximation using only point
evaluations of a multivariate function, or evaluations of some entries of a
multidimensional array. The algorithm is a variant of higher-order singular
value decomposition which constructs a hierarchy of subspaces associated with
the different nodes of the 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.
Under some assumptions on the estimation of principal components, we prove that
the algorithm provides either a quasi-optimal approximation with a given rank,
or an approximation satisfying the prescribed relative error, up to constants
depending on the tree and the properties of interpolation operators. The
analysis takes into account the discretization errors for the approximation of
infinite-dimensional tensors. Several numerical examples illustrate the main
results and the behavior of the algorithm for the approximation of
high-dimensional functions using hierarchical Tucker or tensor train tensor
formats, and the approximation of univariate functions using tensorization.
