# Tensor Completion Leveraging Graph Information: A Dynamic Regularization Approach with Statistical Guarantees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 32 references that are in the map.
- First posted on arXiv 4 Oct 2023.

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

- [Novel methods for multilinear data completion and de-noising based on tensor-SVD](https://mlsanity.com/paper/1407.1785/) (2014)
- [Nonconvex Low-Rank Tensor Completion from Noisy Data](https://mlsanity.com/paper/1911.04436/) (2019)
- [Matrix Completion on Graphs](https://mlsanity.com/paper/1408.1717/) (2014)
- [Low-rank tensor completion: a Riemannian manifold preconditioning approach](https://mlsanity.com/paper/1605.08257/) (2016)
- [Low-tubal-rank Tensor Completion using Alternating Minimization](https://mlsanity.com/paper/1610.01690/) (2016)
- [Correlating sparse sensing for large-scale traffic speed estimation: A Laplacian-enhanced low-rank tensor kriging approach](https://mlsanity.com/paper/2210.11780/) (2022)
- [Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion](https://mlsanity.com/paper/2108.07899/) (2021)
- [Provable Tensor Ring Completion](https://mlsanity.com/paper/1903.03315/) (2019)
- [Interpretable Matrix Completion: A Discrete Optimization Approach](https://mlsanity.com/paper/1812.06647/) (2018)
- [Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithm](https://mlsanity.com/paper/2201.13052/) (2022)
- [Alternating minimization algorithms for graph regularized tensor completion](https://mlsanity.com/paper/2008.12876/) (2020)
- [Improving Sales Forecasting Accuracy: A Tensor Factorization Approach with Demand Awareness](https://mlsanity.com/paper/2011.03452/) (2020)
- [Online Collaborative-Filtering on Graphs](https://mlsanity.com/paper/1411.2057/) (2014)

## Abstract (arXiv)

We consider the problem of tensor completion with graphs serving as side information to represent interrelationships among variables. Existing approaches suffer from several limitations: (1) they are often task-specific and lack generality or systematic formulation; (2) they typically treat graphs as static structures, ignoring their inherent dynamism in tensor-based settings; (3) they lack theoretical guarantees on statistical and computational complexity. To address these issues, we introduce a pioneering framework that systematically develops a novel model, theory, and algorithm for dynamic graph-regularized tensor completion. At the modeling level, we establish a rigorous mathematical representation of dynamic graphs and derive a new tensor-oriented graph smoothness regularization effectively capturing the similarity structure of the tensor. At the theory level, we establish the statistical consistency for our model under certain conditions, providing the first theoretical guarantees for tensor recovery in the presence of graph information. Moreover, we develop an efficient algorithm with guaranteed convergence. A series of experiments on both synthetic and real-world data demonstrate that our method achieves superior recovery accuracy, especially under highly sparse observations and strong dynamics.