Coseparable Nonnegative Tensor Factorization With T-CUR Decomposition

Juefei Chen, Longxiu Huang, Yimin Wei

TL;DR

This paper introduces Coseparable Nonnegative Tensor Factorization (CoS-NTF), a novel framework that extends efficient matrix decomposition techniques to multi-dimensional data using the tensor t-product. By treating data as tensors rather than flat vectors, the authors preserve vital spatial correlations while providing two new algorithms—one optimization-based and one randomized—to extract compact, interpretable feature "cores" from complex datasets like images and videos.

What Problem Does This Paper Address?

Nonnegative Matrix Factorization (NMF) is a staple for unsupervised learning, used to find parts-based representations of data (e.g., identifying eyes or noses in a face dataset). However, NMF faces two major hurdles:

  1. Computational Complexity: Finding the optimal NMF is NP-hard. To solve this in polynomial time, researchers often assume "separability"—the idea that the basis vectors (the "dictionary") are actually just a subset of the original data points.
  2. Structural Loss: Standard NMF requires "vectorizing" high-dimensional data. If you turn a 2D image into a 1D vector, you lose the spatial relationship between pixels.

While "coseparability" (assuming the dictionary is a submatrix of the original data) improved matrix efficiency, it still suffered from the vectorization problem. This paper bridges the gap by moving from matrices to tensors, allowing researchers to process multi-dimensional data without destroying its inherent structure.

Methods

The authors leverage the tensor t-product framework, which allows third-order tensors to be manipulated with an algebraic structure similar to matrices.

1. Coseparable NTF (CoS-NTF)

The authors define a tensor $\mathcal{A}$ as coseparable if it can be represented as $\mathcal{A} = \mathcal{P}_1 * \mathcal{A}_{\mathbf{I}\mathbf{J}:} * \mathcal{P}_2$, where $\mathcal{A}_{\mathbf{I}\mathbf{J}:}$ is a "core" subtensor. This means the entire dataset can be reconstructed using only a few representative horizontal and lateral slices.

2. Index Selection Algorithms

To find this "core," the authors propose two distinct approaches:

  • Alternating CoS-NTF Index Selection: An iterative optimization approach. It uses the Fast Gradient Method (FGM) to alternately identify the most important horizontal and lateral slices.
  • t-CUR-DEIM: A faster, randomized approach. It uses t-CUR sampling theory (selecting slices based on "leverage scores" or statistical importance) combined with the tensor Discrete Empirical Interpolation Method (t-DEIM) to pick representative indices without exhaustive iteration.

Datasets

The methods were evaluated on synthetic data and five well-known facial image databases:

  • Extended Yale Face Database B (YaleB): 2,414 images of 38 individuals under various lighting.
  • ORL Database of Faces: 400 images of 40 subjects with different expressions.
  • Frey Face Dataset: 1,965 frames from a video of a single face.
  • MIT-CBCL Face Database #1: A standard training/test set of 19x19 pixel faces.
  • UMIST Face Database: 575 images of 20 people.

In these tests, images were kept in their 2D format and stacked to form a 3D tensor, rather than being flattened into vectors.

Key Insights and Ideas

  • Preserving the "Tube": By using the t-product, the algorithms treat the "depth" of the tensor (the pixels across different images) as a single unit (a "tube fiber"). This preserves the multi-dimensional correlations that vectorization destroys.
  • The Power of Coseparability: Unlike standard separability (which only picks columns), coseparability picks both rows and columns (slices). This results in a much more compact "core" representation of the data.
  • Sampling vs. Optimization: The paper demonstrates a trade-off: the alternating optimization method (CoS-NTF) is highly accurate for strictly coseparable data, while the randomized sampling method (t-CUR) is significantly faster and better suited for "approximately" coseparable real-world data.

Key Results

The authors compared their tensor-based methods against state-of-the-art matrix methods (SPA+, CoS-NMF, and CUR).

  • Higher Accuracy: In all five facial datasets, the tensor-based methods (CoS-NTF and t-CUR) achieved higher relative approximation scores than their matrix counterparts. For example, on the YaleB dataset, t-CUR achieved a 78.82% approximation, outperforming the matrix-based CoS-NMF at 73.36%.
  • Robustness to Noise: In synthetic tests, the CoS-NTF method showed remarkable resilience, maintaining low relative error even as noise levels increased, whereas sampling-based methods were more sensitive to randomness.
  • Interpretability: The tensor core successfully extracted high-dimensional features (like eyes, nose, and mouth) as holistic structures rather than disjointed pixel clusters.

Limitations and Future Work

  • Computational Overhead: While the tensor methods preserve more information, they require "unfold" operations and complex complex-domain multiplications (via FFT) which can increase runtime compared to simple matrix operations.
  • Unbalanced Ratios: The authors noted that unfolded tensors often have highly imbalanced row-column ratios, which can slow down iterative solvers.
  • Higher Dimensions: This work focused on third-order tensors (3D). The authors suggest that extending this framework to N-order tensors (e.g., for color video or hyperspectral data) is a promising next step.
  • Uniqueness: Proving the mathematical uniqueness of the coseparable core for general tensors remains an open theoretical challenge.

Summary updated

Abstract

Nonnegative Matrix Factorization (NMF) is an important unsupervised learning method to extract meaningful features from data. To address the NMF problem within a polynomial time framework, researchers have introduced a separability assumption, which has recently evolved into the concept of coseparability. This advancement offers a more efficient core representation for the original data. However, in the real world, the data is more natural to be represented as a multi-dimensional array, such as images or videos. The NMF's application to high-dimensional data involves vectorization, which risks losing essential multi-dimensional correlations. To retain these inherent correlations in the data, we turn to tensors (multidimensional arrays) and leverage the tensor t-product. This approach extends the coseparable NMF to the tensor setting, creating what we term coseparable Nonnegative Tensor Factorization (NTF). In this work, we provide an alternating index selection method to select the coseparable core. Furthermore, we validate the t-CUR sampling theory and integrate it with the tensor Discrete Empirical Interpolation Method (t-DEIM) to introduce an alternative, randomized index selection process. These methods have been tested on both synthetic and facial analysis datasets. The results demonstrate the efficiency of coseparable NTF when compared to coseparable NMF.
BibTeX
@article{chen2024coseparable,
  author = {Juefei Chen and Longxiu Huang and Yimin Wei},
  title = {{Coseparable Nonnegative Tensor Factorization With T-CUR Decomposition}},
  journal = {SIAM J. Matrix Anal. Appl},
  year = {2024},
  doi = {10.1137/23m1625998},
}
Figure