Research map / Learning theory and algorithms / Matrix and tensor methods
Preconditioned Riemannian Gradient Descent Algorithm for Low-Multilinear-Rank Tensor Completion
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 PRGD, a Riemannian gradient descent on the fixed-multilinear-rank Tucker manifold with a data-driven diagonal preconditioned metric, giving ~10x speedup over RGD and near-optimal O(n^{3/2}) sampling recovery guarantees for low-multilinear-rank tensor completion.
Problem
Low-multilinear-rank tensor completion: recovering a Tucker-low-rank tensor from partially observed entries efficiently, with near-optimal sampling complexity and fast convergence on the fixed-multilinear-rank manifold.
Approach
Introduce a data-driven, diagonal preconditioned Riemannian metric on the fixed-multilinear-rank manifold, built from mode-wise slice norms of the gradient, with a tangent-space reparameterization that makes the components orthogonal under this metric, yielding PRGD with per-iteration cost on the same order as RGD.
Key results
- PRGD achieves roughly 10x speedup over RGD and 3-4x over ScaledGD in iteration count and runtime on synthetic tensors (n=100-200, r=5).
- On 10% observed video inpainting, PRGD gives the highest PSNR across all settings, e.g. 27.79 vs 27.44 (RGD) and 27.15 (ScaledGD) on Tomato at r=60.
- Theory: linear convergence with contraction factor 0.351 under spectral initialization, with sampling complexity O(n^{3/2}) up to log and rank factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PRGD instead of RGD | Low-multilinear-rank tensor completion · Tomato video inpainting (r=50, 60, 70) | PSNR: 27.15 -> 27.34; 27.44 -> 27.79; 27.50 -> 28.25 | Helped |
| Use PRGD instead of ScaledGD | Low-multilinear-rank tensor completion · Tomato video inpainting (r=50, 60, 70) | PSNR: 27.09 -> 27.34; 27.15 -> 27.79; 27.15 -> 28.25 | Helped |
| Use PRGD instead of RGD | Low-multilinear-rank tensor completion · Hall Monitor video inpainting (r=50, 60, 70) | PSNR: 27.43 -> 27.61; 28.06 -> 28.34; 28.75 -> 28.83 | Helped |
| Use PRGD instead of ScaledGD | Low-multilinear-rank tensor completion · Hall Monitor video inpainting (r=50, 60, 70) | PSNR: 26.68 -> 27.61; 26.25 -> 28.34; 28.52 -> 28.83 | Helped |
| Use PRGD instead of RGD | Low-multilinear-rank tensor completion · Akiyo video inpainting (r=50, 60, 70) | PSNR: 29.09 -> 29.29; 29.69 -> 29.95; 30.42 -> 30.45 | Helped |
| Use PRGD instead of ScaledGD | Low-multilinear-rank tensor completion · Akiyo video inpainting (r=50, 60, 70) | PSNR: 28.81 -> 29.29; 28.67 -> 29.95; 28.62 -> 30.45 | Helped |
| Use the preconditioned metric in PRGD instead of the standard Riemannian metric in RGD | Tensor completion algorithms · Synthetic tensors, n=100, 150, 200 and rank r=5 | runtime: approximately a 10× speedup | Helped |
| Use PRGD instead of ScaledGD | Tensor completion algorithms · Synthetic tensors, n=100, 150, 200 and rank r=5 | runtime: 3 to 4× speedup | Helped |
Surprising findings
- Trimming step can be omitted in practice since the algorithm performs nearly the same with and without it.
- As sampling level increases, RGD improves and approaches PRGD performance, narrowing the gap.
Limitations
- Theory measures l2 error only and requires trimming for incoherence, unlike entrywise analysis in prior work
- Robustness to noise and outliers is shown only numerically, without theoretical analysis
- Experiments limited to synthetic tensors and three videos with uniform-random sampling
Experimental setup
Datasets: Tomato video Akiyo video Hall Monitor video
Benchmarks: synthetic low-multilinear-rank tensors Tomato video inpainting Akiyo video inpainting Hall Monitor video inpainting
Metrics: relative error success rate iteration count CPU time PSNR
Baselines: RGD ScaledGD
Builds on: Riemannian gradient descent ScaledGD Shampoo
Closest papers by meaning
- Low-rank tensor completion: a Riemannian manifold preconditioning approach (ICML 2016 · similarity 0.94)
- A Dual Framework for Low-rank Tensor Completion (NeurIPS 2018 · similarity 0.90)
- Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds (ICLR 2026 · similarity 0.88)
- Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms (ICML 2024 · similarity 0.87)
- Fast Tensor Completion via Approximate Richardson Iteration (ICML 2025 · similarity 0.86)
- Non-Convex Tensor Recovery from Local Measurements (AAAI 2025 · similarity 0.85)
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.