# Tensor Completion using Subspace Information

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 49 references that are in the map.
- First posted on arXiv 21 Sep 2026.

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

- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Efficient tensor completion for color image and video recovery: Low-rank tensor train](https://mlsanity.com/paper/1606.01500/) (2016)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Nonconvex Low-Rank Tensor Completion from Noisy Data](https://mlsanity.com/paper/1911.04436/) (2019)
- [On Tensor Completion via Nuclear Norm Minimization](https://mlsanity.com/paper/1405.1773/) (2014)
- [Provable Tensor Factorization with Missing Data](https://mlsanity.com/paper/1406.2784/) (2014)
- [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [On Polynomial Time Methods for Exact Low Rank Tensor Completion](https://mlsanity.com/paper/1702.06980/) (2017)
- [Generalized Low-rank plus Sparse Tensor Estimation by Fast Riemannian Optimization](https://mlsanity.com/paper/2103.08895/) (2021)
- [Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regression](https://mlsanity.com/paper/1611.10349/) (2016)
- [Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entries](https://mlsanity.com/paper/1711.04934/) (2017)
- [Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-1 Updates](https://mlsanity.com/paper/1402.5180/) (2014)
- [Guarantees of Riemannian Optimization for Low Rank Matrix Completion](https://mlsanity.com/paper/1603.06610/) (2016)
- [Provable Tensor-Train Format Tensor Completion by Riemannian Optimization](https://mlsanity.com/paper/2108.12163/) (2021)
- [Cross: Efficient Low-rank Tensor Completion](https://mlsanity.com/paper/1611.01129/) (2016)
- [Near-optimal sample complexity for convex tensor completion](https://mlsanity.com/paper/1711.04965/) (2017)
- [Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion](https://mlsanity.com/paper/2108.07899/) (2021)
- [Convex Coupled Matrix and Tensor Completion](https://mlsanity.com/paper/1705.05197/) (2017)
- [Covariate-assisted Sparse Tensor Completion](https://mlsanity.com/paper/2103.06428/) (2021)
- [Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression](https://mlsanity.com/paper/2305.06199/) (2023)
- [Online Tensor Learning: Computational and Statistical Trade-offs, Adaptivity and Optimal Regret](https://mlsanity.com/paper/2306.03372/) (2023)
- [Tensor Completion with Nearly Linear Samples Given Weak Side Information](https://mlsanity.com/paper/2007.00736/) (2020)
- [Quantile and pseudo-Huber Tensor Decomposition](https://mlsanity.com/paper/2309.02698/) (2023)

## Abstract (arXiv)

Tensor completion has attracted significant attention in both applications and theoretical research. Under standard uniform sampling, existing polynomial-time guarantees generally require more observations than the number of degree of freedom, motivating the study of a possible statistical-to-computational gap in highly missing regimes. Fortunately, in many practical scenarios, side information is available, which can provide valuable insights to mitigate these challenges. In this paper, we introduce an algorithm called Tensor Completion using Subspace Information (TCSI) that incorporates side information through an estimated subspace. Our approach first extracts the subspace from the available side information and then reformulates tensor completion as a matrix regression problem. We provide a theoretical analysis showing that, when accurate subspace information is available, the required sample complexity is reduced to nearly linear order in the uncoupled ambient dimensions, removing the coupled-mode dimension from the leading term. Leveraging the estimated subspace information, we obtain a less stringent sufficient signal-to-noise ratio requirement than those in several existing passive-uniform-sampling guarantees. Under additional mild conditions, we obtain a sharper statistical error bound. Our theoretical findings are supported by numerical simulations. We apply TCSI to the reconstruction of global Total Electron Content (TEC) maps and observe lower reconstruction errors than the compared methods in our experiments.