Structured Sparse Principal Component Analysis

Rodolphe Jenatton, Guillaume Obozinski, Francis R. Bach

Abstract

We present Structured Sparse Principal Component Analysis (SSPCA), an extension of sparse dictionary learning where sparsity patterns are constrained to specific geometric shapes. By incorporating spatial priors through a novel structured sparsity-inducing norm, SSPCA produces interpretable dictionary elements that are robust to noise and occlusions. Our results on synthetic data and face recognition benchmarks demonstrate significant improvements over standard PCA and unstructured Sparse PCA.

Introduction

Principal Component Analysis (PCA) is a fundamental tool for dimensionality reduction, yet its components are typically dense, involving all input variables. While Sparse PCA (SPCA) addresses this by inducing sparsity, it treats variables as independent, often resulting in disjointed "salt-and-pepper" patterns. In domains like computer vision or genomics, data possesses an inherent spatial or functional structure. We propose SSPCA to bridge this gap, forcing dictionary elements to adhere to meaningful geometric structures such as rectangles or polygons.

Methodology

We formulate the problem as a dictionary learning task, decomposing a data matrix $X \in \mathbb{R}^{n \times p}$ into a dictionary $V \in \mathbb{R}^{p \times r}$ and coefficients $U \in \mathbb{R}^{n \times r}$. The objective function incorporates a structured sparsity-inducing norm $\Omega(v)$ that penalizes non-convex or scattered supports.

Structured Sparsity and Convex Shapes

The core of our approach is the definition of groups of variables that are zeroed out together. For 2D grid data like images, we define groups as horizontal and vertical half-planes. By intersecting these groups, the regularization forces the support of the dictionary elements to form convex shapes.

The intersection of horizontal and vertical half-plane groups allows the model to constrain sparsity patterns to convex rectangular regions.

Non-Convex Optimization

To achieve sharper, more salient features, we employ a non-convex variant of the penalty ($\ell_\alpha$ with $\alpha < 1$). This aggressively suppresses small coefficients, leading to cleaner dictionary elements compared to standard convex norms. The optimization is solved using a Block Coordinate Descent (BCD) scheme, leveraging a variational formulation to simplify the non-convex penalty into a sequence of simpler quadratic problems.

Experimental Results

We evaluated SSPCA on synthetic datasets and the AR Face Database.

Synthetic Denoising

On a 20x20 grid with hidden geometric factors, SSPCA achieved a normalized estimation error of 0.34 under high noise (SNR = 0.5), outperforming PCA (0.41) and SPCA (0.40).

Face Recognition under Occlusion

The AR Face Database, featuring 2,600 images with expressions and occlusions (sunglasses, scarves), served as a robust testbed. SSPCA naturally identifies facial "parts" like eyes or mouths. Quantitatively, SSPCA and its "shared" variant consistently outperformed NMF and SPCA in classification accuracy as the dictionary size increased.

Comparison of classification accuracy on the AR Face Database. SSPCA and shared-SSPCA significantly outperform standard PCA, SPCA, and NMF, especially as the dictionary size grows.

Conclusion

SSPCA provides a powerful framework for learning structured, interpretable representations. By encoding geometric priors directly into the optimization, the model gains resilience to noise and occlusions. Future work will explore the mathematical identifiability of the model and its application to multi-task learning scenarios.

Summary updated

Abstract

We present an extension of sparse PCA, or sparse dictionary learning, where the sparsity patterns of all dictionary elements are structured and constrained to belong to a prespecified set of shapes...
BibTeX
@inproceedings{jenatton2010structured,
  author = {Rodolphe Jenatton and Guillaume Obozinski and Francis R. 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