In this paper, we present algorithms for computing approximate hulls and centerpoints for collections of matrices in positive definite space. There are many applications where the data under consideration, rather than being points in a Euclidean space, are positive definite (p.d.) matrices. These applications include diffusion tensor imaging in the brain, elasticity analysis in mechanical engineering, and the theory of kernel maps in machine learning. Our work centers around the notion of a horoball: the limit of a ball fixed at one point whose radius goes to infinity. Horoballs possess many (though not all) of the properties of halfspaces; in particular, they lack a strong separation theorem where two horoballs can completely partition the space. In spite of this, we show that we can compute an approximate "horoball hull" that strictly contains the actual convex hull. This approximate hull also preserves geodesic extents, which is a result of independent value: an immediate corollary is that we can approximately solve problems like the diameter and width in positive definite space. We also use horoballs to show existence of and compute approximate robust centerpoints in positive definite space, via the horoball-equivalent of the notion of depth.
The mathematics of Riemannian manifolds, Cartan-Hadamard manifolds and @math is well-understood: the book by Bridson and Haefliger @cite_2 is an invaluable reference on metric spaces of nonpositive curvature, and Bhatia @cite_17 provides a detailed study of @math in particular. However, there are many fewer algorithmic results for problems in these spaces. To the best of our knowledge, the only prior work on algorithms for positive definite space are the work by Moakher @cite_3 on mean shapes in positive definite space, and papers by Fletcher and Joshi @cite_22 on doing principal geodesic analysis in symmetric spaces, and the robust median algorithms of Fletcher @cite_4 for general manifolds (including @math and @math ).
@cite_4 @cite_22 @cite_3 @cite_2 @cite_17
1968781546 2030605635 2963747906 1985415289
We dene a notion of a measured length space X having nonnegative N-Ricci curvature, for N 2 [1;1), or having1-Ricci curvature bounded below byK, forK2 R. The denitions are in terms of the displacement convexity of certain functions on the associated Wasserstein metric space P2(X) of probability measures. We show that these properties are preserved under measured Gromov-Hausdor limits. We give geometric and analytic consequences. This paper has dual goals. One goal is to extend results about optimal transport from the setting of smooth Riemannian manifolds to the setting of length spaces. A second goal is to use optimal transport to give a notion for a measured length space to have Ricci curvature bounded below. We refer to [11] and [44] for background material on length spaces and optimal transport, respectively. Further bibliographic notes on optimal transport are in Appendix F. In the present introduction we motivate the questions that we address and we state the main results. To start on the geometric side, there are various reasons to try to extend notions of curvature from smooth Riemannian manifolds to more general spaces. A fairly general setting is that of length spaces, meaning metric spaces (X;d) in which the distance between two points equals the inmum of the lengths of curves joining the points. In the rest of this introduction we assume that X is a compact length space. Alexandrov gave a good notion of a length space having bounded below by K", with K a real number, in terms of the geodesic triangles in X. In the case of a Riemannian manifold M with the induced length structure, one recovers the Riemannian notion of having sectional curvature bounded below by K. Length spaces with Alexandrov curvature bounded below by K behave nicely with respect to the GromovHausdor topology on compact metric spaces (modulo isometries); they form A convenient way of analysing Riemannian manifolds is to embed them in Euclidean spaces, with the embedding typically obtained by flattening the manifold via tangent spaces. This general approach is not free of drawbacks. For example, only distances between points to the tangent pole are equal to true geodesic distances. This is restrictive and may lead to inaccurate modelling. Instead of using tangent spaces, we propose embedding into the Reproducing Kernel Hilbert Space by introducing a Riemannian pseudo kernel. We furthermore propose to recast a locality preserving projection technique from Euclidean spaces to Riemannian manifolds, in order to demonstrate the benefits of the embedding. Experiments on several visual classification tasks (gesture recognition, person re-identification and texture classification) show that in comparison to tangent-based processing and state-of-the-art methods (such as tensor canonical correlation analysis), the proposed approach obtains considerable improvements in discrimination accuracy. By using optimal mass transportation and a quantitative Holder inequality, we provide estimates for the Borell–Brascamp–Lieb deficit on complete Riemannian manifolds. Accordingly, equality cases in Borell–Brascamp–Lieb inequalities (including Brunn–Minkowski and Prekopa–Leindler inequalities) are characterized in terms of the optimal transport map between suitable marginal probability measures. These results provide several qualitative applications both in the flat and non-flat frameworks. In particular, by using Caffarelli's regularity result for the Monge–Ampere equation, we give a new proof of Dubuc's characterization of the equality in Borell–Brascamp–Lieb inequalities in the Euclidean setting. When the n-dimensional Riemannian manifold has Ricci curvature Ric(M) ≥ (n-1)k for some k ⋲ ℝ, it turns out that equality in the Borell–Brascamp–Lieb inequality is expected only when a particular region of the manifold between the marginal supports has constant sectional curvature k. A precise characterization is provided for the equality in the Lott–Sturm–Villani-type distorted Brunn–Minkowski inequality on Riemannian manifolds. Related results for (not necessarily reversible) Finsler manifolds are also presented. We study some Riemannian metrics on the space of regular smooth curves in the plane, viewed as the orbit space of maps from the circle to the plane modulo the group of diffeomorphisms of the circle, acting as reparameterizations. In particular we investigate the L^2 inner product with respect to 1 plus curvature squared times arclength as the measure along a curve, applied to normal vector field to the curve. The curvature squared term acts as a sort of geometric Tikhonov regularization because, without it, the geodesic distance between any 2 distinct curves is 0, while in our case the distance is always positive. We give some lower bounds for the distance function, derive the geodesic equation and the sectional curvature, solve the geodesic equation with simple endpoints numerically, and pose some open questions. The space has an interesting split personality: among large smooth curves, all its sectional curvatures are positive or 0, while for curves with high curvature or perturbations of high frequency, the curvatures are negative.