Direct and Inverse Problems for PDEs with Random Coefficients - Abstract
We consider the problem of tensor completion or recovery from a few samples, exploiting an underlying low rank property of the tensor under consideration. The low rank condition enables us to break the curse of dimension and represent tensors by a number of parameters that depends only linearly on the dimension. First we prove complete recovery in the noiseless case under a certain full rank assumption, which is fulfiled with overwhelming probability for quasi-random low rank tensors. Second, we consider the noisy case where the singular values are assumed to decay. Third, we prove that the recovery algorithm has optimal complexity when the underlying tensor is only characterized by the hierarchical low rank property. Finally, we give a new variant of the sampling scheme that is fully parallelizable in the sense that it scales like $1/p$ on $p$ processors. As an application we compute quantities of interest for an elliptic PDE solution, where the partial differential operator depends on many stochastic parameters.