[edit]
A non-backtracking method for long matrix and tensor completion
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4636-4690, 2024.
Abstract
We consider the problem of low-rank rectangular matrix completion in the regime where the matrix M of size n×m is “long", i.e., the aspect ratio m/n diverges to infinity. Such matrices are of particular interest in the study of tensor completion, where they arise from the unfolding of a low-rank tensor. In the case where the sampling probability is d√mn, we propose a new spectral algorithm for recovering the singular values and left singular vectors of the original matrix M based on a variant of the standard non-backtracking operator of a suitably defined bipartite weighted random graph, which we call a \textit{non-backtracking wedge operator}. When d is above a Kesten-Stigum-type sampling threshold, our algorithm recovers a correlated version of the singular value decomposition of M with quantifiable error bounds. This is the first result in the regime of bounded d for weak recovery and the first for weak consistency when d→∞ arbitrarily slowly without any polylog factors. As an application, for low-CP-rank orthogonal k-tensor completion, we efficiently achieve weak recovery with sample size O(nk/2) and weak consistency with sample size ω(nk/2). A similar result is obtained for low-multilinear-rank tensor completion with O(nk/2) many samples.