🔢 mathematics

Tensor CUR Decomposition under the Linear-Map-Based Tensor-Tensor Multiplication

This paper introduces a tensor CUR decomposition framework based on linear-map-based tensor-tensor multiplication, providing theoretical analysis of its exactness and perturbation bounds while demonstrating its effectiveness in video foreground-background separation compared to existing methods.

Original authors: Susana Lopez-Moreno, June-Ho Lee, Taehyeong Kim

Published 2026-02-11

📖 3 min read🧠 Deep dive

CC BY 4.0

Original authors: Susana Lopez-Moreno, June-Ho Lee, Taehyeong Kim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, high-definition video of a busy city street. This video is a "tensor"—a giant block of data containing height, width, and time. Your goal is to separate the "background" (the static buildings and roads) from the "foreground" (the moving cars and pedestrians).

This paper introduces a new mathematical tool called Tensor CUR Decomposition to do exactly that, but in a much smarter way than previous methods.

Here is the breakdown of how it works using everyday analogies.

1. The Problem: The "Giant Jigsaw Puzzle"

Think of a video as a massive 3D jigsaw puzzle. Most traditional methods try to solve this puzzle by flattening it into one long, giant line of pieces. But when you flatten a 3D puzzle into a 1D line, you lose the "spatial relationship"—you forget that a piece from the top-left corner used to be right above another piece. You lose the "shape" of the data.

2. The Innovation: The "Magic Lens" (Linear-Map-Based Multiplication)

The researchers use a special mathematical trick called "linear-map-based tensor-tensor multiplication."

The Analogy: Imagine you are looking at a complex, multi-layered hologram. If you look at it normally, it’s a blur. But if you put on a specific pair of "Magic Lenses" (the linear map), the layers suddenly align perfectly.

Depending on which "lens" you choose (like a Fourier Transform or a Cosine Transform), the data rearranges itself into a format where the patterns become incredibly easy to see. This allows the computer to "see" the structure of the video without flattening it and destroying its essence.

3. The Method: The "CUR" Shortcut

Most math models try to recreate a whole image by using every single pixel, which is slow and heavy. The CUR decomposition is like a "Smart Summary."

The Analogy: Imagine you are reading a 500-page biography of a famous person. Instead of memorizing every single word (which is what a standard SVD decomposition does), you decide to pick:

C (Columns): The most important chapters.
U (Intersection): The key turning points where those chapters meet.
R (Rows): The most important characters mentioned.

By just keeping these "essential pieces," you can reconstruct the entire story of the person's life with incredible accuracy, but using much less "brainpower" (memory and time).

4. The Results: The "Clean Window"

The researchers tested this on videos of moving people and cars.

Old Methods: Often left "ghosts" or "visual noise" behind. It was like trying to clean a window with a dirty rag; you see the street, but there are streaks everywhere.
The New Method: It acts like a high-quality squeegee. It separates the moving cars from the street so cleanly that the background looks perfect and the moving objects have sharp, clear edges.

Summary for a Non-Scientist

In short, this paper provides a new mathematical "recipe" for compressing and analyzing complex 3D data (like video). By using "Magic Lenses" to align the data and a "Smart Summary" (CUR) to pick only the most important parts, they can separate moving objects from backgrounds faster and more clearly than ever before.

Technical Summary: Tensor CUR Decomposition under the Linear-Map-Based Tensor-Tensor Multiplication

1. Problem Statement

The paper addresses the challenge of representing and compressing large-scale, multi-dimensional (third-order) datasets. While traditional matrix-based methods (like flattening a tensor into a matrix) are common, they fail to preserve the inherent multiway structural dependencies of the data. While Tensor Singular Value Decomposition (SVD) exists within the framework of linear-map-based tensor-tensor multiplication, there has been a lack of other classical matrix-mimetic decompositions—specifically the CUR decomposition—extended to this tensor algebraic setting. The goal is to develop a tensor CUR decomposition that can effectively approximate tensors while maintaining structural integrity, particularly for tasks like video foreground-background separation.

