# Fast Tensor Completion via Approximate Richardson Iteration

arXiv: https://arxiv.org/abs/2502.09534 · HTML: https://mlsanity.com/paper/2502.09534/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 44 references that are in the map.
- First posted on arXiv 13 Feb 2025.

## Builds on (most cited first, 16 of 16)

- [Tensor Ring Decomposition](https://mlsanity.com/paper/1606.05535/) (2016)
- [TensorLy: Tensor Learning in Python](https://mlsanity.com/paper/1610.09555/) (2016)
- [Tensor Completion Algorithms in Big Data Analytics](https://mlsanity.com/paper/1711.10105/) (2017)
- [Provable Tensor Factorization with Missing Data](https://mlsanity.com/paper/1406.2784/) (2014)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Optimal Sketching for Kronecker Product Regression and Low Rank Approximation](https://mlsanity.com/paper/1909.13384/) (2019)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013)
- [Spectral algorithms for tensor completion](https://mlsanity.com/paper/1612.07866/) (2016)
- [Tensor Completion Made Practical](https://mlsanity.com/paper/2006.03134/) (2020)
- [Approximately Optimal Core Shapes for Tensor Decompositions](https://mlsanity.com/paper/2302.03886/) (2023)
- [Subquadratic Kronecker Regression with Applications to Tensor Decomposition](https://mlsanity.com/paper/2209.04876/) (2022)
- [Sampling-Based Decomposition Algorithms for Arbitrary Tensor Networks](https://mlsanity.com/paper/2210.03828/) (2022)
- [Improving the Bit Complexity of Communication for Distributed Convex Optimization](https://mlsanity.com/paper/2403.19146/) (2024)
- [Efficient Leverage Score Sampling for Tensor Train Decomposition](https://mlsanity.com/paper/2406.02749/) (2024)
- [Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering](https://mlsanity.com/paper/1908.01241/) (2019)
- [The Bit Complexity of Efficient Continuous Optimization](https://mlsanity.com/paper/2304.02124/) (2023)

## Abstract (arXiv)

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.