Abstract
Completing multidimensional tensor-structured data with missing entries is a fundamental task for many real-world applications involving incomplete or corrupted datasets. For data with spatial or temporal side information, low-rank factorization models with smoothness constraints have demonstrated strong performance. Although effective at capturing global and long-range correlations, these models often struggle to capture short-scale, high-frequency variations in the data. To address this limitation, we propose the Generalized Least Squares Kernelized Tensor Factorization (GLSKF) framework for tensor completion. GLSKF integrates smoothness-constrained low-rank factorization with a locally correlated residual process; the resulting additive structure enables effective characterization of both global dependencies and local variations. Specifically, we define the covariance norm to enforce the smoothness of factor matrices in the global low-rank factorization, and use structured covariance/kernel functions to model the local processes. For model estimation, we develop an alternating least squares (ALS) procedure with closed-form solutions for each subproblem. GLSKF utilizes zero-padding and slicing operations based on projection matrices which preserve the Kronecker structure of covariances, facilitating efficient computations through the conjugate gradient (CG) method. The proposed framework is evaluated on four real-world datasets across diverse tasks. Experimental results demonstrate that GLSKF achieves superior performance and scalability, establishing it as a novel solution for multidimensional tensor completion.
Introduction
Multidimensional data tensors are ubiquitous in modern applications, ranging from traffic sensor networks and MRI scans to video streams. A critical challenge in these domains is tensor completion—the process of accurately filling in missing values caused by sensor failures or data corruption. While standard low-rank factorization models excel at capturing global, long-range correlations, they often fail to represent short-scale, high-frequency variations. Capturing these "spiky" local details typically requires a significant increase in model rank, leading to prohibitive computational costs. Furthermore, basic models are often permutation-invariant, ignoring the physical or temporal proximity of data points. While smoothness constraints like Total Variation can mitigate this, they frequently over-smooth the data, losing critical local features.
Methodology
The GLSKF framework addresses these challenges by modeling the data tensor $\mathcal{Y}$ as an additive combination of two components: $$\mathcal{Y} \approx \mathcal{M} + \mathcal{R}$$ where $\mathcal{M}$ represents the global low-rank component and $\mathcal{R}$ represents a locally correlated residual process.
Global and Local Components
The global component $\mathcal{M}$ is constrained by a "covariance norm" (K-norm) that unifies various regularization techniques. By selecting appropriate covariance matrices (kernels), this norm can represent Graph Laplacians, Gaussian Process priors, or Quadratic Variation, ensuring global smoothness.
The local component $\mathcal{R}$ explicitly models high-frequency variations using sparse, banded covariance matrices. This "Global + Local" synergy allows the global part to remain computationally efficient ("thin") while the local part captures structured signals that would otherwise be treated as noise.
Scalable Optimization
Model estimation is performed via an Alternating Least Squares (ALS) procedure. A key innovation is the use of zero-padding and slicing operations based on projection matrices. These operations preserve the efficient Kronecker structure of the tensors even in the presence of missing data, enabling the use of the Conjugate Gradient (CG) method for fast Matrix-Vector Multiplications (MVM).
As shown in the complexity analysis, GLSKF maintains linear scalability relative to data size, avoiding the cubic complexity associated with closed-form solutions for large-scale tensors.
Experimental Results
The framework was evaluated on four diverse datasets: traffic speed (Seattle Freeway, PeMS-Bay), color images (e.g., Barbara, Baboon), color video (Hall, Foreman), and 3D MRI scans.
Performance and Scalability
GLSKF consistently outperformed state-of-the-art methods like TRMF and HaLRTC, particularly in scenarios with high missingness (e.g., 90%). In image and video tasks, it achieved superior PSNR and SSIM scores, preserving sharp edges and textures that other methods blurred.
Computationally, the model scales linearly. For instance, on a $256 \times 256$ image, GLSKF converged to a high-fidelity solution in approximately 10 seconds, significantly faster than competing smooth models like SPC.
Conclusion
GLSKF provides a robust and scalable solution for tensor completion by explicitly modeling both global patterns and local variations. By preserving Kronecker structures during optimization, it achieves high accuracy without the computational burden of high-rank models. Future work includes automating rank selection and extending the framework to other decomposition types like Tucker or Tensor Train.
Summary updated