amanpg: Alternating Manifold Proximal Gradient Method for Sparse PCA

Shixiang Chen, Justin K. Huang, Benjamin Jochem, Shiqian Ma, Haichuan Xu, Lingzhou Xue, Zhong Zheng, Hui ZouOpenalex Unknown 2021 · DOI · OpenAlex

Abstract

Alternating Manifold Proximal Gradient Method for Sparse PCA uses the Alternating Manifold Proximal Gradient (AManPG) method to find sparse principal components from a data or covariance matrix. It provides a novel algorithm for solving the sparse principal component analysis problem which provides advantages over existing methods in terms of efficiency and convergence guarantees. Chen, S., Ma, S., Xue, L., & Zou, H. (2020); Zou, H., Hastie, T., & Tibshirani, R. (2006); Zou, H., & Xue, L. (2018).

Introduction

Standard Principal Component Analysis (PCA) is a cornerstone of data science, used to reduce dimensionality by finding a set of orthogonal vectors that capture the most variance in a dataset. However, PCA has a significant drawback in high-dimensional contexts: each principal component is typically a linear combination of all original variables. In fields like genomics or finance, this lack of sparsity makes results difficult to interpret.

Sparse PCA (SPCA) addresses this by forcing many of the "loadings" (the weights of the variables) to be zero. While this improves interpretability, it introduces a complex mathematical challenge. Researchers must simultaneously satisfy two conflicting goals: maintaining the orthogonality of components (a non-convex constraint on the Stiefel manifold) and achieving sparsity (a non-smooth objective usually handled via L1-norm penalties).

The AManPG Methodology

The amanpg package implements the Alternating Manifold Proximal Gradient (AManPG) method. This approach is "alternating" because it decomposes the complex optimization problem into manageable sub-problems, leveraging both manifold optimization and proximal gradient techniques.

Manifold Optimization and Proximal Mapping

Instead of treating the orthogonality constraint as a barrier, the algorithm treats the space of orthogonal matrices as a "manifold"—a smooth geometric surface. It takes steps along this surface to ensure components remain orthogonal throughout the process. To handle the non-smooth L1 penalty that induces sparsity, the algorithm utilizes a proximal mapping function, prox.l1.

The prox.l1 function handles the proximal mapping for L1 regularization, requiring an input matrix and specific parameters to calculate the mapping.

As shown in the implementation details for prox.l1, the mapping requires the input matrix z, the penalty parameter lambda, and the number of columns r. This operator effectively "shrinks" small values to zero, ensuring the resulting components are sparse while maintaining the geometric structure of the problem. This dual approach leads to more stable and efficient convergence compared to heuristic methods that often sacrifice orthogonality for sparsity.

Implementation and Usage

The amanpg package is designed for flexibility, allowing users to work with either raw data matrices or sample covariance matrices. Before processing, data often requires normalization to ensure that different scales of measurement do not bias the principal components.

The normalization function allows users to center and scale the input matrix, ensuring the data is prepared for the Sparse PCA algorithm.

The package provides built-in utilities to center the input matrix to a mean of zero and scale it to a Euclidean length of 1. This preprocessing is critical for the AManPG algorithm to function optimally. Users can control the trade-off between variance explained and sparsity through two primary parameters: lambda1 (for L1-norm sparsity) and lambda2 (for L2-norm regularization).

Key Results and Performance

One of the primary advantages of AManPG is its theoretical backing. Unlike many Sparse PCA solvers, AManPG is mathematically guaranteed to converge to a stable solution. In practical applications, the algorithm demonstrates impressive computational speed. For example, it can process a $1000 \times 500$ matrix and extract four sparse components in just a few seconds.

The package provides users with several key metrics to evaluate the results:

  • Sparsity Metrics: The ratio of zero loadings to total loadings, quantifying the interpretability of the components.
  • Convergence Monitoring: The final gradient value (f_amanpg) and the iteration count, providing transparency into the optimization process.

Conclusion and Future Directions

While amanpg offers a robust and efficient solution for Sparse PCA, it does require the user to manually select penalty parameters, which may necessitate external cross-validation. Furthermore, while highly efficient for standard R memory structures, extremely high-dimensional "big data" may still present memory challenges. Future developments of the AManPG framework could potentially extend these manifold-constrained optimization techniques to other areas, such as Sparse Canonical Correlation Analysis (SCCA).

Summary updated

Abstract

Alternating Manifold Proximal Gradient Method for Sparse PCA uses the Alternating Manifold Proximal Gradient (AManPG) method to find sparse principal components from a data or covariance matrix. Provides a novel algorithm for solving the sparse principal component analysis problem which provides advantages over existing methods in terms of efficiency and convergence guarantees. Chen, S., Ma, S., Xue, L., &amp; Zou, H. (2020) &lt;<a href="https://doi.org/10.1287%2Fijoo.2019.0032" target="_top">doi:10.1287/ijoo.2019.0032</a>&gt;. Zou, H., Hastie, T., &amp; Tibshirani, R. (2006) &lt;<a href="https://doi.org/10.1198%2F106186006X113430" target="_top">doi:10.1198/106186006X113430</a>&gt;. Zou, H., &amp; Xue, L. (2018) &lt;<a href="https://doi.org/10.1109%2FJPROC.2018.2846588" target="_top">doi:10.1109/JPROC.2018.2846588</a>&gt;.
BibTeX
@inproceedings{chen2021amanpg,
  author = {Shixiang Chen and Justin K. Huang and Benjamin Jochem and Shiqian Ma and Haichuan Xu and Lingzhou Xue and Zhong Zheng and Hui Zou},
  title = {{amanpg: Alternating Manifold Proximal Gradient Method for Sparse PCA}},
  booktitle = {Openalex Unknown},
  year = {2021},
  doi = {10.32614/cran.package.amanpg},
}
Figure