Robust and Globally Sparse Pca via Majorization-Minimization and Variable Splitting

Sandeep Kumar, Hugo Brehier, Arnaud Breloy, Mohammed Nabil El Korso, Sandeep Kumar 0005ICASSP 2023 · DOI

TL;DR

This paper introduces a new algorithm for Principal Component Analysis (PCA) that is both robust to outliers and produces sparse, interpretable components. By combining a robust fitting criterion with a novel optimization approach using variable splitting and majorization-minimization, the method achieves a better trade-off between explained variance and sparsity compared to existing techniques, while also maintaining the orthogonality of the principal components.

What Problem Does This Paper Address?

Traditional PCA is a powerful tool for dimensionality reduction and data analysis, but it suffers from two main drawbacks: sensitivity to outliers and a lack of interpretability in the resulting components. Outliers can significantly distort the estimated principal components, leading to misleading results. Furthermore, standard PCA components are linear combinations of all original variables, making it difficult to pinpoint which variables are most influential or to perform variable selection. While robust PCA methods address the outlier issue and sparse PCA methods tackle interpretability, combining both robust and sparse properties in a principled way, while also preserving the desirable orthogonality of PCA components, has been a significant challenge.

Methods

The authors propose a novel algorithm for "Robust and Globally Sparse PCA" (MSPCA) that addresses these challenges. The core of their approach lies in a new formulation that combines:

  • Robust Subspace Recovery: They use a Huber-type cost function (Fq,δ) for fitting the subspace. This function is less sensitive to extreme values (outliers) than the standard least-squares approach, providing robustness.
  • Sparsity Promotion: They incorporate a mixed norm penalty (l2,1-norm) that encourages "structured sparsity." This means that the sparsity pattern is applied row-wise to the loading vectors, promoting the selection of entire groups of related variables or ensuring that a variable either contributes to all principal components or none.
  • Variable Splitting and MADMM: To handle the non-smooth sparsity penalty and the orthogonality constraint on the principal component loading matrix (U) simultaneously, they employ a variable splitting technique. This reformulates the problem into a form solvable by the Alternating Direction Method of Multipliers (ADMM), specifically a variant called MADMM (Manifold ADMM). This allows for efficient optimization by iteratively updating different parts of the problem.
  • Majorization-Minimization (MM): For the subproblem involving the U-update, which is constrained to the Stiefel manifold (ensuring orthogonality), they use a tailored majorization-minimization step. This technique approximates a complex objective function with a simpler, convex one that "majorizes" the original function, allowing for tractable updates.

Datasets

The paper evaluates its proposed method on two types of datasets:

  • Synthetic Data: Generated according to a Probabilistic PCA Model (PPCA) and a Haystack model to simulate inliers and outliers. This allows for controlled experiments to assess robustness and the recovery of the underlying subspace.
  • Microarray Gene Dataset (Khan Gene Data): A real-world dataset consisting of gene expression measurements from cancer patients. This dataset is used to evaluate the practical performance of MSPCA in terms of explained variance and sparsity on biological data.

Key Insights and Ideas

  • Bridging Robustness and Sparsity: The paper successfully demonstrates that it's possible to achieve both robustness to outliers and structured sparsity in PCA simultaneously, a combination that is not straightforward with existing methods.
  • Structured Sparsity Advantage: The use of the l2,1-norm penalty is highlighted as particularly beneficial for variable selection, as it encourages a more coherent and interpretable sparsity pattern across the principal components.
  • MADMM for Orthogonality: The application of MADMM is crucial for maintaining the orthogonality of the principal component basis, a property often relaxed in other sparse PCA methods, which can lead to correlated and less interpretable components.
  • MM for Stiefel Manifold Optimization: The tailored MM step for the U-update on the Stiefel manifold is a key algorithmic innovation that enables efficient optimization of the robust and sparse objective.

Key Results

  • Improved Robustness: On synthetic data, MSPCA shows a higher Average Fraction of Energy (AFE) compared to other methods, indicating better recovery of the true subspace even in the presence of outliers.
  • Better Orthonormality: MSPCA also demonstrates a lower non-orthogonality criterion (NOR), meaning the resulting principal components are closer to being orthogonal than those produced by some competing methods.
  • Competitive Sparsity-Performance Trade-off: On the Khan Gene Data, MSPCA achieves an AFE comparable to state-of-the-art methods while offering a good sparsity-performance trade-off.
  • Enhanced Class Separation: Visualizations of the first three principal components on the gene expression data show that MSPCA, especially with the l2,1-norm penalty, leads to clearer separation of different cancer classes, suggesting improved interpretability and discriminative power.

Limitations and Future Work

  • Parameter Tuning: While the paper mentions that the choice of q and δ in the Huber cost doesn't dramatically impact results, the regularization parameter λ for the sparsity penalty still requires tuning. The paper doesn't delve deeply into systematic methods for selecting λ.
  • Generalization to Other Robust Costs: The paper focuses on the Huber cost but notes that the proposed algorithm can be generalized to other robust cost functions. Exploring these other robust functions could lead to further improvements or different properties.
  • Computational Complexity: While MADMM is generally efficient, the computational cost for very high-dimensional datasets might still be a consideration. Further optimization or exploration of alternative algorithms could be beneficial.
  • Extension to Non-linear PCA: The current work focuses on linear PCA. Extending the robust and sparse principles to non-linear dimensionality reduction techniques could be a promising future direction.

Summary updated

BibTeX
@inproceedings{kumar2023robust,
  author = {Sandeep Kumar and Hugo Brehier and Arnaud Breloy and Mohammed Nabil El Korso and Sandeep Kumar},
  title = {{Robust and Globally Sparse Pca via Majorization-Minimization and Variable Splitting}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2023},
  doi = {10.1109/icassp49357.2023.10094882},
}
Figure