[author]P. Thomas Fletcher, John Moeller, Jeff Phillips and Suresh Venkatasubramanian[/author]
In Algorithms And Data Structures Symposium (formerly WADS), 2011.

Abstract:

Many data analysis problems in machine learning, shape analysis, information theory and even mechanical engineering involve the study and analysis of collections of positive definite matrices. The space of such matrices P(n) is a Riemannian manifold with variable negative curvature. It includes Euclidean space and hyperbolic space as submanifolds, and poses significant challenges for the design of algorithms for data analysis.

In this paper, we develop foundational geometric structures and algorithms for analyzing collections of such matrices. A key technical contribution of this work is the use of \emph{horoballs}, a natural generalization of halfspaces for non-positively curved Riemannian manifolds. Horoballs possess some desirable properties of halfspaces (and balls) but are fundamentally more complex to work with because of the inherent curvature of the underlying space.

We propose generalizations of the notion of a convex hull and a centerpoint and develop algorithms for constructing such structures approximately by combining structural properties of horoballs with novel decompositions of P(n). Using these, we also prove that the VC-dimension of range spaces defined by horoballs is bounded in the case of P(2) (2 x 2 symmetric positive definite matrices).

Links:

• 2 page version at the 19th Fall Workshop on Computational Geometry
• Original version at the arxiv (arXiv:0912.1580v2 [cs.CG])
• Latest version (restructured, including new results on VC-dimension):

---

This material is based upon work supported by the National Science Foundation under Grant No. 0841185

Tags: CCF 0841185