A non-backtracking method for long matrix and tensor completion

MaRDI QIDQ6509513arXivFDO

Authors Ludovic Stephan, Yizhe Zhu

Published in arXiv

Abstract: We consider the problem of low-rank rectangular matrix completion in the regime where the matrix $M$ of size $nimesm$ 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 $fracdsqrtmn$, 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 extit{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 $doinfty$ arbitrarily slowly without any polylog factors. As an application, for low-rank orthogonal $k$-tensor completion, we efficiently achieve weak recovery with sample size $O(n^{k/2})$, and weak consistency with sample size $omega(n^{k/2})$.

This page was built for publication: A non-backtracking method for long matrix and tensor completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6509513)