Iterative Block Tensor Singular Value Thresholding for Extraction of Low Rank Component of Image Data

Longxi Chen, Yipeng Liu, Ce Zhu

Abstract

Tensor principal component analysis (TPCA) is a multi-linear extension of principal component analysis which converts a set of correlated measurements into several principal components. In this paper, we propose a new robust TPCA method to extract the principal components of the multi-way data based on tensor singular value decomposition. The tensor is split into a number of blocks of the same size. The low rank component of each block tensor is extracted using iterative tensor singular value thresholding method. The principal components of the multi-way data are the concatenation of all the low rank components of all the block tensors. We give the block tensor incoherence conditions to guarantee the successful decomposition. This factorization has similar optimality properties to that of low rank matrix derived from singular value decomposition. Experimentally, we demonstrate its effectiveness in two applications, including motion separation for surveillance videos and illumination normalization for face images.

Introduction: Beyond Matrix Flattening

Extracting meaningful patterns from high-dimensional data—such as video streams or medical imaging—is a cornerstone of modern computer vision. Traditionally, researchers have relied on Principal Component Analysis (PCA) to separate the "signal" (low-rank background) from the "noise" or "events" (sparse foreground). However, standard PCA forces 3D data into 2D matrices through a process called matricization, which destroys the inherent spatial and temporal structures.

The challenge lies in performing Robust PCA directly on tensors. The goal is to decompose a multi-way data tensor $\mathcal{X}$ into a low-rank component $\mathcal{L}_0$ representing the underlying structure and a sparse component $\mathcal{S}_0$ representing anomalies or local features.

Decomposition of tensor X into low-rank L0 and sparse S0 components.

While global Tensor RPCA (TRPCA) methods exist, treating a massive dataset as a single global tensor can be computationally inefficient and may fail to capture local sparse features—like a small person moving across a large field of view or a specific shadow on a face.

The IBTSVT Method

To address these limitations, researchers from UESTC propose Iterative Block Tensor Singular Value Thresholding (IBTSVT). This method adopts a "divide and conquer" strategy by breaking the tensor into smaller blocks and processing them in the frequency domain.

1. Block Decomposition

Instead of processing the entire tensor at once, the algorithm splits it into many small blocks of uniform size (e.g., $n \times n \times n_3$). This allows the model to focus on local data correlations and sparse distributions that might be smoothed over in a global analysis.

Block decomposition and concatenation of a tensor.

2. t-SVD and Iterative Thresholding

The method utilizes the Tensor Singular Value Decomposition (t-SVD). By transforming the data into the Fourier domain, complex 3D relationships are simplified into a series of matrix operations. For each block, the algorithm iteratively applies a "soft thresholding" operator to the singular values. This effectively "mutes" the sparse, noisy parts while preserving the consistent, low-rank structure.

3. Concatenation and Reconstruction

Finally, all processed low-rank blocks are stitched back together using tensor concatenation operators to reconstruct the full low-rank component of the original data. The authors provide mathematical "incoherence conditions" to guarantee that this block-based factorization is theoretically sound and optimal.

Experimental Results

The researchers evaluated IBTSVT on two primary real-world benchmarks: surveillance video for motion separation and the Yale B Face Database for illumination normalization.

  • Face Recognition under Harsh Lighting: On the Yale B dataset, original shadowed images yielded a face detection rate of only 29.7%. While standard "Low rank + sparsity" methods improved this to 37.5%, the proposed IBTSVT method achieved a remarkable 84.4% detection rate.
  • Feature Preservation: IBTSVT achieved a 100% eye detection rate, a significant leap from the 58% detection rate in original images.
  • Computational Efficiency: While matrix-based RPCA is faster due to its simplicity, IBTSVT (715s) proved significantly more efficient than competing "Multiscale low rank" methods (4472s) while delivering superior accuracy.

Conclusion

IBTSVT offers a sharper lens for 3D data analysis by respecting both global structure and local details. By staying in the tensor format and utilizing block-based processing, it preserves spatial-temporal integrity and enables parallel computation. Future work will focus on automating the selection of block sizes and thresholding parameters to make the algorithm more adaptable to diverse sensor data.

Summary updated

Abstract

Tensor principal component analysis (TPCA) is a multi-linear extension of principal component analysis which converts a set of correlated measurements into several principal components. In this paper, we propose a new robust TPCA method to extract the princi- pal components of the multi-way data based on tensor singular value decomposition. The tensor is split into a number of blocks of the same size. The low rank component of each block tensor is extracted using iterative tensor singular value thresholding method. The prin- cipal components of the multi-way data are the concatenation of all the low rank components of all the block tensors. We give the block tensor incoherence conditions to guarantee the successful decom- position. This factorization has similar optimality properties to that of low rank matrix derived from singular value decomposition. Ex- perimentally, we demonstrate its effectiveness in two applications, including motion separation for surveillance videos and illumination normalization for face images.
BibTeX
@inproceedings{chen2017iterative,
  author = {Longxi Chen and Yipeng Liu and Ce Zhu},
  title = {{Iterative Block Tensor Singular Value Thresholding for Extraction of Low Rank Component of Image Data}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2017},
  url = {https://openreview.net/forum?id=-jlB7K2f1i},
}
Figure