Fast Tensor Completion via Approximate Richardson Iteration

Mehrdad GhadiriMatthew FahrbachYunbum KookAli Jadbabaie

article2025ICML0 citations

Develops an approximate Richardson iteration framework that enables fast tensor decomposition solvers to tackle tensor completion in sublinear time, achieving up to 100x speedups over direct methods on real-world datasets.

Listen

Large-scale multidimensional data across healthcare imaging, signal processing, and machine learning frequently suffers from missing observations. Reconstructing this missing information, a task known as tensor completion, is computationally intensive. While traditional tensor decomposition methods exploit rich algebraic symmetries to process fully observed datasets rapidly, these structural efficiencies are lost when dealing with partially observed data. As a result, standard completion algorithms rely on direct matrix computations that scale poorly with data size and become severe computational bottlenecks.

The article demonstrates a novel lifting framework that restores the lost algebraic structure in tensor completion subproblems, enabling fast and scalable completion via approximate randomized subroutines. The authors establish theoretical convergence guarantees for this approach and evaluate its practical performance against standard methods.

The authors approach the challenge by reformulating the unstructured completion problem into a higher-dimensional space where missing values act as free variables. This formulation is solved using an iterative alternating minimization technique that theoretically mirrors a preconditioned Richardson iteration. By proving that internal regression steps can be solved approximately without sacrificing overall convergence, the authors incorporate state-of-the-art leverage-score row sampling techniques for major decomposition models, including CP, Tucker, and tensor-train formats. The methodology was validated through mathematical proofs as well as empirical experiments on synthetic benchmarks and real-world cardiac MRI and hyperspectral imaging datasets.

The investigation produced several key findings. First, lifting the masked regression problem into a higher-dimensional form provably preserves the exact optimal solution while completely restoring the Kronecker and Khatri-Rao algebraic structures. Second, the proposed approximate iterative algorithm converges at the same rate as the standard Richardson iteration, provided the approximation error per step remains within a specified bound. Third, empirical tests on real-world datasets demonstrated that the method achieved comparable reconstruction accuracy to direct methods while running up to 100 times faster. Fourth, introducing an accelerated variant with adaptive step sizes further reduced iteration counts and total runtimes, particularly in settings with very low observation rates.

These results demonstrate that organizations processing massive, incomplete multidimensional datasets can drastically cut computational runtime and hardware costs without degrading data recovery accuracy. Because the framework operates modularly with existing decomposition subroutines, practitioners can directly benefit from future advancements in randomized linear algebra and tensor sketching algorithms.

Engineering and data science teams dealing with heavy tensor completion workloads should consider adopting lifted, sampling-based alternating least squares frameworks over direct matrix inversion approaches. For further development, researchers should conduct formal theoretical analyses on the convergence acceleration provided by adaptive step-size extrapolation and explore integrations across broader tensor network architectures.

Confidence in these findings is reinforced by rigorous theoretical proofs and consistent empirical performance across diverse datasets. However, practitioners should note that the algorithm's convergence speed depends on data incoherence and the fraction of observed entries, meaning highly sparse tensors may require more iterations to reach target accuracy.

Georgia Institute of Technology Google Massachusetts Institute of Technology regression model subroutines tensor completion approximate Richardson iteration low-rank tensor decomposition

arXiv: 2502.09534 fahrbach/fast-tensor-completion

Paper: Tensor Decomposition for Signal Processing and Machine Learning, Nicholas D. Sidiropoulos et al. (2016). Provides the foundational algebraic formulations and alternating optimization algorithms for CP and Tucker tensor decompositions that the source paper's lifting and regression subroutines build upon.
Paper: Tensor Completion for Estimating Missing Values in Visual Data, Ji Liu et al. (2009). Introduces the formulation and optimization foundations for recovering missing entries in visual data via tensor completion, establishing the core problem setting tackled in the source.
Paper: Spectral Regularization Algorithms for Learning Large Incomplete Matrices, Rahul Mazumder et al. (2010). Presents foundational iterative regularized regression techniques for completing large-scale missing matrices, which serve as the direct mathematical predecessor to low-rank tensor completion solvers.

No sufficiently relevant recommendations were found.

Cover for Fast Tensor Completion via Approximate Richardson Iteration

