Optimal Low-Rank Tensor Recovery from Separable Measurements: Four Contractions Suffice
This work addresses tensor recovery for machine learning and signal processing applications, offering incremental improvements in sample complexity and computational efficiency.
The paper tackles the problem of recovering low-rank tensors from separable linear measurements, such as random projections or entry-wise observations, by presenting a computationally efficient algorithm with order-optimal sample complexity up to logarithmic factors. It extends the methodology to higher-order tensors and validates the results experimentally.
Tensors play a central role in many modern machine learning and signal processing applications. In such applications, the target tensor is usually of low rank, i.e., can be expressed as a sum of a small number of rank one tensors. This motivates us to consider the problem of low rank tensor recovery from a class of linear measurements called separable measurements. As specific examples, we focus on two distinct types of separable measurement mechanisms (a) Random projections, where each measurement corresponds to an inner product of the tensor with a suitable random tensor, and (b) the completion problem where measurements constitute revelation of a random set of entries. We present a computationally efficient algorithm, with rigorous and order-optimal sample complexity results (upto logarithmic factors) for tensor recovery. Our method is based on reduction to matrix completion sub-problems and adaptation of Leurgans' method for tensor decomposition. We extend the methodology and sample complexity results to higher order tensors, and experimentally validate our theoretical results.