Sparse Exact PGA on Riemannian Manifolds

Monami Banerjee, Rudrasis Chakraborty, Baba C. VemuriICCV 2017 · OpenReview

Abstract: Principal Component Analysis (PCA) is a widely popular dimensionality reduction technique for vector-valued inputs. In the past decade, a nonlinear generalization of PCA, called the Principal Geodesic Analysis (PGA) was developed to tackle data that lie on a smooth manifold. PGA suffers from the same problem as PCA in that, in both the methods, each Principal Component (PC) is a linear combination of the original variables. This makes it very difficult to interpret the PCs especially in high dimensions. This lead to the introduction of sparse PCA (SPCA) in the vector-space input case. In this paper, we present a novel generalization of SPCA, called sparse exact PGA (SEPGA) that can cope with manifold-valued input data and respect the intrinsic geometry of the underlying manifold. Sparsity has the advantage of not only easy interpretability but also computational efficiency. We achieve this by formulating the PGA problem as a minimization of the projection error in conjunction with sparsity constraints enforced on the principal vectors post isomorphic mapping to $\mathbb{R}^m$, where $m$ is the dimension of the manifold on which the data reside. Further, for constant curvature smooth manifolds, we use analytic formulae for the projection error leading to an efficient solution to the SEPGA problem. We present extensive experimental results demonstrating the performance of SEPGA in achieving very good sparse principal components without sacrificing the accuracy of reconstruction. This makes SEPGA accurate and efficient in representing manifold-valued data.

Introduction

Principal Component Analysis (PCA) is often considered the "Swiss Army knife" of dimensionality reduction. However, it faces two significant hurdles in modern data science. First, it assumes data resides in a flat Euclidean vector space, whereas data in fields like medical imaging or computer vision often lives on non-linear Riemannian manifolds (e.g., spheres or spaces of symmetric positive definite matrices). Second, standard PCA produces "dense" components where every original variable contributes to the result, making it difficult to interpret which specific features are most influential.

While Principal Geodesic Analysis (PGA) was developed to handle manifold data, it typically relies on "linearization"—flattening the manifold at the mean point. This approximation works for tightly clustered data but fails when data is spread out. Furthermore, existing PGA methods lack sparsity, hindering the identification of key dimensions. This paper introduces SEPGA (Sparse Exact Principal Geodesic Analysis) to address these limitations by combining exact manifold projection with sparsity constraints.

Methodology

SEPGA achieves interpretability and accuracy through three key innovations:

  1. Exact Objective Function: Instead of maximizing variance on a linearized space, SEPGA minimizes the reconstruction error directly on the manifold. This "exact" approach is significantly more robust to high-variance data than traditional linearized methods.
  2. Isomorphic Sparsity: Enforcing sparsity on manifolds is challenging because they lack a canonical basis. The authors resolve this by mapping the tangent space of the manifold to a standard vector space $\mathbb{R}^m$ using an isomorphism $\iota_\mu$. They then enforce an $\ell_1$-norm constraint on these mapped vectors to induce sparsity.
  3. Analytic Efficiency: Optimization on manifolds is typically computationally expensive. For manifolds with constant curvature (like hyperspheres or hyperbolic spaces), the authors utilize closed-form analytic formulae for the projection operator, making the algorithm feasible for high-dimensional datasets.
Isomorphic mapping from the tangent space $T_\mu M$ to $\mathbb{R}^m$ to enable sparsity constraints.

Experimental Evaluation

The performance of SEPGA was evaluated across several real-world and synthetic datasets:

  • OASIS Brain Scans: Shapes of the corpus callosum on the Kendall shape space.
  • Yale Face Database: SIFT descriptors converted into Symmetric Positive Definite (SPD) matrices.
  • KTH Action Recognition: HOG features mapped to the SPD manifold.
  • Synthetic Data: Points generated on a 2-sphere ($S^2$) to test performance under varying data variance.

Key Results and Discussion

Accuracy vs. Sparsity

On the OASIS dataset, SEPGA achieved an average sparsity of approximately 55-70% while maintaining reconstruction errors ($e_1$) comparable to or better than non-sparse exact PGA (ePGA). Qualitative results on corpus callosum shapes demonstrate that SEPGA can reconstruct complex biological shapes with as few as 50 sparse components, successfully capturing essential geometric features of the aging brain.

Reconstruction of corpus callosum shapes using SEPGA with varying sparsity levels ($r$).

Robustness and Interpretability

In synthetic tests on $S^2$ with high variance, SEPGA maintained an "expressed variance" (evar) of 0.98, while the linearized sparse PGA (sPGA) plummeted to 0.13. This highlights the "linearization trap" where standard approximations fail under high variance. Furthermore, SEPGA offers significant storage benefits; for the Yale Face dataset, it achieved near-perfect reconstruction using only 21% of the original dimensions.

Conclusion

SEPGA successfully brings the benefits of sparse PCA—interpretability and efficiency—to the manifold setting. By optimizing exact projection error, it maintains high accuracy even for widely dispersed data. While the current analytic solutions are optimized for constant curvature manifolds, future work may extend these shortcuts to a wider variety of manifold types or integrate SEPGA into deep learning architectures for manifold-valued data.

Summary updated

Abstract

Principal Component Analysis (PCA) is a widely popular dimensionality reduction technique for vector-valued inputs. In the past decade, a nonlinear generalization of PCA, called the Principal Geodesic Analysis (PGA) was developed to tackle data that lie on a smooth manifold. PGA suffers from the same problem as PCA in that, in both the methods, each Principal Component (PC) is a linear combination of the original variables. This makes it very difficult to interpret the PCs especially in high dimensions. This lead to the introduction of sparse PCA (SPCA) in the vector-space input case. In this paper, we present a novel generalization of SPCA, called sparse exact PGA (SEPGA) that can cope with manifold-valued input data and respect the intrinsic geometry of the underlying manifold. Sparsity has the advantage of not only easy interpretability but also computational efficiency. We achieve this by formulating the PGA problem as a minimization of the projection error in conjunction with sparsity constraints enforced on the principal vectors post isomorphic mapping to R <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> , where m is the dimension of the manifold on which the data reside. Further, for constant curvature smooth manifolds, we use analytic formulae for the projection error leading to an efficient solution to the SEPGA problem. We present extensive experimental results demonstrating the performance of SEPGA in achieving very good sparse principal components without sacrificing the accuracy of reconstruction. This makes SEPGA accurate and efficient in representing manifold-valued data.
BibTeX
@inproceedings{banerjee2017sparse,
  author = {Monami Banerjee and Rudrasis Chakraborty and Baba C. Vemuri},
  title = {{Sparse Exact PGA on Riemannian Manifolds}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2017},
  url = {https://openreview.net/forum?id=ry--7-f_bB},
}
Figure