Structured Sparse Principal Component Analysis

Rodolphe Jenatton, Guillaume Obozinski, Francis Bach

TL;DR

This paper introduces "Structured Sparse Principal Component Analysis" (SSPCA), a novel method that extends traditional sparse PCA by incorporating structural constraints on the learned components. This allows for more interpretable and robust feature extraction, particularly in applications like face recognition where local features are important.

What Problem Does This Paper Address?

Principal Component Analysis (PCA) is a fundamental technique for reducing data dimensionality by finding orthogonal components that capture the most variance. However, standard PCA often results in components that are linear combinations of all original variables, making them difficult to interpret. Sparse PCA (SPCA) addresses this by seeking components that are sparse, meaning they only involve a subset of the original variables. While SPCA is an improvement, it often doesn't go far enough. Many real-world data types have inherent structures (e.g., pixels in an image forming a grid, genes in biological pathways). Simply enforcing sparsity doesn't leverage this existing structure. This paper tackles the problem of how to incorporate these known structural priors into the PCA framework to learn more meaningful and robust components.

Methods

The core contribution is the development of Structured Sparse Principal Component Analysis (SSPCA). This method builds upon the idea of structured sparsity-inducing norms, previously introduced for general regression and classification problems. The key innovation is to adapt these norms for the dictionary learning framework, which is closely related to PCA.

Here's a breakdown of the approach:

  • Structured Regularization: Instead of just penalizing the number of non-zero elements in a component (like in standard SPCA), SSPCA uses a regularization term that encourages components to have supports (patterns of non-zero elements) belonging to a predefined set of "shapes" or structures. For example, in image data, these shapes could be rectangular regions.
  • Dictionary Learning Formulation: The problem is framed as a dictionary learning task, where the goal is to find a dictionary (a set of components) that can reconstruct the input data well. This is formulated as a matrix factorization problem.
  • Non-Convex Optimization: The proposed structured regularization leads to a non-convex optimization problem. The authors propose an efficient block-coordinate descent (BCD) algorithm to solve this. This algorithm iteratively updates different parts of the model (dictionary elements, decomposition coefficients) while keeping others fixed, leveraging closed-form solutions or efficient projections where possible.
  • Extension to Shared Structure: The paper also introduces a way to enforce shared structures across dictionary elements, meaning multiple components might be constrained to have similar sparsity patterns. This is achieved by defining partitions of the dictionary elements and applying a structured norm to these groups.

Datasets

  • AR Face Database: Used for face recognition experiments. This dataset consists of face images with varying poses and occlusions (sunglasses, scarfs). The images were downsampled for computational efficiency.
  • EF-CAM Protein Complex Data: Used to study the dynamics of protein complexes. This dataset represents the successive positions of residues in a protein complex, with each residue described by its 3D coordinates.

Key Insights and Ideas

  • Structure is Key for Interpretability: Simply making components sparse isn't enough. Incorporating known structural information (like spatial locality in images) leads to components that are not only sparse but also more interpretable and aligned with domain knowledge.
  • SSPCA Outperforms Unstructured Methods on Occlusions: In face recognition, SSPCA's ability to learn localized features makes it more robust to occlusions (like sunglasses) compared to methods that learn unconstrained sparse patterns.
  • Capturing Biological Structures: Applying SSPCA to protein complex dynamics revealed biologically meaningful substructures, such as protein tails and interfaces, demonstrating its utility in scientific data analysis.
  • Efficient Optimization for Non-Convex Problems: The development of a block-coordinate descent algorithm with closed-form updates is crucial for making structured sparse learning practical.

Key Results

  • Face Recognition: SSPCA achieved better correct classification rates than PCA, NMF, and standard SPCA when classifying occluded faces using a k-NN classifier. For instance, with a dictionary size of 30, SSPCA achieved around 40% correct classification, while SPCA was around 25% and NMF around 35%. Shared-SSPCA (SSPCA with shared patterns) also showed strong performance.
  • Protein Complex Dynamics: SSPCA successfully identified known energetically stable substructures of the EF-CAM complex, aligning with existing biological knowledge. The learned dictionary elements corresponded to small, spatially coherent regions of the complex.

Limitations and Future Work

  • Non-Convexity Sensitivity: The authors acknowledge that the non-convex nature of the optimization problem means the results can be sensitive to initialization. They address this in experiments by running the algorithm multiple times with different initializations.
  • Parameter Tuning: Selecting the regularization parameter $\lambda$ and the structure parameter $\alpha$ can be challenging and requires cross-validation.
  • Future Directions:
    • Refining the optimization scheme for better sparsity exploitation.
  • Applying structured sparsity-inducing norms to multi-task learning to leverage structure between tasks.
  • Exploring non-linear classification methods or advanced feature engineering (like Laplacian filters) for improved performance in applications like face recognition.

Summary updated

Abstract

Principal component analysis (PCA) is an essential tool for data analysis and unsupervised dimensionality reduction, whose goal is to find, among linear combinations of the data variables, a sequence of orthogonal factors that most efficiently explain the variance of the observations. One of its main shortcomings is that, even if PCA finds a small number of important factors, the factor themselves typically involve all original variables. In the last decade, several alternatives to PCA which find sparse and potentially interpretable factors have been proposed, notably nonnegative matrix factorization (NMF) [1] and sparse PCA (SPCA) [2]. However, in many applications, only constraining the size of the factors does not seem appropriate because the considered factors are not only expected to be sparse but also to have a certain structure. In fact, the popularity of NMF for face image analysis owes essentially to the fact that the method happens to retrieve sets of variables that are localized on the face and capture some parts of the face which seem intuitively meaningful given our prior information. We might therefore gain in the quality of the factors induced by enforcing directly this a priori in the matrix factorization constraints. More generally, it is desirable to encode higher-order information about the supports that reflects the structure of the data. For example, in computer vision, features associated to the pixels of an image
BibTeX
@inproceedings{jenatton2010structured,
  author = {Rodolphe Jenatton and Guillaume Obozinski and Francis Bach},
  title = {{Structured Sparse Principal Component Analysis}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2010},
  url = {https://openreview.net/forum?id=MzJfhMvH0kx},
}
Figure