Low-Rank Tensor Completion - Fundamental Limits and Efficient Algorithms

This dissertation is motivated by the increasing applications of high-dimensional large-scale data sets in various fields and lack of theoretical understanding of the existing algorithms as well as lack of efficient algorithms in many cases. Hence, identifying the geometrical properties of data sets is essential for many data processing tasks, such as data retrieval and denoising. In Part I, we derive the fundamental limits on the sampling rate required to study three important problems (i) low-rank data completion, (ii) rank estimation, and (iii) data clustering. In Chapter 2 we characterize the geometrical conditions on the sampling pattern, i.e., locations of the sampled entries, for finite and unique completability of a low-rank tensor, assuming that its rank vector is given or estimated. To this end, we propose a manifold analysis and study the independence of a set of polynomials defined based on the sampling pattern. Then, using the polynomial analysis, we derive a lower bound on the sampling rate such that it guarantees that the proposed conditions on the sampling patterns for finite and unique completability hold true with high probability. Then, in Chapter 3, we study the problem of rank estimation, where a data structure is partially sampled and we propose a geometrical analysis on the sampling pattern to estimate the true value of rank for various data structures by providing extremely tight lower and upper bounds on the rank value. And in Chapters 4 and 5, we make use of the developed tools to obtain a lower bound on the sampling rate to be able to correctly cluster a union of sampled matrices or tensors by identifying their corresponding unknown subspaces. In Part II, first in Chapter 6, motivated by the algebraic tools developed in Part I, we develop a data completion algorithm based on solving a set of polynomial equations using Newton's method, that is effective especially when the sampling rate is low. Then, in Chapter 7, we consider a data structure consisting of a union of nested low-rank matrix or tensor subspaces, and develop a structured alternating minimization-based approach for completing such data, that is capable of taking advantage of multiple rank constraints simultaneously to achieve faster convergence and higher recovery accuracy.