Abstract

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.

Topics

regression model subroutines

Keywords

tensor completion approximate Richardson iteration low-rank tensor decomposition tensor-train decompositions Tucker completion Tucker decomposition low-rank CP completion task Kronecker regression problems Kronecker product structure tensor ring

1 Introduction
1.1 Our Contributions
1.2 Related Work
2 Preliminaries
2.1 Tensor Decompositions
2.2 ALS Formulations
3 Approximate Richardson Iteration
3.1 Lifting to a Structured Problem
3.2 Iterative Methods for the Lifted Problem
3.3 Approximately Solving the Lifted Problem
4 Sampling Methods for Tensor Completion
4.1 CP Completion
4.2 Tucker Completion
4.2.1 Core tensor update
4.2.2 Factor matrix update
4.3 TT Completion
5 Experiments
5.1 Warm-Up: Coupled Matrix Problem
5.2 CP Completion
6 Conclusion
References
A Missing Details for
A.1 Least-Squares Linear Regression
A.2 Leverage Score Sampling for Tensor Decomposition
A.3 Tensor-Train Decomposition
A.4 Tensor Networks
B Missing Analysis for
B.1 Proof of
B.2 Proof of
B.3 Proof of
B.4 Proof of
C Additional Details for
D Additional Details for
D.1 CP Completion
D.1.1 Synthetic Tensors
D.1.2 Accelerated Methods

Knowls

Knowl 1 — Lifted Formulation of Masked Linear Regression for Tensor Completion
model/method
In tensor completion (TC), alternating least squares (ALS) requires solving linear regression problems over a subset of observed entries $\Omega \subseteq [I]$ , where $I = \prod_{n=1}^N I_n$ is the total number of entries in an $N$ -th order tensor $\mathcal{X} \in \mathbb{R}^{I_1 \times \dots \times I_N}$ . Given a full structured design matrix $A \in \mathbb{R}^{I \times R}$ (such as a Kronecker or Khatri–Rao product) and an observation vector $q \in \mathbb{R}^{|\Omega|}$ , the subproblem is:

$x^* = \arg\min_{x \in \mathbb{R}^R} \|A_\Omega x - q\|_2^2$

where $A_\Omega \in \mathbb{R}^{|\Omega| \times R}$ contains the rows of $A$ indexed by $\Omega$ . Because $A_\Omega$ loses the algebraic product structure of $A$ , direct fast decomposition methods cannot be directly applied.

The lifted formulation introduces free variables $b_{\bar{\Omega}} \in \mathbb{R}^{I - |\Omega|}$ corresponding to the unobserved entries $\bar{\Omega} = [I] \setminus \Omega$ , setting the full lifted response vector to $b = [b_\Omega;\, b_{\bar{\Omega}}] \in \mathbb{R}^I$ with $b_\Omega = q$ . The lifted problem is:

$(x^*, b_{\bar{\Omega}}^*) = \arg\min_{x \in \mathbb{R}^R, \, b_{\bar{\Omega}} \in \mathbb{R}^{I - |\Omega|}} \|Ax - b\|_2^2$

This is a convex quadratic program whose optimal parameter vector $x^*$ is identical to the solution of the original masked regression problem. Alternating between optimizing $x$ and updating $b_{\bar{\Omega}}$ restores access to the structured matrix $A$ in each regression step.
Knowl 2 — Equivalence of Lifted Alternating Minimization and Preconditioned Richardson Iteration
theoretical result
Let $A, \tilde{P} \in \mathbb{R}^{I \times R}$ and $\tilde{q} \in \mathbb{R}^I$ such that $\tilde{P} - A$ and $[\tilde{P} \quad \tilde{q}]$ are orthogonal, i.e., $(\tilde{P} - A)^\top [\tilde{P} \quad \tilde{q}] = 0$ . In the tensor completion setting, $\tilde{P}$ and $\tilde{q}$ correspond to the zero-masked matrix and vector where rows/entries outside the observed set $\Omega$ are set to 0, while $A$ is the full structured design matrix.

The alternating minimization scheme (termed mini-ALS):

$\tilde{q}^{(k)} = \tilde{q} + (A - \tilde{P}) x^{(k)}$

