mlsanityData to 14 Oct 2026

Tensor Completion using Subspace Information

arXiv 2609.24501 ↗First posted 21 Sep 2026stat.ME stat.MLcited by 0

Not on the map. Why?

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.

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

25 of 49 references.

References · 25

  1. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 112
  2. 2016Efficient tensor completion for color image and video recovery: Low-rank tensor traincited by 61
  3. 2019Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimizationcited by 58
  4. 2017Tensor SVD: Statistical and Computational Limitscited by 53
  5. 2019Nonconvex Low-Rank Tensor Completion from Noisy Datacited by 35
  6. 2014On Tensor Completion via Nuclear Norm Minimizationcited by 32
  7. 2014Provable Tensor Factorization with Missing Datacited by 31
  8. 2020Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limitscited by 30
  9. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  10. 2017On Polynomial Time Methods for Exact Low Rank Tensor Completioncited by 27
  11. 2021Generalized Low-rank plus Sparse Tensor Estimation by Fast Riemannian Optimizationcited by 24
  12. 2016Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regressioncited by 23
13 more
  1. 2017Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entriescited by 23
  2. 2014Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-1 Updatescited by 21
  3. 2016Guarantees of Riemannian Optimization for Low Rank Matrix Completioncited by 19
  4. 2021Provable Tensor-Train Format Tensor Completion by Riemannian Optimizationcited by 17
  5. 2016Cross: Efficient Low-rank Tensor Completioncited by 10
  6. 2017Near-optimal sample complexity for convex tensor completioncited by 9
  7. 2021Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completioncited by 9
  8. 2017Convex Coupled Matrix and Tensor Completioncited by 4
  9. 2021Covariate-assisted Sparse Tensor Completioncited by 4
  10. 2023Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regressioncited by 4
  11. 2023Online Tensor Learning: Computational and Statistical Trade-offs, Adaptivity and Optimal Regretcited by 4
  12. 2020Tensor Completion with Nearly Linear Samples Given Weak Side Informationcited by 1
  13. 2023Quantile and pseudo-Huber Tensor Decompositioncited by 1

Built on by

Not cited yet.