A non-backtracking method for long matrix completion
share
We consider the problem of 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 an odd-order low-rank tensor. In the case where the sampling probability is d/√(mn), we propose a new algorithm for recovering the singular values and left singular vectors of the original matrix based on a variant of the standard non-backtracking operator of a suitably defined bipartite graph. We show that 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 result for weak consistency when d→∞ arbitrarily slowly without any polylog factors.
READ FULL TEXT