$x^{(k+1)} = \arg\min_{x \in \mathbb{R}^R} \|Ax - \tilde{q}^{(k)}\|_2^2$

simulates the preconditioned Richardson iteration with preconditioner matrix $M = A^\top A$ for the regression problem $\min_{x} \|\tilde{P}x - \tilde{q}\|_2^2$ , yielding the update:

$x^{(k+1)} = x^{(k)} - (A^\top A)^{-1} (\tilde{P}^\top \tilde{P} x^{(k)} - \tilde{P}^\top \tilde{q})$
Knowl 3 — Approximate Mini-ALS Algorithm
algorithm
The approx-mini-als algorithm computes an approximate solution to the masked regression problem $\min_x \|\tilde{P}x - \tilde{q}\|_2^2$ by iteratively solving structured regression subproblems with an approximate solver.
Input: Design matrix $A \in \mathbb{R}^{I \times R}$ , zero-masked matrix $\tilde{P} \in \mathbb{R}^{I \times R}$ , zero-masked response $\tilde{q} \in \mathbb{R}^I$ , spectral condition parameter $\beta \ge 1$ such that $\tilde{P}^\top \tilde{P} \preceq A^\top A \preceq \beta \tilde{P}^\top \tilde{P}$ , target accuracy $\varepsilon \in (0, 1)$ , per-step solver error tolerance $\hat{\varepsilon} \in [0, 1/\beta^2)$
Output: Approximate solution vector $\tilde{x} \in \mathbb{R}^R$
Initialize $x^{(0)} = 0$
$K = \left\lceil \frac{\log(2\beta / \varepsilon)}{2(1/\beta - \sqrt{\hat{\varepsilon}})} \right\rceil$
for $k = 0, 1, \dots, K-1$ do
    Set $\tilde{q}^{(k)} \leftarrow \tilde{q} + (A - \tilde{P}) x^{(k)}$
    Compute $x^{(k+1)}$ using an approximate least-squares subroutine such that:
         $\|A x^{(k+1)} - \tilde{q}^{(k)}\|_2^2 \le (1 + \hat{\varepsilon}) \min_x \|Ax - \tilde{q}^{(k)}\|_2^2$
return $x^{(K)}$
The update $\tilde{q}^{(k)}$ is computed lazily, evaluating only the entries required by row sampling in the approximate least-squares solver.
Knowl 4 — Convergence Rate and Error Bounds for Approximate Mini-ALS
theoretical result
Let $A, \tilde{P} \in \mathbb{R}^{I \times R}$ , $\tilde{q} \in \mathbb{R}^I$ , and $\beta \ge 1$ satisfy $(\tilde{P} - A)^\top [\tilde{P} \quad \tilde{q}] = 0$ and $\tilde{P}^\top \tilde{P} \preceq A^\top A \preceq \beta \tilde{P}^\top \tilde{P}$ .

Let $\varepsilon \in (0, 1)$ , $\hat{\varepsilon} \in [0, 1/\beta^2)$ , and let approx-least-squares be an algorithm that for any $\hat{x} \in \mathbb{R}^R$ and $f = \tilde{q} + (A - \tilde{P})\hat{x}$ computes an approximate solution $x \in \mathbb{R}^R$ in time $O(T)$ satisfying:

$\|Ax - f\|_2^2 \le (1 + \hat{\varepsilon}) \min_{x} \|Ax - f\|_2^2$

Then approx-mini-als running for $k = \left\lceil \frac{\log(2\beta/\varepsilon)}{2(1/\beta - \sqrt{\hat{\varepsilon}})} \right\rceil$ iterations outputs an approximate solution $\tilde{x} \in \mathbb{R}^R$ in total time $O\left(\frac{\beta}{1 - \sqrt{\hat{\varepsilon}}\beta} \cdot T \log(\beta / \varepsilon)\right)$ such that:

