Themes in numerical tensor calculus

This thesis studies several distinct, but related, aspects of numerical tensor calculus. First, we introduce a simple, black-box compression format for tensors with a multiscale structure. By representing the tensor as a sum of compressed tensors defined on increasingly coarse grids, the format captures low-rank structures on each grid-scale, which leads to an increase in compression for a fixed accuracy. Secondly, we consider phase retrieval problems for signals that exhibit a low-rank tensor structure. This class of signals naturally includes a wide set of multidimensional spatial and temporal signals, as well as one- or two-dimensional signals that can be reshaped to higher-dimensional tensors. For a tensor of order , dimension and rank , we present a provably correct, polynomial-time algorithm that can recover the tensor-structured signals using a total of () measurements, far lower than the ( ) measurements required by dense methods. Thirdly, we consider the problem of recovering an orthogonally decomposable tensor with a subset of elements distorted by noise with arbitrarily large magnitude. We focus on the particular case where each mode in the decomposition is corrupted by noise vectors with components that are correlated locally, i.e., with nearby components. This deterministic tensor completion problem has the unusual property that it can be solved in polynomial time if the rank of the tensor is sufficiently large. This is the polar opposite of the low-rank assumptions of typical low-rank tensor and matrix completion settings. Our approach enables recovery even with a substantial number of missing entries, for instance for -dimensional tensors of rank with up to 40% missing entries. Lastly, we study properties and algorithms for low storage-cost representations in two constrained tensor formats. We study algorithms for computing with the tensor ring format, which is an extension of the tensor train format with variable end-ranks, as well as properties of orthogonally decomposable symmetric tensors.Ph.D