如何對SPD流形上的測地距離進行凸近似？

全體對稱正定矩陣的集合稱為SPD流形，這一流形上有一個well-defined的測地距離，其定義如下：假設對稱正定矩陣和是SPD流形上的兩個點，在一個合適的黎曼度量下，其測地距離為,這裡log是矩陣對數，F是矩陣的Forbenius範數。一個典型的優化問題是，在一定約束條件下，用一個SPD矩陣去逼近另一個給定的SPD矩陣，也就是使得該測地距離最小。查了一些文獻，發現這一距離應當不是凸的，這對於很多優化問題非常不好處理。那麼是否存在對這一距離的凸近似？或者某種性質比較好的上界？

對於SPD流形 給一個凸優化的思路。為了避免複雜的數學符號，這裡採用類比思路進行描述。

首先抽象地思考歐式空間的凸集的定義如何推廣到黎曼流形上去。凸集定義（代數描述）：集合C是一個凸集，如果 屬於C，那麼對任意 也屬於C。幾何描述是，如果兩個端點屬於C，那麼連接這兩個端點的「直線段」也屬於C。從代數上看，對於一個抽象黎曼流形，想要定義抽象凸性，就需要定義或者說推廣加法和標量乘法；從幾何上看，就需要把歐氏空間的「直線段」的含義推廣到黎曼流形上去。符合凸優化需要的一個框架是：Hadamard 流形上的凸集，對應的「直線段」是測地線 [1]。

再考慮一個具體的例子，幾何規劃geometric progamming（GP）。眾所周知，GP的本身形式並不是凸的，但是經過log-exp變換之後，可以得到一個指數錐上的線性凸規劃的凸形式。代數角度來看，log-exp變換把加法 換成乘法 ，把算術加權 替換成幾何加權 ；從幾何角度來思考，log-exp變換等價地規定了GP的定義流形 上的測地線，log-exp變換就是把測地線變換成了歐式空間的直線段，而歐式空間的測地距離對應的是 上的Thompson距離。

有意思的是，也可以類比 定義 上的GP。對於任意兩個維度一致的SPD矩陣 , 總存在一個非奇異矩陣可以將他們同時對角化，那麼就可以應用 上的log-exp變換及其對應的測地距離了。當然，我們其實不需要這麼繞彎子，可以在 上直接定義 和 【不是通常意義上不可交換的矩陣乘法含義】。對應的Thompson距離是 ,這裡對數是矩陣對數，範數是通常的運算元範數，此時Thompson距離是測地線凸的。

這方面的研究通常叫做錐幾何規劃 [2][3]。通常的線性凸錐規劃 里非線性部分被包含在已經結構的凸錐 里，其他部分是線性映射，而在更為一般的凸錐規劃 ，考慮是非線性映射 的 。在錐幾何規劃里非線性映射 就是矩陣指數映射 ，很顯然，通常的GP就是這裡的特例 ，而[3]的GP是特例 。這裡涉及到的其實是非線性凸優化的表示問題【因為求解演算法的效率是與問題表示形式有關的】，到底是應該把非線性部分放到錐里(一個複雜的凸集總可以看作是一個超平面與一個非線性凸錐的交集，但這裡凸錐的維度可能很高)，還是用非線性映射直接顯式表示（比如，非線性映射的像在簡單的凸錐 里）。錐幾何規劃在信號處理和機器學習應用見[4]-[7], 一篇有意思的研究隨機SPD矩陣的高斯分布的論文見[8]。

[1] Borisenko A A. Convex sets in Hadamard manifolds[J]. Differential Geometry Its Applications, 2002, 17(2–3):111-121.

[2] Chandrasekaran V, Shah P. Conic geometric programming[C]// Information Sciences and Systems. IEEE, 2013:1-4.

[3] Sra S, Hosseini R. Conic geometric optimisation on the manifold of positive definite matrices[J]. Siam Journal on Optimization, 2014, 25(1).

[4] Wiesel. Geodesic Convexity and Covariance Estimation[J]. IEEE Transactions on Signal Processing, 2012, 60(12):6182-6189.

[5] Zhang H, Sra S. First-order methods for geodesically convex optimization[C]//Conference on Learning Theory. 2016: 1617-1638.

[6] Zhang T, Wiesel A, Greco M S. Multivariate Generalized Gaussian Distribution: Convexity and Graphical Models[J]. IEEE Transactions on Signal Processing, 2013, 61(16):4141-4148.

[7] Arnaudon M, Barbaresco F, Yang L. Riemannian Medians and Means With Applications to Radar Signal Processing[J]. IEEE Journal of Selected Topics in Signal Processing, 2013, 7(4):595-604.

[8] Said S, Bombrun L, Berthoumieu Y, et al. Riemannian Gaussian Distributions on the Space of Symmetric Positive Definite Matrices[J]. IEEE Transactions on Information Theory, 2015, PP(99):1-1.

看題目的意思似乎是固定 ，找一個滿足約束的 讓距離最小。那麼最簡單的應該是用 去近似吧，這個距離關於 是convex的。另外一個簡單的近似可以這樣。先考慮標量的情況, 這個函數關於x是nonconvex的。一種簡單的近似是先用不等式

然後一個 的convex upper/lower bound就是

到底是upper bound還是lower bound需要討論下x的範圍。

矩陣的情況也不難。我們先來算一下 的梯度:

因為 很小，所以 的特徵值 都很小, 利用，我們有

根據這個等式再結合 的concavity我們有下面的不等式

把不等式右邊帶入你的測地距離就能得到一個關於A的convex bound。