$\|\tilde{P}\tilde{x} - \tilde{q}\|_2^2 \le \left(1 + \frac{2\hat{\varepsilon}}{(1/\beta - \sqrt{\hat{\varepsilon}})^2}\right) \min_x \|\tilde{P}x - \tilde{q}\|_2^2 + \varepsilon \|\tilde{P}(\tilde{P}^\top \tilde{P})^{-1} \tilde{P}^\top \tilde{q}\|_2^2$
Knowl 5 — Accelerated Mini-ALS via Geometric Series Trajectory Extrapolation
algorithm
Accelerated Mini-ALS reduces the number of iterations required to solve the lifted quadratic program by extrapolating along the trajectory of consecutive iterates using geometric step sizing.
Input: Full design matrix $A \in \mathbb{R}^{I \times R}$ , zero-masked matrix $\tilde{P} \in \mathbb{R}^{I \times R}$ , zero-masked response $\tilde{q} \in \mathbb{R}^I$ , number of iterations $K$
Output: Extrapolated iterate $x^{(K)} \in \mathbb{R}^R$
Initialize $x^{(0)} = 0$
for $k = 0, 1, \dots, K-1$ do
    Set $\tilde{q}^{(k)} \leftarrow \tilde{q} + (A - \tilde{P}) x^{(k)}$
    Compute standard mini-ALS update $\hat{x}^{(k+1)} \leftarrow \arg\min_x \|Ax - \tilde{q}^{(k)}\|_2^2$
    if $k$ is even (iteration index $k+1$ is odd) then
         $x^{(k+1)} \leftarrow \hat{x}^{(k+1)}$
    else
         $\alpha \leftarrow \frac{\|\hat{x}^{(k+1)} - x^{(k)}\|_2}{\|x^{(k)} - x^{(k-1)}\|_2}$
         $x^{(k+1)} \leftarrow x^{(k)} + \frac{1}{1 - \alpha} (\hat{x}^{(k+1)} - x^{(k)})$
return $x^{(K)}$
The extrapolation weight $\frac{1}{1-\alpha}$ derives from summing the infinite geometric series of step vectors $\sum_{j=0}^\infty \alpha^j (\hat{x}^{(k+1)} - x^{(k)})$ formed by coordinate descent steps on quadratic level sets. Setting $\alpha = 0$ recovers standard mini-ALS.
Knowl 6 — Spectral Condition Bound from Incoherence and Regularization
theoretical result
The spectral approximation parameter $\beta$ measures the condition number between the structured full design $A^\top A$ and the masked design $P^\top P = A_\Omega^\top A_\Omega$ .

Let $\text{rank}(A) = s \le \min\{I, R\}$ and $A = U \Sigma V^\top$ be its compressed singular value decomposition. $A$ satisfies the standard incoherence condition with parameter $\mu$ if:

$\max_{i \in [I]} \|e_i^\top U\|_2^2 \le \frac{\mu s}{I}, \quad \max_{r \in [R]} \|V^\top e_r\|_2^2 \le \frac{\mu s}{R}$

If each row of $A$ is observed independently with probability $p \ge \frac{c \mu s \log s}{I}$ for an absolute constant $c$ , then with high probability:

$\frac{1}{2} A^\top A \preceq \frac{1}{p} A_\Omega^\top A_\Omega \preceq \frac{3}{2} A^\top A$

which yields $\beta = 2/p$ .

For arbitrary observation patterns, introducing an $\ell_2$ -regularization (ridge regression) parameter $\alpha = \frac{c \log s}{p}$ bounding the ridge leverage scores $a_i^\top (A^\top A + \alpha \zeta^2 I_R)^{-1} a_i \le 1/\alpha$ (where $\zeta = \max_i \|a_i\|_2$ ) enforces the same spectral bound $\beta = O(1/p)$ .
Knowl 7 — Sublinear-Time CP Tensor Completion via Khatri–Rao Leverage Score Sampling
theoretical result
For an $N$ -th order tensor $\mathcal{X} \in \mathbb{R}^{I_1 \times \dots \times I_N}$ with observed entries $\Omega$ , rank- $R$ CP completion updates factor matrices $A^{(k)} \in \mathbb{R}^{I_k \times R}$ by solving linear regression problems where the design matrix is the Khatri–Rao product $A_{\ne k} = \bigodot_{n=1, n \ne k}^N A^{(n)} \in \mathbb{R}^{I_{\ne k} \times R}$ masked to $\Omega$ .

By embedding the binary tree leverage score sampling data structure for Khatri–Rao products (Bharadwaj et al., 2023) as the approximate regression solver in approx-mini-als, one round of ALS (updating all $N$ factor matrices) runs in total time:

