Source-linked AI summary
Dimensionality Reduction on SPD Manifolds: The Emergence of Geometry-Aware Methods
Mehrtash Harandi, Mathieu Salzmann, Richard Hartley
TL;DR
High-dimensional SPD matrices offer useful geometry for visual recognition, but Riemannian computation becomes costly and Euclidean dimensionality reduction is inadequate. The paper learns orthonormal projections to lower-dimensional SPD manifolds, optimizing supervised discriminability or unsupervised variance on a Grassmann manifold. Across classification tasks, dimensionality reduction consistently improves accuracy over direct use of high-dimensional SPD matrices, with Stein especially powerful in supervised settings and log-Euclidean especially competitive unsupervised.
Problem
Riemannian computation on high-dimensional SPD manifolds is costly, limiting existing techniques despite their discriminative value for visual recognition.
Method
The paper learns an orthonormal projection from a high-dimensional SPD manifold to a lower-dimensional one, optimizing discriminative power or data variance on a Grassmann manifold.
Results
Dimensionality reduction consistently improved accuracy over directly using high-dimensional SPD matrices across the paper’s classification tasks.
Takeaways & Limitations
Stein divergence was particularly powerful for supervised reduction, while the log-Euclidean metric was highly competitive in the unsupervised case.
Takeaways & Limitations
The authors regard AIRM, Stein, and Jeffrey as geometrically more attractive than log-Euclidean, while acknowledging log-Euclidean’s usefulness as an AIRM substitute in several applications.
Abstract
from arXiv · showhide
Representing images and videos with Symmetric Positive Definite (SPD) matrices, and considering the Riemannian geometry of the resulting space, has been shown to yield high discriminative power in many visual recognition tasks. Unfortunately, computation on the Riemannian manifold of SPD matrices -especially of high-dimensional ones- comes at a high cost that limits the applicability of existing techniques. In this paper, we introduce algorithms able to handle high-dimensional SPD matrices by constructing a lower-dimensional SPD manifold. To this end, we propose to model the mapping from the high-dimensional SPD manifold to the low-dimensional one with an orthonormal projection. This lets us formulate dimensionality reduction as the problem of finding a projection that yields a low-dimensional manifold either with maximum discriminative power in the supervised scenario, or with maximum variance of the data in the unsupervised one. We show that learning can be expressed as an optimization problem on a Grassmann manifold and discuss fast solutions for special cases. Our evaluation on several classification tasks evidences that our approach leads to a significant accuracy gain over state-of-the-art methods.
1. Introduction
The paper addresses dimensionality reduction for high-dimensional SPD matrices, whose Riemannian computations are costly and whose geometry is poorly captured by Euclidean methods. It proposes supervised and unsupervised mappings to lower-dimensional SPD manifolds and reports improved recognition performance.
- SPD matrices support visual tasks including medical imaging, image segmentation, texture, pedestrian, face, and action recognition.
- Euclidean analysis is inadequate for SPD matrices because the SPD set is not a vector space and can produce physically unacceptable interpolation artifacts.In diffusion tensor imaging, Euclidean interpolation may yield intermediate determinants larger than both originals.
- AIRM provides a geometric SPD-manifold structure with affine-transformation invariance, but computational cost increases drastically with matrix dimension.This cost has led prior studies to favor low-dimensional SPD matrices, aside from some medium-sized features.
- The supervised formulation learns a lower-dimensional manifold by pulling together same-class samples and pushing apart different-class samples.Variants use AIRM, Stein divergence, or Jeffrey divergence; the latter two are motivated partly by faster computation and shared invariance properties.
- The unsupervised formulation maps data to a low-dimensional SPD manifold where training matrices are maximally separated from their mean.It likewise has AIRM-, Stein-, and Jeffrey-divergence variants.
- The approach outperforms state-of-the-art techniques on material categorization, face recognition, and action recognition from 3D motion capture sequences.
2. Background Theory
The background defines SPD matrices and their Riemannian geometry, then introduces Bregman-derived divergences and their invariance properties. These tools motivate the paper’s dimensionality-reduction formulations and their optimization machinery.
- An n × n SPD matrix is positive definite, and the SPD space forms the interior of a convex cone in an n(n + 1)/2-dimensional Euclidean space.
- AIRM equips the SPD space with a Riemannian structure and induces a geodesic distance that is invariant to affine transformations.
- The paper extends earlier work by adding an unsupervised dimensionality-reduction algorithm and Jeffrey-divergence variants for supervised and unsupervised methods.
- Bregman divergence is asymmetric, non-negative, and definite; the paper focuses on its symmetrized Stein and Jeffrey forms.
- The Stein divergence uses −log det(X) as a seed function with Jensen–Shannon symmetrization, while the Jeffrey divergence uses the same seed with direct symmetrization.
- Stein and Jeffrey divergences share affine-transform and inversion invariance with AIRM, motivating their use for SPD dimensionality reduction.
- The Stein divergence admits a Hilbert-space embedding through an RBF kernel, whereas the analogous AIRM property does not hold.
- The paper reports that a kernel based on the Jeffrey divergence is not positive definite because its kernel matrix can have a negative eigenvalue for β = 1/4.
3. DR on SPD Manifolds
The paper learns an orthonormal projection from high-dimensional SPD matrices to a lower-dimensional SPD manifold while preserving supervised discriminative structure or unsupervised variance. Both formulations become constrained optimization problems on a Grassmann manifold, solved with manifold-based methods.
- Mapping and constraints: The learned mapping f_W(X)=W^T XW embeds high-dimensional SPD matrices into a lower-dimensional SPD manifold using W∈R^n×m with m<n.Full-rank W ensures W^T XW remains positive definite; the paper imposes W^T W=I_m.
- Supervised dimensionality reduction: In the supervised setting, the projection minimizes intra-class distances while maximizing inter-class distances using AIRM, Stein, or Jeffrey divergences.The affinity function uses same-label and different-label nearest neighbours to encode within-class and between-class structure.
- Unsupervised dimensionality reduction: In the unsupervised setting, the projection seeks a low-dimensional SPD manifold whose training matrices have maximum collective distance from their manifold mean.This objective is motivated by PCA and Maximum Variance Unfolding, with variants based on AIRM, Stein, and Jeffrey divergences.
- Unsupervised dimensionality reduction: The unsupervised objective depends on a Fréchet mean, computed with a Riemannian mean for AIRM, CCCP for Stein divergence, and an analytic solution for Jeffrey divergence.The Jeffrey-divergence mean is obtained through a Riccati equation with a unique positive-definite solution.
- Optimization framework: Both supervised and unsupervised objectives are optimized under a unitary constraint on the Grassmann manifold because their nonlinear cost functions preclude standard eigenvalue solutions.The paper uses manifold-based Newton-type optimization, including conjugate-gradient methods on the Grassmannian.
4. Further Discussions
The section develops a log-Euclidean supervised dimensionality-reduction formulation, faster optimization alternatives, and practical implications for Region Covariance Matrices. It also contrasts these choices with geometrically richer SPD metrics and discusses implementation constraints.
- Log-Euclidean dimensionality reduction: The log-Euclidean metric maps SPD matrices through the matrix principal logarithm and supports supervised dimensionality reduction analogous to the earlier SPD-manifold formulation.The unsupervised adaptation can be derived similarly.
- Log-Euclidean dimensionality reduction: Because an analytic gradient for ∥log(W^T XW)−...∥_F with respect to W is unavailable, the method approximates log(W^T XW) by W^T log(X)W.The approximation is introduced to overcome the gradient difficulty.
- Optimization: The resulting optimization is posed on a Grassmann manifold, with an iterative eigen-decomposition solver that repeatedly updates F(W) and selects its m smallest eigenvectors.The solver initializes W with a truncated identity matrix and iterates until convergence.
- Optimization: 10 times faster than conjugate-gradient optimization on the Grassmannian, although conjugate gradient achieves a slightly lower error on the MOCAP experiment.The eigen-decomposition solution also converges much faster in Figure 4.
- Comparison and geometry: The formulation is simpler and faster than the compared log-det approach, while its symmetric projection leads to the less expensive optimization problem on G(m, n).The comparison concerns the rank-m positive semidefinite formulation of Huang et al.
- Comparison and geometry: AIRM, Stein, and Jeffrey divergences preserve nonlinear SPD geometry and affine invariance, whereas the log-Euclidean metric flattens the manifold but remains useful in several applications.This is presented as a geometrical trade-off rather than an absolute rejection of the log-Euclidean metric.
- Region Covariance Descriptors: For Region Covariance Matrices, the projected representation is itself an RCM with m observations, although valid original RCMs require r ≥ n.Applying W directly to observations reduces final RCM construction time because RCM computation is quadratic in feature dimensionality.
5. Related Work
Related work has reduced manifold data through tangent spaces, RKHS embeddings, or nonlinear Riemannian mappings. The paper instead targets a direct mapping from a high-dimensional SPD manifold to a lower-dimensional SPD manifold.
- Manifold-to-Euclidean methods: Most prior dimensionality-reduction methods map manifold-valued data to Euclidean space rather than between manifolds of different dimensions.The paper positions its approach as a direct high-dimensional-to-low-dimensional SPD mapping.
- Manifold-to-Euclidean methods: Tangent-space approaches such as Principal Geodesic Analysis flatten the manifold and have been applied to vertebrae outlines and motion-capture data.PGA is described as a generalization of principal component analysis.
- Manifold-to-Euclidean methods: Kernel PCA, kernel PLS, and kernel LDA embed manifolds into RKHSs, requiring a positive-definite kernel; Gaussian kernels may fail to preserve geodesic distances on non-flat manifolds.The cited discussion notes that strict use of the manifold structure is therefore questionable for these approaches.
- Direct Riemannian dimensionality reduction: Goh and Vidal extend LLE, Hessian LLE, and Laplacian Eigenmaps to Riemannian manifolds using logarithm maps, producing Euclidean embeddings after constructing an appropriate W.Their framework preserves neighboring properties during the embedding.
- Direct Riemannian dimensionality reduction: Prior covariance mappings learned between different-dimensional covariance matrices while ignoring SPD Riemannian geometry, unlike the paper’s geometry-aware formulation.The related-work passage identifies this as a distinction from the proposed approach.
- Geometry of Euclidean dimensionality reduction: Riemannian geometry has also been used to analyze Euclidean dimensionality-reduction methods through Stiefel-manifold geometry.This line of work differs from reducing SPD-manifold representations directly.
6. Empirical Evaluation
The evaluation tests supervised and unsupervised SPD dimensionality reduction across classification, clustering, and multiple SPD metrics. Learned low-dimensional manifolds substantially improve supervised recognition results, with strong gains on material, action, and face recognition tasks.
- Evaluation setup: Experiments evaluate supervised classification and unsupervised clustering, selecting the low-dimensional manifold size by cross-validation.The supervised experiments use nearest-neighbor and Riemannian sparse-coding classifiers, while unsupervised evaluation uses video clustering.
- Evaluation setup: The evaluated classifiers include nearest-neighbor methods and kernel sparse coding with AIRM, Stein, Jeffrey, or log-Euclidean geometry.Both high-dimensional and learned low-dimensional SPD manifolds are compared, alongside CDL and dataset-specific state-of-the-art baselines.
- Material categorization: 66.6% maximum accuracy is achieved on UIUC material categorization by kSC-S-DR, while dimensionality reduction boosts kSC-S by nearly 14%.The learned manifold also makes nearest-neighbor methods outperform the reported 43.5% state-of-the-art result.
- Action recognition: 81.9% best accuracy is achieved by kSC-S-DR on HDM05 action recognition, with nearest-neighbor and sparse-coding accuracies significantly improved by learning.The experiment uses 118 training and 188 test sequences from motion-capture data.
- Face recognition: 80.1% maximum accuracy is achieved by kSC-S-DR on YTC face recognition, exceeding the reported 78.2% holistic-descriptor result.For Stein-based nearest-neighbor classification, dimensionality reduction raises accuracy from 45.4% to 72.8%.
- Video clustering: In video clustering, log-Euclidean geometry achieves better accuracy on the dataset, while kernel k-means with Stein divergence surpasses its AIRM-based counterpart.The evaluation reports both clustering accuracy and normalized mutual information.
7. Conclusions and Future Work
The paper concludes that supervised and unsupervised mappings can reduce high-dimensional SPD manifolds while improving recognition accuracy. It identifies Stein divergence as particularly powerful for supervised reduction and log-Euclidean geometry as highly competitive for unsupervised reduction.
- Conclusions: The proposed approach provides both supervised and unsupervised mappings from high-dimensional SPD manifolds to lower-dimensional ones.The formulations study AIRM, Stein, Jeffrey, and log-Euclidean similarities.
- Conclusions: Dimensionality reduction consistently improves accuracy over directly using high-dimensional SPD matrices in the reported experiments.The conclusion summarizes gains across the paper’s recognition evaluations.
- Conclusions: Stein divergence is particularly powerful in the supervised case, while the log-Euclidean metric is highly competitive in the unsupervised case.The paper positions the framework as a step toward dimensionality reduction methods for Riemannian manifolds.
- Future work: Future work will extend the framework to other types of Riemannian manifolds.The paper is an extended and revised version of earlier work that added unsupervised and Jeffrey-divergence variants.
Appendix A. The equivalency between the length of curves under AIRM and the J-divergence
The appendix establishes equivalence between curve lengths induced by AIRM and the J-divergence through intrinsic-metric arguments. The proof reduces the analysis using affine invariance and local behavior near the identity matrix.
- Proof strategy: The appendix concludes the curve-length equivalence after analyzing the limiting behavior of the compared metrics near coincident points.The final steps use L’Hopital’s rule to evaluate an indefinite limit.
- Metric foundations: A curve in a metric space is defined as a continuous map joining an initial point to an endpoint.The appendix begins its proof by defining curves and their lengths without assuming differentiability.
- Metric foundations: Curve length is defined as the supremum of partition-based sums, and the intrinsic metric is the infimum of lengths over all paths between two points.These definitions provide the framework for comparing metrics through their induced intrinsic metrics.
- Metric comparison: If two metrics have identical intrinsic metrics up to scale, they induce curve lengths that agree up to the same scale.The appendix also states that uniformly equivalent metrics have identical intrinsic metrics.
- Proof strategy: Affine invariance reduces the metric analysis to behavior around the identity matrix, where nearby points can be represented through diagonal exponential coordinates.The proof uses a decomposition of X and invariance under orthogonal transformations to obtain this reduction.