流形优化：初步的理论分析
Contents
流形优化：初步的理论分析
在上一篇文章流形优化：从一个简单的例子开始中，从实例出发介绍了流形优化的过程，并将其与传统的拉格朗日乘数法做了对比。本文将对流形优化中的概念进行介绍。
欧式空间
常用符号\varepsilon来表示实数线性空间，常见的线性空间有\mathbb{R}^n（长度为n的向量）,\mathbb{R}^{n\times p}（大小为n\times p的矩阵），Sym(n)（大小为n的实对称方阵）。
对于一个函数F:\varepsilon \rightarrow \varepsilon’，若它是无限可微的，则称该函数是光滑的。函数F的微分DF(x)：\varepsilon \rightarrow \varepsilon’定义为：
DF(x)[v]=\lim_{t\rightarrow0}\frac{F(x+tv)-F(x)}{t}=\frac{d}{dt}F(x+tv)|_{t=0}
其中，v代表微分方向。
尽管我们只提到了实数线性空间，但我们仍可以通过适当的变换来处理复数，比如对于\mathbb{C}^n，可以将其变换为\mathbb{R}^{2n}（长度为2n的向量）,或者是\mathbb{R}^{2\times n}（大小为2 \times n的矩阵）。
欧式空间中的嵌入子流形
仍以球流形S^{n-1}为例，该流形中的元素x\in \mathbb R^n满足如下等式：
h(x)=x^Tx-1=0
在x的邻域内将上式泰勒展开，得到：
h(x+tv)=h(x)+tDh(x)[v]+O(t^2)
这意味着当t很小时，我们可以使用上式将S^{n-1}线性表达。我们称这样的集合为光滑集合，可以发现线性空间\varepsilon以及它的开子集都是光滑集合。值得注意的是，上式中v不是任取的，v应包含在核Dh(x)中（即h(x)=0且Dh(x)[v]=0）。求解Dh(x)[v]有：
Dh(x)[v]=\lim_{t\rightarrow0}\frac{h(x+tv)-h(x)}{t}=x^Tv+v^Tx=2x^Tv=0
可见Dh(x)的核是正交于x的子空间。
但不是所有可以写成h(x)的流形都可以被线性表达的。比如下列流形：
\mathbb X ={x\in \mathbb R^2: h(x)=x_1^2-x_2^2=0}
它的函数图像如下：
在非零处，该函数的核Dh(x)均无问题，但在原点出，核Dh(x)为整个\mathbb R^2。这是因为在原点处，Dh(x)的秩从1掉到了0。我们希望避免这种情况，为此我们定义了嵌入子流形。
定义1：令M为线性空间\varepsilon的子空间，我们称M为嵌入子流形，若它满足如下任一条件：
- M是\varepsilon的开子集，则称M为开子流形，若M=\varepsilon，则称其为线性流形
对于一个给定的整数k>0，对于每个x\in M存在一个邻域U和一个函数h:U\rightarrow \mathbb R^k满足如下条件：
- 对于y\in U，仅当y \in M时，h(y)=0
rank \space Dh(x)=k
如下图所示，在邻域U中，于流形M的交集（即红线部分）经过h的映射后为零，其他部分均不为零。
嵌入子流形的切空间
类似于笛卡尔坐标系中的切向量，我们将切空间定义为经过流形上某一点的所有光滑曲线在该点的速度的集合。用数学语言表述成如下形式：
定义2：令M为为\varepsilon的子集，对于所有的x\in M，定义切空间为：T_xM={c'(0)|c:I \rightarrow M在附近光滑且c(0)=x}
于是，我们将T_xM中的向量称为切M在x处的切向量。切空间T_xM的维度成为流形M的维度。
嵌入子流形间的光滑映射
上文已经介绍了光滑集合，我们可以进一步引入光滑集合之间的光滑映射。流形间的光滑映射的定义依赖于线性空间间的光滑映射。
定义3：令M和M’分别为\varepsilon和\varepsilon’的嵌入子流形，令映射F:M \rightarrow M’为M与M’间的映射。现定义函数\bar F=U \rightarrow \varepsilon’，其中U为x在\varepsilon中的邻域，且对于所有的y\in M \cap U，有F(y)=\bar F(y)。若存在这样的函数\bar F在x处光滑，则映射F在x处光滑。若映射F对于所有的x\in M均光滑，则称映射F光滑。
推论1：由上述定义可知，对于所有的x\in M，F(x)=\bar F(x)，或者可以写成这样的形式F=\bar F|_M。
光滑映射的微分
现定义一个两个线性空间间的光滑函数\bar F: U\in \varepsilon \rightarrow \varepsilon’，给定一点x \in U，\bar F在该点的微分为：
D\bar F(x)[v]=\lim_{t\rightarrow0}\frac{\bar F(x+tv)-\bar F(x)}{t}
这个式子表示了自变量x沿着方向v移动后\bar F的变化率，但这个定义不能直接套用在嵌入子流形间的映射F:M \rightarrow M’，因为x+tv通常来说不属于M，即F在x+tv处往往没有定义。
既然沿着x+tv这个方向行不通，我们可以换一个方向，通过使用c(t)，c(t)是定义在M上的曲线，且与x+tv有相同的性质，由定义2可知，c(0)=x，且c'(0)=v。由此求出的微分结果自然是在切空间上的。在此给出光滑映射的微分：
定义4：映射F:M \rightarrow M’在x处的微分为DF(x):T_xM \rightarrow T_{F(x)}M’，定义为：
DF(x)[v]=\frac{d}{dt}F(c(t))|_{t=0}
值得注意的地方有两点：1.该微分的定义不依赖于曲线c的选择，因为定义中只用到了曲线c的两个性质，而切空间中的所有曲线的这两个性质都相同。2.DF(x)是线性的。
之前提到过F=\bar F|_M，由于c \subset M，则F \circ c = \bar F \circ c ，由此可得：
DF(x)[v]=\frac{d}{dt}F(c(t))|_{t=0}=\frac{d}{dt}\bar F(c(t))|_{t=0}=D\bar F(x)[v]\tag{1}
可以用简化的式子F=\bar F|_{T_XM}表示上述关系。
当然，该微分的定义与光滑延申函数\bar F的选择无关，因为对于所有的延申函数，在流形M都是相等的，比如我们取两个不同的延申函数\bar F与\tilde F，我们可以得到如下等式关系：
D\bar F(x)[v]=(\bar F \circ c)'(0)=(\tilde F \circ c)'(0)=D\tilde F(x)[v]
例子1：仍考虑上一篇文章中的瑞利商问题，该问题的函数可以写成如下形式：
f :S^{n-1} \rightarrow \mathbb R: x \rightarrow x^TAx
该函数的自变量在球流形上，我们可以写出自变量在\mathbb R^n上的光滑延申函数\bar f:\mathbb R^n \rightarrow \mathbb R : x \rightarrow x^TAx，对于线性空间上的光滑延申函数，我们可以使用线性空间中的多元函数微分的定义求解：
D\bar f(x)[v]=\lim_{t\rightarrow0}\frac{\bar f(x+tv)-\bar f(x)}{t}=2x^TAv
由（1）式，我们可以得到瑞利商问题的微分：
D f(x)[v]=D\bar f(x)[v]=2x^TAv\\其中v\in T_xS^{n-1}={v \in \mathbb R^n:x^Tv=0}
嵌入流形中的微分与线性空间中的微分性质类似，这里不加证明的给出三个性质：
推论2：映射F : x \rightarrow a_1F_1(x)+a_2F_2(x)的微分为
DF(x)[v]=a_1DF_1(x)[v]+a_2DF_2(x)[v]
推论3：映射FG:x \rightarrow F(x)G(x)的微分为
D(FG)(x)[v]=G(x)DF(x)[v]+F(x)DG(x)[v]
推论4：映射G \circ F:x \rightarrow G(F(x))的微分为
D(G \circ F)(x)[v]=DG(F(x))[DF(x)[v]]
拉回（retractions）
所谓的拉回就是让流形上一点x沿着方向v \in T_xM移动后仍落在M上。如下图所示：
我们用R_x(v):T_xM \rightarrow M来表示拉回函数，拉回函数形式不唯一，但需要满足两个条件，现给出拉回函数的定义：
定义5：拉回是一个光滑映射，对于每个x\in M，令R_x(v):T_xM \rightarrow M，并满足如下条件：
- R_x(0)=x
DR_x(0):T_xM \rightarrow T_xM是一个恒等映射，即DR_x(0)[v]=v
同样的，用拉回函数定义的曲线c(t)=R_x(tv)满足c(0)=x且c'(0)=v
例子2：仍以球流形S^{n-1}为例，v\in T_xM。为了让x沿着v移动后仍落在球上，一种方法是将移动后的点对着球心方向投影到球上。
R_x(v)\triangleq \frac{x+v}{||x+v||}=\frac{x+v}{\sqrt{||x||^2+||v||^2}}=\frac{x+v}{\sqrt{1+||v||^2}}
将其写成流形上的曲线c
c(t)=R_x(tv)=\frac{x+tv}{\sqrt{1+t^2||v||^2}}
验证可得，c(0)=x，且c'(0)=v
还有一种合理的拉回方式，可以沿着大圆的方向拉回：
R_x(v)=\cos(||v||)x+sin(||v||)\frac{v}{||v||}
黎曼流形和子流形
为切空间选择合适的内积对接下来要讲的梯度至关重要。这里用<\cdot,\cdot >_x:T_xM \times T_xM \rightarrow \mathbb R表示内积。对于内积的选择，我们称之为度量（metric）。
若度量是对于x光滑的，则称之为黎曼度量，使用黎曼度量的流形称为黎曼流形。使用黎曼度量的欧式空间内的嵌入子流形称为黎曼子流形。
黎曼梯度
定义6：令f:M \rightarrow \mathbb R为黎曼流形M上的光滑函数。f的黎曼梯度定义为：
\forall (x,v) \in TM,\space \space \space \space \space Df(x)[v]=
上式中gradf(x)对于每个x而言是唯一确定的，是不随v的选择而变化的。
计算黎曼梯度最直接的方法就是通过定义计算，可以现计算Df(x)[v]，然后将其变换为
推论5：令f:M \rightarrow \mathbb R为黎曼流形M上的光滑函数，R为该流形的拉回函数，对于所有的x\in M：
{\rm grad}f(x)={\rm grad}(f \circ R_x)(0)
上式中的f\circ R_x:T_xM \rightarrow \mathbb R是一个线性空间到实数的映射，因此它的梯度是一个典型的线性空间内的梯度。
证明：由推论4可知
D(f \circ R_x)(0)[v]=Df(R_x(0))[DR_x(0)[v]]
根据拉回函数的性质，上式可进一步化简：
D(f \circ R_x)(0)[v] = Df(x)[v]
根据定义6
D(f \circ R_x)(0)[v] = <{\rm grad}(f \circ R_x)(0),v>_x= Df(x)[v]=<{\rm grad }f(x),v>_x
由此，原始得证。
对于黎曼子流形，我们还可以通过光滑延申函数计算梯度。
Df(x)[v]=
由于gradf(x)是在\varepsilon上的向量，而T_xM是在\varepsilon上的子空间，gradf(x)可能不在T_xM内，于是尝试将gradf(x)分解成平行于切空间和垂直于切空间得两部分。
{\rm grad}\bar f(x)={\rm grad}\bar f(x)_{\parallel} + {\rm grad}\bar f(x)_{\perp}
垂直于切空间的那部分与切空间内的切向量v的内积必然为0，于是（2）式可以改写为：
所以，如果我们想求黎曼梯度，只需求光滑延申函数平行于切空间的梯度分量即可，即：
{\rm grad}f(x) = {\rm grad}\bar f(x)_{\parallel}\tag{3}
换句话说，我们可以先用经典的方法求出\bar f(x)的梯度，然后再将该梯度投影到切空间上即可。于是我们定义投影函数：
定义7：令M为线性空间\varepsilon的嵌入子流形，使用度量<\cdot,\cdot>
{\rm Proj}_x:\varepsilon \rightarrow T_xM
这里的{\rm Proj}_x满足以下关系：\forall v \in M,u \in \varepsilon\space \space \space <{u - \rm Proj}_x(u),v>=0
于是，（3）式可以写成如下形式：
{\rm grad}f(x) = {\rm Proj}_x({\rm grad}\bar f(x))\tag{4}
例子3：这里我们仍以瑞利商为例，引入函数f(x)=x^TAx，其中A=A^T，使用欧式度量
D\bar f(x)[v]=2x^TAv=<2Ax,v>
通过定义6可以得到梯度：
{\rm grad}\bar f(x)=2Ax
接下来，我们会试图将该梯度投影到切空间上。球流形S^{n-1}的切空间，之前已经求出
T_xS^{n-1}={v\in \mathbb R^n:x^Tv=0}={v\in \mathbb R^n:
如下图所示，可以得到线性空间中的向量u与切空间中的向量{\rm Proj}_x(u)的关系：
a = u – {\rm Proj}_x(u)
其中向量a即为u的垂直分量，因此它与球流形上的x向量平行，而向量u在x上的投影即为||a||
||a|| = \frac{
由此便可以得到向量u在切空间上的投影
{\rm Proj}_x(u) = u – (x^Tu)x=(I_n-xx^T)u
由（4）式求得函数f(x)的梯度：
{\rm grad}f(x) = {\rm Proj}_x({\rm grad}\bar f(x))=2(Ax-(x^TAx)x)