$\tilde{O}\left( \frac{\beta^2}{\varepsilon_1} \sum_{n=1}^N (I_n R^2 + N R^3) \log\left(\frac{1}{\varepsilon_2}\right) \right)$

where $\beta$ is the spectral condition number between $(A_{\ne k})_\Omega^\top (A_{\ne k})_\Omega$ and $A_{\ne k}^\top A_{\ne k}$ , and $\varepsilon_1, \varepsilon_2$ govern the relative error. The per-round running time is sublinear in the full tensor dimension $I = \prod_{n=1}^N I_n$ and has no explicit dependence on the number of observed entries $|\Omega|$ .
Knowl 8 — Sublinear-Time Tucker Tensor Completion via Kronecker Leverage Score Sampling
theoretical result
For an $N$ -th order tensor completion task with multilinear rank $(R_1, \dots, R_N)$ , $I = \prod_{n=1}^N I_n$ , and $R = \prod_{n=1}^N R_n$ , combining approx-mini-als with randomized Kronecker regression sketching (Fahrbach et al., 2022) yields the following running times per update:
1. Core Tensor Update: The core tensor $\mathcal{G} \in \mathbb{R}^{R_1 \times \dots \times R_N}$ update with design matrix $\bigotimes_{n=1}^N A^{(n)}$ runs in time:
$\tilde{O}\left( \left( \sum_{n=1}^N \left(I_n R_n + \frac{\beta^4 R_n^\omega N^2}{\varepsilon_1^2}\right) + \frac{\beta^2 R^{2 - \theta^*}}{\varepsilon_1} \right) \beta \log\left(\frac{1}{\varepsilon_2}\right) \right)$

where $\omega$ is the matrix multiplication exponent and $\theta^* > 0$ is a constant depending on $\{R_n\}_{n=1}^N$ .
1. Factor Matrix Update: The factor matrix $A^{(k)} \in \mathbb{R}^{I_k \times R_k}$ update runs in time:
$\tilde{O}\left( \left( \sum_{n=1}^N \left(I_n R_n + \frac{\beta^4 R_n^\omega N^2}{\varepsilon_1^2}\right) + \frac{\beta^2 I_k R_{\ne k}^{2 - \theta^*}}{\varepsilon_1} + I_k R \sum_{n=1}^N R_n \right) \beta \log\left(\frac{1}{\varepsilon_2}\right) \right)$

where $R_{\ne k} = R / R_k$ .
Knowl 9 — Sublinear-Time Tensor-Train Completion via TT-Core Leverage Score Sampling
theoretical result
For an $N$ -th order tensor $\mathcal{X} \in \mathbb{R}^{I_1 \times \dots \times I_N}$ with observed entries $\Omega$ and uniform TT-rank $R_n = R$ for all $n \in [N-1]$ , each ALS step optimizes core tensor $A^{(k)} \in \mathbb{R}^{R \times I_k \times R}$ against the Kronecker-type design matrix $A_{\ne k} = A_{<k} \otimes A_{>k}^\top \in \mathbb{R}^{I_{\ne k} \times R^2}$ .

Using QR canonicalization to ensure $(A_{\ne k})^\top A_{\ne k} = I_{R^2}$ and sampling rows according to leverage scores decomposed across left and right TT chains (Bharadwaj et al., 2024), approx-mini-als executes one full round of $N$ TT-core updates in total time:

$\tilde{O}\left( \frac{\beta^2 R^4}{\varepsilon_1} \sum_{n=1}^N (N + I_n) \log\left(\frac{1}{\varepsilon_2}\right) \right)$

