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.
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.
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