2011 | OriginalPaper | Chapter
Horoball Hulls and Extents in Positive Definite Space
Authors : P. Thomas Fletcher, John Moeller, Jeff M. Phillips, Suresh Venkatasubramanian
Published in: Algorithms and Data Structures
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The space of positive definite matrices P(
n
) is a Riemannian manifold with variable nonpositive 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
horoballs
, a natural generalization of halfspaces for non-positively curved Riemannian manifolds. We propose generalizations of the notion of a convex hull and a centerpoint and approximations of these structures using horoballs and based on novel decompositions of P(
n
). This leads to an algorithm for approximate hulls using a generalization of extents.