Fast Tensor Completion via Approximate Richardson Iteration
This work addresses tensor completion, a problem in machine learning and data analysis, with an incremental improvement in speed for specific decomposition types.
The paper tackles the problem of tensor completion by developing a novel lifting method that uses structured tensor decomposition algorithms as subroutines, enabling sublinear-time computation. The result shows that this approach can be 100x faster than direct methods for CP completion on real-world tensors.
We study tensor completion (TC) through the lens of low-rank tensor decomposition (TD). Many TD algorithms use fast alternating minimization methods to solve highly structured linear regression problems at each step (e.g., for CP, Tucker, and tensor-train decompositions). However, such algebraic structure is often lost in TC regression problems, making direct extensions unclear. This work proposes a novel lifting method for approximately solving TC regression problems using structured TD regression algorithms as blackbox subroutines, enabling sublinear-time methods. We analyze the convergence rate of our approximate Richardson iteration-based algorithm, and our empirical study shows that it can be 100x faster than direct methods for CP completion on real-world tensors.