Advanced Multilinear Data Analysis and Sparse Representation Approaches and Their Applications

Khoa LuuSpectrum 2014

Abstract

Multifactor analysis is essential for interpreting real-world datasets where variables—such as identity, pose, and illumination—are deeply interdependent. Traditional methods like Multilinear PCA (MPCA) often fail because they are sensitive to noise, computationally expensive, and destructive to the data's underlying geometric structure. This paper presents two novel frameworks: Compressed Submanifold Multifactor Analysis (CSMA) for robust tensor decomposition and Sparse Class-dependent Feature Analysis (SCFA) for high-accuracy pattern classification. By integrating $\ell_1$-norm optimization, random projections, and sparse representation, these methods provide superior performance in face recognition, object classification, and data restoration tasks.

Introduction

In modern computer vision, data is rarely the product of a single factor. A facial image, for instance, is a complex combination of identity, expression, and environmental lighting. To analyze such data, researchers utilize tensors (multi-dimensional arrays). While Multilinear PCA (MPCA) has been a staple for tensor decomposition, it possesses three critical vulnerabilities: it is highly sensitive to outliers due to its reliance on the $\ell_2$-norm, it scales poorly with massive datasets, and it tends to blur local geometric structures through its averaging processes.

Furthermore, in pattern classification, existing dictionary-based methods often rely on simplistic discriminative functions, while filter-based methods like Kernel Class-dependent Feature Analysis (KCFA) are frequently hampered by their reliance on raw pixel values. This makes them fragile when faced with occlusions or significant appearance variations. This research addresses these gaps by leveraging the robustness of the $\ell_1$-norm and the efficiency of compressed sensing.

Compressed Submanifold Multifactor Analysis (CSMA)

To address the limitations of traditional multilinear analysis, the CSMA framework introduces three key innovations:

1. Robust Decomposition via HOSVD-$\ell_1$

Standard Higher-order Singular Value Decomposition (HOSVD) uses the $\ell_2$-norm, which squares error terms and thus over-prioritizes outliers. CSMA replaces this with a novel $\ell_1$-norm formulation. Solved using the Alternating Direction Method of Multipliers (ADMM), this approach allows the model to naturally isolate sparse outliers and perform "tensor completion," effectively filling in missing values in a dataset.

2. Computational Efficiency through Random Projections

Processing high-dimensional tensors is traditionally a $O(dn^2)$ operation. CSMA utilizes Random Projections to map data into a lower-dimensional subspace before decomposition. This reduces the computational complexity to $O(dn \log n)$ while preserving the essential pairwise distances between data points, ensuring that speed does not come at the cost of accuracy.

3. Preserving Local Geometry

Unlike MPCA, which averages data structures and loses the unique "curves" of the data manifold, CSMA employs an Adaptive Local Coordinate Alignment strategy. Using a Stratified Procrustes approach, it aligns local coordinates to preserve the true geometric shape of the data submanifolds, leading to more representative feature extraction.

Sparse Class-dependent Feature Analysis (SCFA)

For the task of classification, the research introduces SCFA, which bridges the gap between sparse representation and nonlinear filtering.

  • Sparse Coefficient Extraction: Rather than processing raw pixels, SCFA uses the K-SVD algorithm to learn an overcomplete dictionary. It then extracts sparse coefficients that represent the data more robustly.
  • $\ell_1$-norm Filter Design: These coefficients are passed through optimal class-specific filters. The filter design is framed as an $\ell_1$-norm optimization problem, making the classifier significantly more tolerant to noise and occlusions (e.g., a subject wearing sunglasses or a scarf).
  • Non-linear Extension: The method is further extended into a Reproducing Kernel Hilbert Space (RKHS) to handle complex, non-linear classification boundaries.

Experimental Results and Discussion

The proposed methods were evaluated against several benchmark datasets, including CMU-PIE, Extended Yale-B, and the AR database.

Data Restoration and Inpainting

CSMA demonstrated remarkable resilience to missing data, successfully reconstructing tensors with up to 70% of their values removed. In image inpainting tests with 90% missing pixels, CSMA achieved a Peak Signal-to-Noise Ratio (PSNR) of 27.1 dB. Notably, it achieved these results in 397 seconds, nearly twice as fast as state-of-the-art methods like FaLRTC (745 seconds).

Face Recognition and Object Classification

SCFA set new benchmarks for accuracy and robustness:

  • Extended Yale-B: Achieved 98.64% accuracy, outperforming K-SVD and SRC under heavy illumination variations.
  • AR Database: Achieved 99.17% accuracy, proving extreme robustness against occlusions like scarves and sunglasses.
  • Caltech101: Reached 74.9% accuracy in general object classification, outperforming standard dictionary-based methods.
  • Inference Speed: SCFA recognized test faces in approximately 4.9ms, a significant improvement over the 91ms required by standard Sparse Representation-based Classification (SRC).

Conclusion

This research demonstrates that shifting from $\ell_2$ to $\ell_1$-norm optimization is a "game-changer" for high-dimensional data analysis. By combining this robustness with the efficiency of random projections and the discriminative power of sparse coefficients, the CSMA and SCFA frameworks offer a powerful solution for modern computer vision challenges. These methods not only improve accuracy in the presence of noise and occlusions but also provide the computational scalability required for large-scale real-world applications.

Summary updated

Abstract

Multifactor analysis plays an important role in data analysis since most real-world datasets usually exist with a combination of numerous factors. These factors are usually not independent but interdependent together. Thus, it is a mistake if a method only considers one aspect of the input data while ignoring the others. Although widely used, Multilinear PCA (MPCA), one of the leading multilinear analysis methods, still suffers from three major drawbacks. Firstly, it is very sensitive to outliers and noise and unable to cope with missing values. Secondly, since MPCA deals with huge multidimensional datasets, it is usually computationally expensive. Finally, it loses original local geometry structures due to the averaging process. This thesis sheds new light on the tensor decomposition problem via the ideas of fast low-rank approximation in random projection and tensor completion in compressed sensing. We propose a novel approach called Compressed Submanifold Multifactor Analysis (CSMA) to solve the three problems mentioned above. Our approach is able to deal with the problem of missing values and outliers via our proposed novel sparse Higher-order Singular Value Decomposition approach, named HOSVD-L1 decomposition. The Random Projection method is used to obtain the fast low-rank approximation of a given multifactor dataset.
\nIn addition, our method can preserve geometry of the original data.
\n
\nIn the second part of this thesis, we present a novel pattern classification approach named Sparse Class-dependent Feature Analysis (SCFA), to connect the advantages of sparse representation in an overcomplete dictionary, with a powerful nonlinear classifier. The classifier is based on the estimation of class-specific optimal filters, by solving an L1-norm optimization problem using the Alternating Direction Method of Multipliers. Our method as well as its Reproducing Kernel Hilbert Space (RKHS) version is tolerant to the presence of noise and other variations in an image. Our proposed methods achieve very high classification accuracies in face recognition on two challenging face databases, i.e. the CMU Pose, Illumination and Expression (PIE) database and the Extended YALE-B that exhibit pose and illumination variations; and the AR database that has occluded images. In addition, they also exhibit robustness on other evaluation modalities, such as object classification on the Caltech101 database. Our method outperforms state-of-the-art methods on all these databases and hence they show their applicability to general computer vision and pattern recognition problems.
BibTeX
@inproceedings{luu2014advanced,
  author = {Khoa Luu},
  title = {{Advanced Multilinear Data Analysis and Sparse Representation Approaches and Their Applications}},
  booktitle = {Spectrum},
  year = {2014},
}
Figure