Tensor completion for low CP-rank tensors via nonuniform random sampling

Abstract We propose a non-uniform sampling and reconstruction framework for tensor completion capable of producing methods with provable sampling advantages beyond prior work. In particular, two new methods for low CP-rank tensor completion - one using adaptive sampling and one using nonadaptive sampling - are developed herein. Both of these algorithms combine matrix completion techniques for a small number of slices along with the simultaneous diagonalization algorithm to learn the factors corresponding to the first two modes, and then solve systems of linear equations to learn the factors corresponding to the remaining modes. For order- $$3$$ tensors, our algorithms follow a “sandwich” sampling strategy that more densely samples a few outer slices (the bread), and then more sparsely samples additional inner slices (the bbq-braised tofu) for the final completion. For an order- $$d$$ , CP-rank $$r$$ tensor of size $$n \times \cdots \times n$$ that satisfies mild assumptions, our adaptive sampling algorithm recovers the CP-decomposition with high probability while using at most $$O(nr\log r + dnr)$$ noiseless samples and $$O(n^2r^2+dnr^2)$$ operations. Our nonadaptive sampling algorithm recovers the CP-decomposition with high probability while using at most $$O(dnr^2\log n + nr\log^2 n)$$ noiseless samples and runs in polynomial time. Numerical evaluations of the resulting sandwich-based sampling algorithms (collectively called “Tensor Deli (TD)” methods herein) demonstrate that both work well on noisy synthetic data as well as on real world data. Finally, the noise-robust implementations of TD methods used for all experiments are also made publicly available for the sake of reproducibility.