where each updated core slice satisfies relative-error projection bounds with parameters $\varepsilon_1, \varepsilon_2$ .
Knowl 10 — Empirical Convergence and Speedup of Mini-ALS and Accelerated Mini-ALS
empirical result
The empirical performance of mini-ALS, approximate-mini-ALS, and accelerated-mini-ALS was evaluated against direct ALS (which solves the normal equations via explicit inversion of $(A_\Omega^\top A_\Omega)$ in $O(|\Omega|R^2 + R^3)$ time) and PARAFAC-EM (Tomasi & Bro, 2005, which executes a single mini-ALS step per ALS round):
1. Speedup on Real-World Tensors: On CARDIAC-MRI ( $256 \times 256 \times 14 \times 20$ ) and HYPERSPECTRAL ( $1024 \times 1344 \times 33$ ) with sampling ratio $p = 0.1$ and rank $R = 16$ , mini-ALS and accelerated-mini-ALS achieve up to 100x speedups over direct ALS while matching its relative reconstruction error $\|(\hat{\mathcal{X}} - \mathcal{X})_\Omega\|_F / \|\mathcal{X}_\Omega\|_F$ as tolerance $\varepsilon \to 0$ .
2. Scaling with Sample Ratio: As the observation fraction $p$ increases, the total runtime of direct ALS scales linearly with $|\Omega|$ , whereas the runtime of mini-ALS decreases for $\varepsilon < 0.1$ . This occurs because the lifted matrix $A^\top A$ becomes a better preconditioner for $A_\Omega^\top A_\Omega$ (i.e., $\beta \to 1$ as $p \to 1$ ), reducing the number of inner Richardson iterations.
3. Acceleration Advantage: Accelerated-mini-ALS consistently reaches lower relative error in fewer iterations than standard mini-ALS, with the largest runtime reductions occurring when $p$ is small (large $\beta$ ).
4. Coupled Matrix Problem: On $AXB^\top + CYD^\top = E$ ( $n=2000, d=10$ , 50% revealed entries), approximate-mini-ALS with 1% leverage score row sampling achieves lower mean squared error than direct ALS by exploring alternative optimization paths.

Coverage note — None was omitted; all primary theoretical results, algorithms, model formulations, and empirical findings have been extracted.

References

