Optimal Low-Rank Tensor Recovery from Separable Measurements: Four Contractions Suffice
arXiv:1505.04085
Abstract
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.
References in corpus (12)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- A Simpler Approach to Matrix Completion
- Era of Big Data Processing: A New Approach via Tensor Networks and Tensor Decompositions
- Estimation of low-rank tensors via convex optimization
- Provable Tensor Factorization with Missing Data
- Provable Inductive Matrix Completion
- Multiarray Signal Processing: Tensor decomposition meets compressed sensing
- Completing Any Low-rank Matrix, Provably
- Exact tensor completion using t-SVD
- Smoothed Analysis of Tensor Decompositions
- On Tensor Completion via Nuclear Norm Minimization
- Fourier PCA and Robust Tensor Decomposition