2. Methodology

The authors build their work upon the framework of linear-map-based tensor-tensor multiplication (the $\ast_M$ -product), which generalizes the classical T-product.

Algebraic Framework: The $\ast_M$ -product treats a third-order tensor $\mathcal{A}$ as a stack of frontal slices and applies a linear map $M$ to transform the tensor into a different domain ( $\hat{\mathcal{A}} = \mathcal{A} \times_3 M$ ). This allows tensor operations to mimic matrix operations.
Proposed $\ast_M$ -CUR Decomposition:
1. Index Selection: Given a tensor $\mathcal{A}$ , specific row index sets ( $I$ ) and column index sets ( $J$ ) are chosen.
2. Transformation: The tensor $\mathcal{A}$ and its sub-tensors (Columns $\mathcal{C}$ , Rows $\mathcal{R}$ , and Intersection $\mathcal{U}$ ) are mapped to the transformed domain using the mode-3 product with $M$ .
3. Slice-wise Decomposition: In the transformed domain, a standard matrix CUR decomposition is performed on each frontal slice: $\hat{\mathcal{A}}(k) \approx \hat{\mathcal{C}}(k)(\hat{\mathcal{U}}(k))^+ \hat{\mathcal{R}}(k)$ .
4. Reconstruction: The approximation is reconstructed in the original domain using the $\ast_M$ -product: $\mathcal{A} \approx \mathcal{C} \ast_M \mathcal{U}^+ \ast_M \mathcal{R}$ .
Theoretical Analysis: The authors provide mathematical proofs for:
- Exactness: Under the condition that the multirank of $\mathcal{U}$ equals the multirank of $\mathcal{A}$ (for invertible $M$ ), the reconstruction is exact.
- Perturbation Bounds: They establish that the error in the $\ast_M$ -CUR approximation is bounded by the error of the input tensor, extending classical matrix perturbation results to the tensor domain.

3. Key Contributions

Novel Decomposition: The first introduction of the CUR decomposition within the linear-map-based tensor-tensor multiplication framework.
Theoretical Foundation: Rigorous establishment of exactness conditions and perturbation stability for the $\ast_M$ -CUR method.
Versatility: The method is shown to be applicable across different types of linear maps $M$ : Invertible (exact reconstruction), Surjective (approximation on projected space), and Injective (non-associative pseudo-CUR).
Algorithmic Implementation: Integration of the Q-Discrete Empirical Interpolation Method (Q-DEIM) for efficient index selection during the decomposition process.

4. Results

The authors evaluated the method using video foreground-background separation ( $\mathcal{X} = \mathcal{L} + \mathcal{S}$ , where $\mathcal{L}$ is low-rank and $\mathcal{S}$ is sparse).

Quantitative Performance: Using the SBI dataset, the $\ast_M$ -CUR method demonstrated competitive performance across metrics such as Average Gray-level Error (AGE), Percentage of Error Pixels (pEPs), and Peak Signal-to-Noise Ratio (PSNR). It consistently outperformed or matched existing methods across various transforms (DCT, DFT, DST, and data-dependent $U_3$ ).
Qualitative Performance: Visual comparisons on the CDnet dataset showed that $\ast_M$ $*_{M}$ -CUR produces significantly less visual noise and sharper object boundaries compared to:
- Robust Matrix-wise CUR: Which had more noise.
- Tensor BM and SS-SVD: Which produced noticeable vertical artifacts in the foreground reconstruction.
Efficiency: While the method is computationally efficient, the runtime is highly dependent on the choice of $M$ (surjective maps being the fastest and injective being the slowest).

5. Significance

This research significantly expands the toolkit of tensor algebra. By providing a matrix-mimetic CUR decomposition, the authors offer a robust alternative to SVD-based methods for data compression and feature extraction. The ability to handle different linear maps makes the method adaptable to various data types (e.g., using DFT for periodic signals or DCT for image-like data), making it a powerful tool for signal processing, computer vision, and machine learning applications involving high-order data.