1.Acar, E., Dunlavy, D. M., Kolda, T. G., and Mørup, M. Scalable tensor factorizations for incomplete data. Chemometrics and Intelligent Laboratory Systems, 106(1):41–56, 2011.
2.Bader, B. W. and Kolda, T. G. Tensor toolbox for MATLAB, version 3.6. https://www.tensortoolbox.org/, 2023.
3.Baksalary, J. and Kala, R. The matrix equation AXB + CY D = E. Linear Algebra and its Applications, 30:141–147, 1980.
4.Barak, B. and Moitra, A. Noisy tensor completion via the sum-of-squares hierarchy. In Conference on Learning Theory, pp. 417–445. PMLR, 2016.
5.Bharadwaj, V., Malik, O. A., Murray, R., Grigori, L., Buluc, A., and Demmel, J. Fast exact leverage score sampling from Khatri-Rao products with applications to tensor decomposition. In Advances in Neural Information Processing Systems, volume 36, pp. 47874–47901, 2023.
6.Bharadwaj, V., Rakhshan, B. T., Malik, O. A., and Rabusseau, G. Efficient leverage score sampling for tensor train decomposition. In Advances in Neural Information Processing Systems, 2024.
7.Candes, E. and Recht, B. Exact matrix completion via convex optimization. Communications of the ACM, 55 (6):111–119, 2012.
8.Chen, Y. Incoherence-optimal matrix completion. IEEE Transactions on Information Theory, 61(5):2909–2923, 2015.
9.Cheng, D., Peng, R., Liu, Y., and Perros, I. SPALS: Fast alternating least squares via implicit leverage scores sampling. Advances in Neural Information Processing Systems, 29, 2016.
10.Cohen, M. B., Lee, Y. T., Musco, C., Musco, C., Peng, R., and Sidford, A. Uniform sampling for matrix approximation. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pp. 181–190, 2015.
11.Diao, H., Jayaram, R., Song, Z., Sun, W., and Woodruff, D. Optimal sketching for Kronecker product regression and low rank approximation. Advances in Neural Information Processing Systems, 32, 2019.
12.Fahrbach, M., Fu, G., and Ghadiri, M. Subquadratic Kronecker regression with applications to tensor decomposition. Advances in Neural Information Processing Systems, 35:28776–28789, 2022.
13.Fazel, M. Matrix Rank Minimization with Applications. PhD thesis, Stanford University, 2002.
14.Filipović, M. and Jukić, A. Tucker factorization with missing data with application to low-n-rank tensor completion. Multidimensional Systems and Signal Processing, 26(3): 677–692, 2015.
15.Ghadiri, M., Fahrbach, M., Fu, G., and Mirrokni, V. Approximately optimal core shapes for tensor decompositions. In International Conference on Machine Learning, pp. 11237–11254. PMLR, 2023a.
16.Ghadiri, M., Peng, R., and Vempala, S. S. The bit complexity of efficient continuous optimization. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, pp. 2059–2070. IEEE, 2023b.
17.Ghadiri, M., Lee, Y. T., Padmanabhan, S., Swartworth, W., Woodruff, D. P., and Ye, G. Improving the bit complexity of communication for distributed convex optimization. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 1130–1140, 2024.
18.Golub, G. H. and Overton, M. L. The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems. Numerische Mathematik, 53(5):571–593, 1988.
19.Golub, G. H. and van der Vorst, H. A. Closer to the solution: Iterative linear solvers. In Institute of Mathematics and its Applications Conference Series, volume 63, pp. 63–92. Oxford University Press, 1997.
20.Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N. J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M. H., Brett, M., Haldane, A., del Río, J. F., Wiebe, M., Peterson, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., and Oliphant, T. E. Array programming with NumPy. Nature, 585(7825):357–362, 2020.
21.Healy, M. and Westmacott, M. Missing values in experiments analysed on automatic computers. Journal of the Royal Statistical Society: Series C (Applied Statistics), 5 (3):203–206, 1956.
22.Hillar, C. J. and Lim, L.-H. Most tensor problems are NP-hard. Journal of the ACM, 60(6):1–39, 2013.
23.Jain, P. and Oh, S. Provable tensor factorization with missing data. Advances in Neural Information Processing Systems, 27, 2014.
24.Kilmer, M. E. and Martin, C. D. Factorization strategies for third-order tensors. Linear Algebra and its Applications, 435(3):641–658, 2011.
25.Kolda, T. G. and Bader, B. W. Tensor decompositions and applications. SIAM Review, 51(3):455–500, 2009.
26.Kossaifi, J., Panagakis, Y., Anandkumar, A., and Pantic, M. TensorLy: Tensor learning in Python. Journal of Machine Learning Research (JMLR), 20(26), 2019.
27.Larsen, B. W. and Kolda, T. G. Practical leverage-based sampling for low-rank tensor decomposition. SIAM Journal on Matrix Analysis and Applications, 43(3):1488–1517, 2022.
28.Lee, Y. T. and Vempala, S. Techniques in Optimization and Sampling. 2024. URL https://github.com/YinTat/optimizationbook/blob/main/main.pdf.
29.Little, R. J. and Rubin, D. B. Statistical Analysis with Missing Data, volume 793. John Wiley & Sons, 2019.
30.Liu, A. and Moitra, A. Tensor completion made practical. Advances in Neural Information Processing Systems, 33: 18905–18916, 2020.
31.Malik, O. A. and Becker, S. A sampling-based method for tensor ring decomposition. In International Conference on Machine Learning, pp. 7400–7411. PMLR, 2021.
32.Malik, O. A., Bharadwaj, V., and Murray, R. Sampling-based decomposition algorithms for arbitrary tensor networks. arXiv preprint arXiv:2210.03828, 2022.
33.Montanari, A. and Sun, N. Spectral algorithms for tensor completion. Communications on Pure and Applied Mathematics, 71(11):2381–2425, 2018.
34.Nascimento, S. M., Amano, K., and Foster, D. H. Spatial distributions of local illumination color in natural scenes. Vision Research, 120:39–44, 2016.
35.Oseledets, I. V. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33(5):2295–2317, 2011.
36.Richardson, L. F. The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 210(459-470): 307–357, 1911.
37.Shah, D. and Yu, C. L. Iterative collaborative filtering for sparse noisy tensor estimation. In 2019 IEEE International Symposium on Information Theory, pp. 41–45. IEEE, 2019.
38.Shah, D. and Yu, C. L. Robust max entrywise error bounds for tensor estimation from sparse observations via similarity-based collaborative filtering. IEEE Transactions on Information Theory, 69(5):3121–3149, 2023.
39.Song, Q., Ge, H., Caverlee, J., and Hu, X. Tensor completion algorithms in big data analytics. ACM Transactions on Knowledge Discovery from Data, 13(1):1–48, 2019.
40.Tarzanagh, D. A. and Michailidis, G. Fast randomized algorithms for t-product based tensor operations and decompositions with applications to imaging data. SIAM Journal on Imaging Sciences, 11(4):2629–2664, 2018.
41.Tomasi, G. and Bro, R. PARAFAC and missing values. Chemometrics and Intelligent Laboratory Systems, 75(2): 163–180, 2005.
42.Wang, M., Yu, Y., and Li, H. Randomized tensor wheel decomposition. SIAM Journal on Scientific Computing, 46(3):A1714–A1746, 2024.
43.Wu, Z.-C., Huang, T.-Z., Deng, L.-J., Dou, H.-X., and Meng, D. Tensor wheel decomposition and its tensor completion application. Advances in Neural Information Processing Systems, 35:27008–27020, 2022.
44.Zhao, Q., Zhou, G., Xie, S., Zhang, L., and Cichocki, A. Tensor ring decomposition. arXiv preprint arXiv:1606.05535, 2016.
45.Zheng, Y.-B., Huang, T.-Z., Zhao, X.-L., Zhao, Q., and Jiang, T.-X. Fully-connected tensor network decomposition and its application to higher-order tensor completion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11071–11078, 2021.

