Source-linked AI summary
Conic geometric optimisation on the manifold of positive definite matrices
Suvrit Sra, Reshad Hosseini
TL;DR
The paper addresses how to globally optimise structured objectives on HPD matrices when Euclidean nonconvexity and local minima complicate estimation. It develops g-convexity recognition tools and cone-theoretic fixed-point methods, then applies them to ECD maximum likelihood and reports that a scaled fixed-point method outperforms the compared methods, while broader experimental validation remains needed.
Problem
Maximum-likelihood estimation for elliptically contoured distributions can be nonconvex with multiple local minima, making globally optimal estimation difficult.
Method
The paper develops g-convexity recognition and construction tools, manifold optimisation methods, and cone-theoretic fixed-point algorithms for HPD matrices.
Results
The scaled fixed-point method FP2 outperforms the other tested methods across increasing dimensionality and varying β.
Takeaways & Limitations
The framework provides globally optimisable formulations for a rich class of ECDs and extends geometric optimisation beyond previously known examples.
Takeaways & Limitations
The authors state that a more thorough experimental study of their algorithms remains to be undertaken.
Abstract
from arXiv · showhide
We develop \emph{geometric optimisation} on the manifold of Hermitian positive definite (HPD) matrices. In particular, we consider optimising two types of cost functions: (i) geodesically convex (g-convex); and (ii) log-nonexpansive (LN). G-convex functions are nonconvex in the usual euclidean sense, but convex along the manifold and thus allow global optimisation. LN functions may fail to be even g-convex, but still remain globally optimisable due to their special structure. We develop theoretical tools to recognise and generate g-convex functions as well as cone theoretic fixed-point optimisation algorithms. We illustrate our techniques by applying them to maximum-likelihood parameter estimation for elliptically contoured distributions (a rich class that substantially generalises the multivariate normal distribution). We compare our fixed-point algorithms with sophisticated manifold optimisation methods and obtain notable speedups.
1 Introduction
The paper develops conic geometric optimisation for HPD matrices, exploiting their manifold and cone geometry to address structured nonconvex problems. It introduces recognition tools, optimisation methods, and an elliptically contoured distribution application.
- Geometric setting: HPD matrices form a convex cone whose interior is a Riemannian manifold and a CAT(0) space, supporting geometric optimisation.This geometry can make Euclidean-nonconvex problems convex along the manifold or otherwise efficiently optimisable.
- Contributions: The paper formally develops conic geometric optimisation for HPD matrices and provides results for recognising g-convexity and handling some non-g-convex functions.
- Motivation: The framework is motivated by conic optimisation problems arising in covariance shrinkage, nonlinear matrix equations, and nonlinear Perron–Frobenius theory.
- Application: The authors apply their ideas to maximum-likelihood estimation for elliptically contoured distributions, using ECDs as an instructive and important application.
- Scope: The paper studies g-convexity, log-nonexpansive functions, manifold optimisation, fixed-point algorithms, and ECD inference before presenting numerical results.
2 Geodesic convexity for HPD matrices
The paper develops theory for recognising and constructing g-convex functions on HPD matrices, where noncommutativity prevents a direct scalar characterisation. The resulting theorems generate broad families of g-convex and log-g-convex objectives, including matrix means and related problems.
- Recognising g-convexity: Unlike the scalar case, HPD-matrix g-convexity lacks a comparable characterisation because matrix multiplication is noncommutative.The paper therefore develops theory for recognising and constructing g-convex functions.
- Recognition tools: Theorem 8 states that applying a strictly positive linear map to the matrix geometric mean yields a key mechanism for recognising and constructing g-convex functions.
- Log-g-convexity: Corollary 9 establishes log-g-convexity for a trace-based construction, so its logarithm is g-convex and products or sums preserve log-g-convexity.
- Further constructions: Additional results cover spectral constructions, log-trace-exponential functions, determinant objectives, multivariable maps, and joint g-convexity.
- Recognition tools: Theorem 15 extends this mechanism: h(Φ(S^r)) is g-convex when h is nondecreasing and g-convex, Φ is positive linear, and r is ±1.
- Applications: The framework yields g-convex objectives for HPD geometric means and medians, with strict g-convexity giving uniqueness for the mean objective.
3 Manifold optimisation for g-convex functions
The paper formulates optimisation algorithms using the Riemannian structure of HPD matrices, including intrinsic gradients, retractions, vector transport, and limited-memory Riemannian BFGS. The intrinsic metric is reported to substantially improve convergence speed over the induced Euclidean metric.
- Manifold machinery: Optimisation on HPD matrices uses manifold concepts including tangent vectors, derivatives, inner products, gradients, retractions, vector transport, and Hessians.
- Manifold machinery: The tangent space consists of Hermitian matrices, and manifold derivatives can be obtained from embedded Euclidean derivatives along tangent directions.
- Metric choice: The intrinsic inner product yields more than a hundred times faster convergence than the induced Euclidean inner product in the authors’ experiments.
- Retractions: The intrinsic metric produces geodesic exponential-map retractions for steepest descent on the HPD manifold.
- Quasi-Newton optimisation: Limited-memory Riemannian BFGS is described for HPD matrices, with parallel transport and its inverse identified as possible computational bottlenecks.
4 Geometric optimisation for log-nonexpansive functions
The paper develops cone-based fixed-point optimisation for log-nonexpansive objectives on HPD matrices, using the Thompson metric to establish convergence and uniqueness under suitable conditions. It also introduces scaling to address slow empirical convergence.
- Fixed-point optimisation: Fixed-point methods can replace more computationally demanding Newton approaches for solving the nonlinear stationarity equation.The paper notes that Newton iterations may require the inverse Hessian, whereas fixed-point iterations offer a simpler alternative.
- Thompson metric: The Thompson part metric is the appropriate convergence framework because HPD matrices are treated as a convex cone rather than only as a Riemannian manifold.This conic viewpoint is grounded in nonlinear Perron–Frobenius theory.
- Convergence and uniqueness: When G is log-contractive and a fixed point exists, it is unique and Picard iteration converges to it; for log-nonexpansive maps, solutions are unique up to positive scaling under spanning-data conditions.The LN result uses the compression property of the Thompson metric.
- Contractive maps: Log-nonexpansive maps preserve Thompson distances, while log-contractive maps strictly contract them; sums of the two map types remain log-contractive.These properties support fixed-point convergence results in the HPD cone.
- Computational efficiency: Scaling each update by a searched factor α_k can substantially accelerate convergence by resolving cases where the unscaled contraction factor becomes small.The problematic cases occur when both extreme eigenvalues of M(S_k) lie on the same side of one.
5 Application to Elliptically Contoured Distributions
The paper applies conic geometric optimisation to maximum-likelihood estimation for elliptically contoured distributions, whose likelihood objective can be difficult and nonconvex in Euclidean coordinates. It classifies density-generating functions by optimisation structure and derives global-convergence and existence results for manifold and fixed-point methods.
- Maximum likelihood parameter estimation: Elliptically contoured distributions generalise the multivariate normal and include Kotz-type, multivariate-t, logistic, and other density-generating functions.The scatter matrix is proportional to the covariance matrix when covariance is finite.
- Maximum likelihood parameter estimation: The negative log-likelihood may be nonconvex with multiple local minima, motivating methods that can locate globally optimal estimates.The difficulty arises in part because log det(S) is concave while it is minimised.
- Classes of density-generating functions: The study separates ECD likelihoods into g-convex, log-nonexpansive, and log-convex classes with different optimisation guarantees.The LN class is introduced to exploit the non-positive curvature of the HPD manifold, including cases not covered by previous methods.
- Class g-convex: Strict g-convexity rules out multiple solutions and makes every local solution globally optimal, while the existence theorem supplies conditions under which a minimum is attained.The existence result assumes lower semicontinuity of −log ϕ and coercivity as S or S^-1 becomes unbounded.
- Class LN: For LN objectives, log-contractive fixed-point maps have unique solutions and convergent iterations; Kotz-type distributions satisfy such guarantees under stated parameter and data conditions.Theorem 47 gives convergence for 0 < β < 2 and α ≤ d/2, while the combined results cover α ≤ d/2 whenever the MLE exists.
- Class LC: For LC objectives, the proposed iteration decreases the cost and converges to a positive definite solution under boundary-growth, concavity, and nonnegativity assumptions.The iteration remains in the positive semidefinite cone, and the boundary condition ensures convergence to the positive definite interior.
6 Numerical results
The numerical study evaluates fixed-point iterations on Kotz-type likelihoods against four manifold optimisation methods across matrix dimensions and distribution parameters. Scaling the fixed-point update substantially improves performance, while the authors caution that the experiments are limited.
- Computational mechanism: Fixed-point updates preserve the positive-definiteness constraint by construction, avoiding extra eigenvalue computations required by general constrained solvers.This constraint handling is presented as a source of computational savings.
- Experimental setup: The experiments use 10,000 Kotz-distribution samples with specified α and β values and random covariance matrices.They vary input-matrix dimensionality and β, which influences fixed-point convergence rate.
- Experimental setup: The comparison includes steepest descent, conjugate gradients, trust-region, and limited-memory RBFGS manifold optimisation methods.All methods are implemented in Matlab, with HPD-manifold support added to Manopt for the manifold methods.
- Running-time comparison: Basic fixed-point iteration does not outperform steepest descent and can closely follow it relative to the other manifold methods.The comparison covers the running-time experiments described for increasing dimension and varying β.
- Running-time comparison: The scaled fixed-point method FP2 outperforms all other methods as dimensionality increases and β varies.The scale is selected to enforce trace(M(S_k+1)) = d.
- Limitations: The results are preliminary: a more thorough experimental assessment of the algorithms remains to be undertaken.The authors describe the experiments as indicating competitiveness rather than establishing a comprehensive evaluation.
7 Conclusion
The paper develops geometric optimisation methods for certain nonconvex objectives on positive definite matrices, including geodesic-convexity recognition and log-nonexpansive optimisation via fixed-point iterations. It applies these techniques to maximum-likelihood estimation for elliptically contoured distributions and reports coverage beyond the state of the art, while broader numerical tooling remains ongoing.
- The paper studies minimisation of certain nonconvex functions over positive definite matrices.
- It develops results for recognising geodesic convexity and introduces log-nonexpansive functions that need not be geodesically convex but can still be optimised efficiently.
- Fixed-point iterations in a suitable metric space on positive definite matrices form the key algorithmic construction.
- The methods are developed and applied to maximum-likelihood estimation for elliptically contoured distributions, covering instances substantially beyond the state of the art.
- Developing a more extensive geometric optimisation numerical package remains an ongoing project.