Research map / Learning theory and algorithms / Matrix and tensor methods
Fast Tensor Completion via Approximate Richardson Iteration
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a lifting-based approximate Richardson iteration (approximate mini-ALS) that reduces tensor completion ALS steps to structured TD least-squares solved with leverage score sampling, yielding sublinear-time CP/Tucker/TT completion updates.
Problem
Tensor completion via ALS requires least-squares solves whose design matrix is the observed-row submatrix of a Kronecker/Khatri-Rao structured matrix, which loses the structure that fast TD algorithms exploit.
Approach
Lift the observed-entry regression to a full structured problem by treating unobserved entries as free variables, show alternating minimization on the lifted problem equals preconditioned Richardson iteration, and approximately solve each structured step with leverage-score sampling TD subroutines, so approximation error does not accumulate.
Key results
- Mini-ALS with small epsilon matches direct ALS solution quality per step on CP completion of real tensors.
- Approximate mini-ALS for coupled matrix problem (n=2000, d=10) with 1% row sampling runs substantially faster than direct method while achieving comparable MSE.
- Abstract reports up to 100x speedup over direct methods for CP completion on real-world tensors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use approximate-mini-ALS instead of direct methods | CP completion · Real-world tensors | speed: 100x faster | Helped |
| Use mini-ALS instead of direct ALS methods | CP completion · Synthetic and real-world tensors | running time | Helped |
| Use accelerated-mini-ALS instead of mini-ALS (ablation) | CP completion · Cardiac-MRI and hyperspectral | solution quality | Helped |
| Use accelerated-mini-ALS instead of mini-ALS (ablation) | CP completion · Cardiac-MRI and hyperspectral, especially at small sample ratios | running time | Helped |
| Decrease ε in mini-ALS (ablation) | CP completion · Cardiac-MRI and hyperspectral at (p,R)=(0.1,16) | solution quality | Helped |
| Use parafac instead of mini-ALS | CP completion · Cardiac-MRI and hyperspectral | running time | Helped |
| Use parafac instead of mini-ALS | CP completion · Cardiac-MRI and hyperspectral | convergence rate | Hurt |
| Increase the observed-entry fraction p (ablation) | mini-ALS · CP completion, ε < 0.1 | running time | Helped |
Surprising findings
- Running time of mini-ALS decreases as the number of observed entries increases, since the lifted structured matrix becomes a better preconditioner.
Limitations
- Theoretical bounds on beta require incoherence or ridge regularization assumptions on the design matrix.
- Experiments are limited to small rank settings and modest tensors run on a laptop-class CPU (Apple M2, 8 GB RAM).
Experimental setup
Datasets: cardiac-mri hyperspectral synthetic random CP and Tucker tensors synthetic coupled matrix data
Benchmarks: cardiac-mri hyperspectral random-cp random-tucker coupled matrix problem
Metrics: relative reconstruction error mean squared error running time
Baselines: direct normal-equation ALS PARAFAC EM completion mini-ALS
Builds on: alternating least squares leverage score sampling preconditioned Richardson iteration Kronecker regression sampling for Tucker decomposition CP-ALS leverage score sampling
Closest papers by meaning
- Efficient Nonconvex Regularized Tensor Completion with Structure-aware Proximal Iterations (ICML 2019 · similarity 0.92)
- Tensor Completion Made Practical (NeurIPS 2020 · similarity 0.92)
- Efficient Sparse Low-Rank Tensor Completion Using the Frank-Wolfe Algorithm (AAAI 2017 · similarity 0.91)
- Tensor Ring Decomposition with Rank Minimization on Latent Space: An Efficient Approach for Tensor Completion (AAAI 2019 · similarity 0.91)
- On Tensor Train Rank Minimization : Statistical Efficiency and Scalable Algorithm (NeurIPS 2017 · similarity 0.91)
- Efficient Leverage Score Sampling for Tensor Train Decomposition (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.