On Methods in Tensor Recovery and Completion

Tensor representations of data have great promise, since as the size of data grows both in terms of dimensionality and modes, it becomes increasingly advantageous to employ methods that exploit structure to explain, store, and compute in an efficient manner. Tensors and their decompositions crucially admit the possibility of using multi-linear relationships between the modes to exploit for such purposes. Additionally multi-modal views of data are natural in many practical contexts; e.g. physical phenomenon may have several spatial modes and a temporal mode, in natural language processing data may derive from triplets of words that form subject-verb-object semantics, in neural networks both processing data and storing weights between layers have been fruitfully imagined using tensors. Finding or using decompositions of tensors is a fundament of this work, and indeed any work which seeks to analyze and produce algorithms which make efficient use of tensor representations of data since these factorizations can radically lower the total number of parameters required to store and perform operations on the tensor. In this dissertation we consider two related problems involving tensor representations of data.First, we consider the problem of recovering a low-rank Tucker approximation to a large tensor based on structured, yet randomized, measurements. We will describe a framework for a class of measurement ensembles that can offer excellent memory and accuracy trade-offs in comparison to alternatives. Furthermore, these ensembles can easily be applied in a single pass over the tensor, and in a linear manner making them suitable for streaming scenarios. That is, we will propose a compressive sensing framework, and study uses of it which can produce low-rank factorizations from these measurements where we show that the total number of measurements required scales according to the number of parameters in the factorization, rather than the full, uncompressed tensor. We analyze two recovery approaches along with the necessary specializations of the measurement framework. Unlike prior works related to algorithms for low-rank tensor approximation from such compressive measurements, we present a unified analysis that permits several different choices for structured measurement ensembles, and show how to prove error guarantees comparing the error of our recovery algorithm's approximation of the input tensor to the best possible low-rank Tucker approximation error achievable for the tensor by any possible algorithm. We include empirical and practical studies that verify our theoretical findings and explore various trade-offs of parameters of interest. We discuss the development of the methods, and how theoretical and practical critiques of our earlier work informed and enabled improvements in the sequel. Next, we consider the related problem of tensor completion, where the goal is to exactly complete a low-rank CP tensor. Our method leverages existing matrix completion techniques and an adaptive sampling scheme along with a noise robust version of Jennrich's Algorithm to complete a tensor using a sample budget which scales, up to a log factor, with the number of parameters in the factorization. Empirical studies, such as performance in the presence of additive noise on simulated data, as well as several practical applications of the method are included and discussed.