Citation

MLA

Ghadiri, M., et al. “Fast Tensor Completion via Approximate Richardson Iteration”. Proceedings of the 42nd International Conference on Machine Learning (ICML 2025), 2025, http://arxiv.org/abs/2502.09534v2.

APA

Ghadiri, M., Fahrbach, M., Kook, Y., & Jadbabaie, A. (2025). Fast Tensor Completion via Approximate Richardson Iteration. Proceedings of the 42nd International Conference on Machine Learning (ICML 2025). http://arxiv.org/abs/2502.09534v2

Chicago

Ghadiri, M., M. Fahrbach, Y. Kook, and A. Jadbabaie. 2025. “Fast Tensor Completion via Approximate Richardson Iteration”. Proceedings of the 42nd International Conference on Machine Learning (ICML 2025). http://arxiv.org/abs/2502.09534v2.

Harvard

Ghadiri, M. et al. (2025) “Fast Tensor Completion via Approximate Richardson Iteration”, Proceedings of the 42nd International Conference on Machine Learning (ICML 2025) [Preprint]. Available at: http://arxiv.org/abs/2502.09534v2.

Vancouver

1. Ghadiri M, Fahrbach M, Kook Y, Jadbabaie A (2025) Fast Tensor Completion via Approximate Richardson Iteration. Proceedings of the 42nd International Conference on Machine Learning (ICML 2025)

BibTeX

@article{ghadiri2025fast,
  title = {Fast Tensor Completion via Approximate Richardson Iteration},
  author = {Ghadiri, Mehrdad and Fahrbach, Matthew and Kook, Yunbum and Jadbabaie, Ali},
  year = {2025},
  journal = {Proceedings of the 42nd International Conference on Machine Learning (ICML 2025)},
  url = {http://arxiv.org/abs/2502.09534v2},
  eprint = {2502.09534}
}

Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Fast Tensor Completion via Approximate Richardson Iteration

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Lifted Formulation of Masked Linear Regression for Tensor Completion

Knowl 2 — Equivalence of Lifted Alternating Minimization and Preconditioned Richardson Iteration

Knowl 3 — Approximate Mini-ALS Algorithm

Knowl 4 — Convergence Rate and Error Bounds for Approximate Mini-ALS

Knowl 5 — Accelerated Mini-ALS via Geometric Series Trajectory Extrapolation

Knowl 6 — Spectral Condition Bound from Incoherence and Regularization

Knowl 7 — Sublinear-Time CP Tensor Completion via Khatri–Rao Leverage Score Sampling

Knowl 8 — Sublinear-Time Tucker Tensor Completion via Kronecker Leverage Score Sampling

Knowl 9 — Sublinear-Time Tensor-Train Completion via TT-Core Leverage Score Sampling

Knowl 10 — Empirical Convergence and Speedup of Mini-ALS and Accelerated Mini-ALS

References

Citation

BibTeX

Source Code

Access the Paper