TL;DR
This paper introduces a novel method called Iterative Block Tensor Singular Value Thresholding (IBTSVT) to extract low-rank components from high-dimensional data represented as tensors. By decomposing the tensor into smaller blocks and applying a modified singular value thresholding technique to each block, IBTSVT effectively separates background from foreground in surveillance videos and normalizes illumination in face images, outperforming existing methods.
What Problem Does This Paper Address?
High-dimensional data, often represented as tensors, is prevalent in fields like image and video processing. While Principal Component Analysis (PCA) is a standard technique for 2D data, extending it to tensors (Tensor PCA) is crucial for leveraging the inherent structure of multi-way data. Existing tensor decomposition methods often struggle with the computational complexity of large tensors or don't fully exploit the data's structure. Specifically, robust PCA (RPCA) aims to decompose data into a low-rank component and a sparse component, but applying it directly to large tensors can be inefficient. This paper addresses the challenge of efficiently and effectively extracting low-rank components from large tensors, particularly when the data exhibits block-like structures, by proposing a block-wise decomposition approach.
Methods
The core of the proposed method, IBTSVT, lies in decomposing the input tensor $X \in \mathbb{R}^{n_1 \times n_2 \times n_3}$ into multiple smaller block tensors, $X_p$, each of size $n \times n \times n_3$. For each block tensor $X_p$, the goal is to decompose it into a low-rank component $L_p$ and a sparse component $S_p$, such that $X_p = L_p + S_p$. The extraction of the low-rank component $L_p$ is achieved by minimizing its tensor nuclear norm, which is related to the sum of singular values of its frontal slices after a Fast Fourier Transform (FFT) along the third dimension.
The paper introduces "block tensor incoherence conditions" to ensure successful decomposition. The actual low-rank component extraction for each block uses an iterative singular value thresholding approach in the Fourier domain. This involves applying a soft thresholding operator, denoted by $D_{\tau}$, to the block tensor's transformed representation. The thresholding parameter $\tau$ is crucial and is discussed as being experience-based, with a suggestion of $\tau = 1/\sqrt{nn_3}$ for denoising, but acknowledging that it needs adjustment for applications with non-uniformly distributed sparse components. The final low-rank component of the original tensor is obtained by concatenating the low-rank components of all the blocks.
Datasets
The paper evaluates its method on two real-world datasets:
- Surveillance Videos: A dataset of 20 frames, each of size $144 \times 176$, is used for motion separation.
- Yale B Face Database: This dataset consists of face images of size $192 \times 168$ captured under 64 different lighting conditions, used for illumination normalization.
Key Insights and Ideas
- Block-wise Decomposition for Efficiency: Decomposing a large tensor into smaller blocks significantly reduces computational complexity compared to processing the entire tensor at once. This is a key enabler for handling large-scale tensor data.
- Leveraging Block Structure: The method explicitly assumes and exploits the idea that some data might have inherent block structures, making a block-wise approach more effective than a global one.
- Iterative Thresholding for Low-Rank Extraction: The use of iterative singular value thresholding, adapted for tensors via the t-SVD and FFT, is a robust way to extract the low-rank component from each block.
- Importance of Incoherence Conditions: The paper highlights the theoretical necessity of "block tensor incoherence conditions" for guaranteeing the successful separation of low-rank and sparse components.
- Adaptive Thresholding: The authors recognize that the thresholding parameter is application-dependent, especially when dealing with non-uniform sparse components like shadows or motion, suggesting the need for careful tuning.
Key Results
The IBTSVT method demonstrates strong performance in two applications:
- Motion Separation for Surveillance Videos: The method successfully separates the background (low-rank component) from moving objects (sparse component), visually identifying pedestrians in the video.
- Illumination Normalization for Face Images: IBTSVT effectively removes shadows and illumination variations from face images, resulting in "almost shadow-free faces." This is quantitatively shown by a significant improvement in face and eye detection accuracy using the Viola-Jones algorithm.
- Face Detection Accuracy: IBTSVT achieved 0.844, compared to 0.375 for low rank + sparsity and 0.359 for multiscale low rank.
- Eye Detection Accuracy: IBTSVT achieved 1.00, matching the multiscale low rank method but significantly outperforming low rank + sparsity (0.70).
- Computational Time: IBTSVT was significantly faster, processing 64 face images in 715 seconds, compared to 10 seconds for low rank + sparsity and 4472 seconds for multiscale low rank. The speedup is attributed to parallel processing of block tensors.
Limitations and Future Work
- Block Size Selection: The paper notes that the block size is a critical parameter. If too large, the sparse part might contain low-rank components; if too small, computational time increases due to the large number of t-SVDs. The authors suggest a block size of $2 \times 2 \times n_3$ as a general choice.
- Thresholding Parameter Tuning: The thresholding parameter $\tau$ is identified as difficult to determine and is currently set based on experience. The paper suggests that for different applications with non-uniformly distributed sparse components, this parameter needs careful adjustment.
- Future Work: The paper's success in these two applications suggests that IBTSVT could be applied to other problems involving high-dimensional data with block structures, such as shadow removal in general images or motion segmentation in other types of video data. Further research could focus on developing more principled methods for block size selection and automatic thresholding parameter estimation.
Summary updated