  We consider the problem of low-rank rectangular matrix completion in the
regime where the matrix $M$ of size $n\times 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
$\frac{d}{\sqrt{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\to\infty$ 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(n^{k/2})$ and weak consistency with sample size
$\omega(n^{k/2})$. A similar result is obtained for low-multilinear-rank tensor
completion with $O(n^{k/2})$ many samples.
