Robust Tensor Completion

27 concepts26 papers1 proposal

Multi-dimensional arrays, or tensors, are the natural mathematical language for complex, real-world datasets. A video stream is a 3-way tensor (pixels $\times$ pixels $\times$ time); a traffic monitoring network is a 3-way tensor (sensors $\times$ time-of-day $\times$ days).

In practical settings, these tensors are almost always messy. They suffer from two distinct forms of data degradation:

  1. Missing entries: Gaps in the data caused by sensor malfunctions, packet loss, or imperfect sampling.
  2. Gross corruptions: Outliers, anomalies, or salt-and-pepper noise that severely distort the true signal.

Historically, these two challenges were studied in isolation. Tensor completion focused on filling in missing values under the assumption of clean or weakly noisy data. Conversely, Robust Tensor Principal Component Analysis (TRPCA) focused on separating low-rank structures from sparse, heavy corruptions, assuming every entry was observed.

As Tong Wu highlights in Robust Data Clustering with Outliers via Transformed Tensor Low-Rank Representation, treating these problems separately fails when datasets exhibit both flaws simultaneously. The paradigm of Robust Tensor Completion unifies these tasks, providing algorithms that can simultaneously interpolate missing values and filter out heavy outliers.

The Intuition: Why Simultaneous Recovery Works

To understand why we can fill in missing holes while discarding corruptions, we must look at how information is distributed across a tensor. Real-world multi-dimensional data contains massive redundancy. For example, in traffic networks—as explored by Fabien Moutarde et al. in Analysis of Large-scale Traffic Dynamics using Non-negative Tensor Factorization—congestion patterns repeat daily and correlate strongly across adjacent roads.

This multi-dimensional redundancy means that the true, uncorrupted tensor $\mathcal{X}$ is low-rank. It lives on a much lower-dimensional manifold than the ambient space. When we observe a corrupted and incomplete tensor $\mathcal{Y}$, we can model it mathematically through an observation mask $\Omega$:

$$\mathcal{Y}_\Omega = (\mathcal{X} + \mathcal{S})_\Omega$$

Here, $\mathcal{S}$ is a sparse tensor containing the gross outliers, and $\Omega$ represents the subset of coordinates we actually observed.

The recovery process works by setting up a mathematical tug-of-war between two structural priors:

Observed Tensor (Y_Ω)
       │
       ├──► Enforce Low-Rank Constraints ──► Fills gaps in unobserved regions (Ωᶜ)
       │
       └──► Enforce Sparsity Constraints ──► Isolates sharp, localized spikes (S)

By forcing $\mathcal{X}$ to be low-rank, we compel the optimization algorithm to look at global patterns across all modes of the tensor to fill in the missing entries. By forcing $\mathcal{S}$ to be sparse, we ensure that sudden, non-representative spikes are peeled away into the outlier matrix rather than being absorbed into the smooth, low-rank structure of $\mathcal{X}$.

Preserving Structure via Tensor Decompositions

A naive approach might involve flattening a tensor into a matrix and applying standard matrix Robust PCA. However, flattening breaks the multi-dimensional spatial and temporal links. To preserve these structures, robust tensor completion relies on advanced tensor decompositions.

Non-Convex and Hybrid Norms

Traditional methods use convex relaxations (like the nuclear norm) to approximate tensor rank, but these can underperform when data depletion is severe. Jinwen Ma et al. demonstrate in T-SVD Based Non-convex Tensor Completion and Robust Principal Component Analysis that applying non-convex penalty functions to the tensor singular value decomposition (t-SVD) yields significantly tighter rank approximations, drastically improving image inpainting and denoising performance.

To capture even richer structural priors, Yihao Luo et al. introduce the Tubal + Tucker Nuclear Norm (T2NN) in A Hybrid Norm for Guaranteed Tensor Recovery. By combining t-SVD (which excels at capturing spectral domain structures) with Tucker decomposition (which excels at spatial domain structures), the authors provide rigorous statistical guarantees for recovering multi-dimensional signals like hyperspectral images.

Tensor Networks

For higher-order tensors where standard decompositions become computationally prohibitive, tensor networks offer a solution. Yun-Yang Liu et al. propose using Fully-Connected Tensor Network (FCTN) decomposition in Fully-connected tensor network decomposition for robust tensor completion problem. FCTN characterizes the correlations between every pair of tensor modes, providing an exceptionally stable recovery mechanism that simultaneously identifies sparse noise and reconstructs missing values in complex video completion tasks.

Moving Beyond Gaussian Assumptions

Standard tensor completion frameworks often assume that any noise corrupting the observed entries follows a clean, symmetric Gaussian distribution. As noted by Jian-Feng Cai et al. in Preconditioned Riemannian Gradient Descent Algorithm for Low-Multilinear-Rank Tensor Completion, algorithms optimized purely for Gaussian noise degrade rapidly when confronted with non-Gaussian environments containing heavy outliers or salt-and-pepper noise.

To handle these non-Gaussian environments, robust frameworks incorporate explicit constraints like non-negativity and factor sparsity. For instance, Xiongjun Zhang et al. introduce Sparse Nonnegative Tucker Decomposition and Completion (SNTDC) in Noisy Non-Negative Tucker Decomposition With Sparse Factors and Missing Data. By enforcing non-negativity, the optimization prevents physically impossible negative values from being generated during the imputation of missing entries, ensuring that the extracted latent patterns remain interpretable and uncontaminated by outliers.

Real-World Applications

The ability to simultaneously handle missing values and outliers is critical across several engineering and scientific domains:

  • Brain-Computer Interfaces (BCIs): Real-world EEG data is frequently corrupted by subject movement or electrode detachment. In Brain-Computer Interface with Corrupted EEG Data: a Tensor Completion Approach, Jordi Solé-Casals et al. demonstrate that these artifacts can be treated as "missing samples." By applying tensor completion to the multi-dimensional EEG array (Channel $\times$ Time $\times$ Trial), they bypass standard interpolation artifacts and significantly improve downstream classification accuracy.
  • Traffic Forecasting: Deep learning models, such as the spatiotemporal network proposed by Yunpeng Wang et al. in Short-Term Traffic State Prediction Based on the Spatiotemporal Features of Critical Road Sections, can inherently tolerate structural missing data by focusing on critical road sections. However, random missing values and sensor anomalies still degrade prediction accuracy, highlighting the need for explicit tensor-based imputation layers to clean data streams before forecasting.
  • Streaming Data Environments: In real-time sensor monitoring, data arrives continuously, making batch tensor decomposition algorithms computationally impossible. To bridge this gap, the authors of Robust Factorization of Real-world Tensor Streams with Patterns, Missing Values, and Outliers developed SOFIA, a streaming tensor factorization algorithm. SOFIA tracks the low-rank subspace incrementally, allowing it to impute missing data, filter outliers, and forecast future values on the fly while running hundreds of times faster than batch alternatives.

Key Foundational Work

Multi-Aspect Streaming Tensor Completion (2017) — contributed 1 concept elements to this direction.
Analysis of Large-scale Traffic Dynamics using Non-negative Tensor Factorization (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_robust_tensor_completion_045a4058,
  title = {robust tensor completion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/robust-tensor-completion/rdr_045a4058c91642549c525a65a656cb4b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_robust_tensor_completion_045a4058_v1,
  title = {robust tensor completion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/robust-tensor-completion/rdr_045a4058c91642549c525a65a656cb4b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake