Python视频微信订餐小程序课程视频
https://edu.csdn.net/course/detail/36074
Python实战量化交易理财系统
https://edu.csdn.net/course/detail/35475
Paper Information
Title:Cauchy Graph EmbeddingAuthors:Dijun Luo, C. Ding, F. Nie, Heng HuangSources:2011, ICMLOthers:71 Citations, 30 References
Abstract
嵌入拉普拉斯(Laplacian embedding)为节点提供了一种低维表示,其中边权值表示节点对象之间的成对相似性。通常假设拉普拉斯的嵌入结果保留了低维投影子空间上原始数据的局部拓扑结构,即任何图形节点都应紧密嵌入嵌入空间。然而,在本文中,我们将证明 Laplacian embedding 局部拓扑像预期的那样保持局部拓扑。为了提高嵌入图中的局部拓扑保持性,我们提出了一种新的 Cauchy Graph Embedding 该方法通过新的目标保持原始数据嵌入空间的相似性。
1 Introduction
从数据嵌入的角度来看,我们可以将无监督嵌入法分为两类。第一种方法是通过线性变换将数据嵌入线性空间,如主成分分析(PCA)(Jolliffe,2002年及多维度分析(MDS)(Cox&Cox,2001)。主成分分析和 MDS 它们都是特征向量法,可以在高维数据中线性变量。它们在许多机器学习应用泛应用于许多机器学习应用中。
但真实数据的底层结构往往是高度非线性的,因此不能用线性流形准确地近似。第二种方法以非线性方式以不同的目的嵌入数据。最近提出了几种有前途的非线性方法,包括 IsoMAP (Tenenbaum et al., 2000), Local Linear Embedding (LLE) (Roweis & Saul, 2000), Local Tangent Space Alignment (Zhang & Zha, 2004), Laplacian Embedding/Eigenmap (Hall, 1971; Belkin & Niyogi, 2003; Luo et al., 2009), and Local Spline Embedding (Xiang et al., 2009) etc。通常,他们建立了一个由邻域图导出的二次目标,并求解它的主要特征向量:Isomap 取与最大特征值相关的特征向量;LLE 和 嵌入拉普拉斯 使用与最小特征值相关的特征向量。通常,他们建立了一个由邻域图导出的二次目标,并解决了其主要特征向量:Isomap 取与最大特征值相关的特征向量;LLE 和 嵌入拉普拉斯 使用与最小特征值相关的特征向量。Isomap 试图保持输入数据沿低维流形测量的整体成对距离;LLE和嵌入拉普拉斯试图保持数据的局部几何关系。
2 Laplacian Embedding
首先介绍 Laplacian embedding 。输入数据是 nnn 数据对象之间的矩阵成对相似 WWW。把 WWW 看作是一个有 nnn 节点图上边缘的权值。其任务是将图中的节点嵌入坐标中 (x1,?,xn)(x1,?,xn)\left(x_{1}, \cdots, x_{n}\right) 一维空间。如果,目标是 iii,jjj 相似(即 wijwijw_{ij} 它们应该在嵌入空间中相邻,即 (xi?xj)2(xi?xj)2{(x_i?x_j)}^2 应该很小。这可以通过最小化来实现。
minxJ(x)=∑ij(xi?xj)2wij(1)minxJ(x)=∑ij(xi?xj)2wij(1)\underset{\mathbf{x}}{\text{min}}J(\mathbf{x})=\sum\limits_{i j}\left(x_{i}-x_{j}\right)^{2} w_{i j}\quad\quad\quad(1)
如果最小化 ∑ij(xi?xj)2wij∑ij(xi?xj)2wij \sum\limits_{i j}\left(x_{i}-x_{j}\right)^{2} w_{i j} 没有限制,可以使向量 xx\mathbf{x} 全为 000 向量,这显然不好, 所以加入限制 ∑ix2i=1∑ixi2=1\sum\limits_{i} x_{i}^{2}=1 。另一个问题是,原目标函数具有平移不变性 xixix_{i} 替换为 xi axi ax_{i} a 这显然是不可能的,所以添加限制 ∑xi=0∑xi=0\sum\limits x_{i}=0,即 xxx 围绕在 000 附近。另一个问题是,原目标函数具有平移不变性 xixix_{i} 替换为 xi axi ax_{i} a 这显然是不可能的,所以添加限制 ∑xi=0∑xi=0\sum\limits x_{i}=0,即 xxx 围绕在 000 附近。此时,原目标函数变为:
minx∑ij(xi?xj)2wij,s.t.∑ix2i=1,∑ixi=0minx∑ij(xi?xj)2wij,s.t.∑ixi2=1,∑ixi=0\begin{array}{c} \min _{\mathbf{x}} \sum\limits_{i j}\left(x_{i}-x_{j}\right)^{2} w_{i j},\\ \text { s.t. } \sum\limits_{i} x_{i}^{2}=1, \sum\limits_{i} x_{i}=0\end{array}
由于嵌入式问题的解决方案很容易得到,因为
J(x)=2∑ijxi(D?W)ijxj=2xT(D?W)xJ(x)=2∑ijxi(D?W)ijxj=2xT(D?W)xJ(\mathbf{x})=2 \sum\limits_{i j} x_{i}(D-W)_{i j} x_{j}=2 \mathbf{x}^{T}(D-W) \mathbf{x}
其中 D=diag(d1,?,dn)D=diag(d1,?,dn)D=\operatorname{diag}\left(d_{1}, \cdots, d_{n}\right),di=∑jWijdi=∑jWijd_{i}=\sum\limits_{j} W_{i j}。矩阵 (D?W)(D?W)(D-W) 被称为图拉普拉斯算子,最小化嵌入目标的嵌入解
(D?W)x=λx(4)(D?W)x=λx(4)(D-W) \mathbf{x}=\lambda \mathbf{x} \quad \quad \quad (4)
拉普拉斯被广泛应用于机器学习,以保持局部拓扑图节点的正则化
3 The Local Topology Preserving Property of Graph Embedding
本文研究了地图嵌入式局部拓扑的保持性质。首先,局部拓扑保留的定义证明,与被广泛接受的概念相反,局部拓扑可能无法在嵌入空间中保留原始数据。
3.1 Local Topology Preserving
首先,定义了局部拓扑保留。给定边权值为 W=(wij)W=(wij)W=\left(w_{i j}\right) 对称(无向)图,对图 nnn 具有相应嵌入的节点 (x1,?,xn)(x1,?,xn)\left(\mathbf{x}_{1}, \cdots, \mathbf{x}_{n}\right)。如果建立了以下条件,我们假设嵌入保持了局部拓扑
ifwij≥wpq, then(xi?xj)2≤(xp?xq)2,?i,j,p,q.(5)ifwij≥wpq, then(xi?xj)2≤(xp?xq)2,?i,j,p,q.(5)\text { if } w_{i j} \geq w_{p q} \text {, then }\left(x_{i}-x_{j}\right)^{2} \leq\left(x_{p}-x_{q}\right)^{2}, \forall i, j, p, q \text {. }\quad\quad \quad (5)
粗略地说,这个定义说,对于任何一对节点 (i,j)(i,j)(i,j),它们越相似(边权重) wijwijw_{ij} 它们应该嵌入得越大,就越近( |xi?xj||xi?xj||x_i?x_j| 应该越小)。
拉普拉斯被广泛应用于机器学习中保留局部拓扑的概念。作为本文的贡献,我们指出,在许多情况下,局部拓扑保留的感知概念实际上是错误的。
我们的发现有两个方面。一是距离大(相似度小):
The quadratic function of the Laplacian embedding emphasizes the large distance pairs, which enforces node pair (i,j)(i,j)(i,j) with small wijwijw_{ij} to be separated far-away.
二是小距离(大相似性):
The quadratic function of the Laplacian embedding de-emphasizes the small distance pairs, leading to many violations of local topology preserving at smal distance pairs.
在下面,我们将展示一些示例来支持我们的发现。这一发现的一个结果是,k个最近邻(kNN)类型的分类方法将表现得很差,因为它们依赖于局部拓扑属性。在此基础上,我们提出了一种新的图嵌入方法,它强调小距离(大相似性)数据对,从而强制在嵌入空间中保持局部拓扑。
3.2. Experimental Evidences
在 “manifold” data 上,证明了本文提出的方法好于LE。
这里
wij=exp(−∥xi−xj∥2/d⃗ 2)wij=exp(−‖xi−xj‖2/d→2)w_{i j}=\exp \left(-\left|x_{i}-x_{j}\right|^{2} / \vec{d}^{2}\right)
d¯=(∑i≠j∥xi−xj∥)/(n(n−1))d¯=(∑i≠j‖xi−xj‖)/(n(n−1))\bar{d}=\left(\sum\limits _{i \neq j}\left|x_{i}-x_{j}\right|\right) /(n(n-1))
4. Cauchy Embedding
在本文中,我们提出了一种新的强调短距离的图嵌入方法,并确保在局部,两个节点越相似,它们在嵌入空间中就越近。
我们的方法如下。关键思想是,对于具有大 wijwij w_{i j} 的一对 (i,j)(i,j)(i,j),(xi−xj)2(xi−xj)2\left(x_{i}-x_{j}\right)^{2} 应该很小,从而使目标函数最小化。现在,如果 (xi−xj)2≡Γ1(|xi−xj|)(xi−xj)2≡Γ1(|xi−xj|)\left(x_{i}-x_{j}\right)^{2} \equiv \Gamma_{1}\left(\left|x_{i}-x_{j}\right|\right) 很小,比如:
(xi−xj)2(xi−xj)2+σ2≡Γ2(|xi−xj|)(xi−xj)2(xi−xj)2+σ2≡Γ2(|xi−xj|)\frac{\left(x_{i}-x_{j}\right){2}}{\left(x_{i}-x_{j}\right){2}+\sigma^{2}} \equiv \Gamma_{2}\left(\left|x_{i}-x_{j}\right|\right)
此外,函数 Γ1(⋅)Γ1(⋅)\Gamma_{1}(\cdot) 是单调的,函数 Γ2(⋅)Γ2(⋅)\Gamma_{2}(\cdot) 也是单调的。因此,我们最小化
minx s.t., ∑ij(xi−xj)2(xi−xj)2+σ2wij∥x∥2=1,eTx=0minx∑ij(xi−xj)2(xi−xj)2+σ2wij s.t., ‖x‖2=1,eTx=0\begin{array}{ll}\underset{\mathbf{x}}{\text{min}} \quad & \sum\limits _{i j} \frac{\left(x_{i}-x_{j}\right){2}}{\left(x_{i}-x_{j}\right){2}+\sigma^{2}} w_{i j} \\text { s.t., } & |\mathbf{x}|^{2}=1, \mathbf{e}^{T} \mathbf{x}=0 \end{array}
由于
(xi−xj)2(xi−xj)2+σ2=1−σ2(xi−xj)2+σ2(xi−xj)2(xi−xj)2+σ2=1−σ2(xi−xj)2+σ2\frac{\left(x_{i}-x_{j}\right){2}}{\left(x_{i}-x_{j}\right){2}+\sigma{2}}=1-\frac{\sigma{2}}{\left(x_{i}-x_{j}\right){2}+\sigma{2}}
因此可以简化为
maxx s.t. ∑ijwij(xi−xj)2+σ2,∑ix2i=1,∑ixi=0.maxx∑ijwij(xi−xj)2+σ2, s.t. ∑ixi2=1,∑ixi=0.\begin{aligned}\underset{\mathbf{x}}{\text{max}} & \sum_{i j} \frac{w_{i j}}{\left(x_{i}-x_{j}\right){2}+\sigma{2}}, \\text { s.t. } & \sum_{i} x_{i}^{2}=1, \sum_{i} x_{i}=0 .\end{aligned}
柯西嵌入的目标函数之间的最重要的区别 [ Eq. (6) Eq. (7) ] 与拉普拉斯嵌入的目标函数 [ Eq. (1) ]如下。对于拉普拉斯嵌入,大距离 (xi−xj)2(xi−xj)2\left(x_{i}-\right. \left.x_{j}\right)^{2} 项由于二次形式而贡献更大,而对于柯西嵌入,小距离 (xi−xj)2(xi−xj)2\left(x_{i}-\right. \left.x_{j}\right)^{2} 项贡献更大。这一关键的差异确保了柯西嵌入表现出更强的局部拓扑保持性。
4.1. Multi-dimensional Cauchy Embedding
为了表示的简单和清晰,我们首先考虑二维嵌入。对于二维嵌入,每个节点 iii 都嵌入在具有坐标 (xi,yi)(xi,yi)(x_i,y_i) 的二维空间中。通常的拉普拉斯式嵌入可以表示为
maxx,y s.t. ∑ij[(xi−xj)2+(yi−yj)2]wij(8)∥x∥2=1,eTx=0(9)∥y∥2=1,eTy=0(10)xTy=0(11)maxx,y∑ij[(xi−xj)2+(yi−yj)2]wij(8) s.t. ‖x‖2=1,eTx=0(9)‖y‖2=1,eTy=0(10)xTy=0(11)\begin{array}{ll}\underset{\mathbf{x,y}}{\text{max}} & \sum\limits _{i j}\left[\left(x_{i}-x_{j}\right){2}+\left(y_{i}-y_{j}\right){2}\right] w_{i j} \quad\quad\quad(8) \\text { s.t. } & |\mathbf{x}|^{2}=1, \mathbf{e}^{T} \mathbf{x}=0 \quad\quad\quad\quad\quad\quad\quad\quad(9)\& |\mathbf{y}|^{2}=1, \mathbf{e}^{T} \mathbf{y}=0 \quad\quad\quad\quad\quad\quad\quad\quad(10)\& \mathbf{x}^{T} \mathbf{y}=0 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(11)\end{array}
其中 e=(1,⋯,1)Te=(1,⋯,1)T\mathbf{e}=(1, \cdots, 1)^{T} . 约束 xTy=0xTy=0\mathbf{x}^{T} \mathbf{y}=0 很重要,因为没有它,优化得到的最优值为 x=yx=y\mathbf{x}=\mathbf{y}。
二维柯西矩阵的动机是通过以下优化得到的
minx,y∑ij(xi−xj)2+(yi−yj)2(xi−xj)2+(yi−yj)2+σ2wij(12)minx,y∑ij(xi−xj)2+(yi−yj)2(xi−xj)2+(yi−yj)2+σ2wij(12) \underset{\mathbf{x,y}}{\text{min}} \sum_{i j} \frac{\left(x_{i}-x_{j}\right){2}+\left(y_{i}-y_{j}\right){2}}{\left(x_{i}-x_{j}\right){2}+\left(y_{i}-y_{j}\right){2}+\sigma^{2}} w_{i j}\quad\quad\quad (12)
具有相同的约束方程式。(8-11).这将被简化为
minx,ywij(xi−xj)2+(yi−yj)2+σ2minx,ywij(xi−xj)2+(yi−yj)2+σ2\underset{\mathbf{x,y}}{\text{min}}\frac{w_{i j}}{\left(x_{i}-x_{j}\right){2}+\left(y_{i}-y_{j}\right){2}+\sigma^{2}}
一般来说,ppp 维柯西嵌入到 R=(r1,⋯,rn)∈Rp×nR=(r1,⋯,rn)∈ℜp×nR= \left(\mathbf{r}_{1}, \cdots, \mathbf{r}_{n}\right) \in \Re^{p \times n} 是通过优化获得
maxR s.t. J®=∑ijwij∥ri−rj∥2+σ2(14)RRT=I,Re=0(15)maxRJ®=∑ijwij‖ri−rj‖2+σ2(14) s.t. RRT=I,Re=0(15)\begin{array}{rl}\underset{\mathbf{R}}{\text{max}} & J®=\sum\limits _{i j} \frac{w_{i j}}{\left|\mathbf{r}_{i}-\mathbf{r}_{j}\right|{2}+\sigma{2}} \quad\quad(14)\\text { s.t. } & R R^{T}=I, R \mathbf{e}=\mathbf{0}\quad\quad(15)\end{array}
4.2. Exponential and Gaussian Embedding
In Cauchy embedding the short distance pairs are emphasized more than large distance pairs, in comparison to Laplacian embedding. We can further emphasize the short distance pairs and de-emphasize large distance pairs by the following Gaussian embedding:
maxx∑ijexp[−(xi−xj)2σ2]wij(16) s.t., ∥x∥2=1,eTx=0(17)maxx∑ijexp[−(xi−xj)2σ2]wij(16) s.t., ‖x‖2=1,eTx=0(17)\begin{array}{r}\underset{\mathbf{x}}{\text{max}} \sum\limits _{i j} \exp \left[-\frac{\left(x_{i}-x_{j}\right){2}}{\sigma{2}}\right] w_{i j}\quad\quad(16) \\text { s.t., }|\mathbf{x}|^{2}=1, \mathbf{e}^{T} \mathbf{x}=0\quad\quad(17) \end{array}
或者指数嵌入
maxx∑ijexp[−|xi−xj|σ]wij s.t., ∥x∥2=1,eTx=0maxx∑ijexp[−|xi−xj|σ]wij s.t., ‖x‖2=1,eTx=0\begin{array}{r}\underset{\mathbf{x}}{\text{max}} \sum\limits _{i j} \exp \left[-\frac{\left|x_{i}-x_{j}\right|}{\sigma}\right] w_{i j} \\text { s.t., }|\mathbf{x}|^{2}=1, \mathbf{e}^{T} \mathbf{x}=0\end{array}
一般情况下,我们可以引入 decay function Γ(dij)Γ(dij)\Gamma\left(d_{i j}\right),并将这三个嵌入目标写为
maxx∑ijΓ(|xi−xj|)wij, s.t. ,∥x∥2=1,eTx=0(20)maxx∑ijΓ(|xi−xj|)wij, s.t. ,‖x‖2=1,eTx=0(20)\underset{\mathbf{x}}{\text{max}} \sum\limits _{i j} \Gamma\left(\left|x_{i}-x_{j}\right|\right) w_{i j}, \text { s.t. },|\mathbf{x}|^{2}=1, \mathbf{e}^{T} \mathbf{x}=0\quad\quad(20)
下面是一系列的decay functions:
Laplacian embed: ΓLaplace (dij)=−d2ij(21)ΓLaplace (dij)=−dij2(21)\quad \Gamma_{\text {Laplace }}\left(d_{i j}\right)=-d_{i j}^{2}\quad\quad(21) Cauchy embed: ΓCauchy (dij)=1d2ij+σ2(22)ΓCauchy (dij)=1dij2+σ2(22)\quad \Gamma_{\text {Cauchy }}\left(d_{i j}\right)=\frac{1}{d_{i j}{2}+\sigma{2}}\quad\quad(22) Gaussian embed: ΓGaussian (dij)=e−d2ij/σ2(23)ΓGaussian (dij)=e−dij2/σ2(23)\quad \Gamma_{\text {Gaussian }}\left(d_{i j}\right)=e^{-d_{i j}^{2} / \sigma^{2}}\quad\quad(23) Exponential embed: Γexp(dij)=e−dij/σ(24)Γexp(dij)=e−dij/σ(24)\quad \Gamma_{\exp }\left(d_{i j}\right)=e^{-d_{i j} / \sigma}\quad\quad(24) Linear embed: Γlinear (dij)=−dij(25)Γlinear (dij)=−dij(25)\quad \Gamma_{\text {linear }}\left(d_{i j}\right)=-d_{i j} \quad\quad(25)
我们讨论了衰变函数的两个性质。
-
- 对衰减函数有一个要求:Γ(d)Γ(d)\Gamma(d) 必须是随着 ddd 的增加而单调递减的。如果违反了这种单调性,那么嵌入就没有意义了。
- 衰减函数在一个常数之前是未定义的,即 Γ′(dij)=Γ(dij)+cΓ′(dij)=Γ(dij)+c\Gamma^{\prime}\left(d_{i j}\right)=\Gamma\left(d_{i j}\right)+c 导致任何常数 ccc 得到相同的嵌入。
- 对衰减函数有一个要求:Γ(d)Γ(d)\Gamma(d) 必须是随着 ddd 的增加而单调递减的。如果违反了这种单调性,那么嵌入就没有意义了。
我们可以看到这些衰减函数的不同行为,如图3所示,我们发现,在 ΓLaplace (d)ΓLaplace (d)\Gamma_{\text {Laplace }}(d) 和 Γlinear (d)Γlinear (d)\Gamma_{\text {linear }}(d) 中,大距离对占优势,而在 Γexp(d)Γexp(d)\Gamma_{\exp }(d),ΓGaussian ΓGaussian \Gamma_{\text {Gaussian }} ,和 ΓCauchy (d)ΓCauchy (d)\Gamma_{\text {Cauchy }}(d) 中,小距离对占优势。
4.3. Algorithms to Compute Cauchy Embedding
我们的算法是基于以下定理的。
Theorem 1 If J®J®J® defined in Eq. (14) is Lipschitz continuous with constant L≥0L≥0L \geq 0 , and
R∗=argminR∥∥R−(R+1L∇J(R))∥∥2F(26) s.t. RRT=I,Re=0R∗=argminR‖R−(R+1L∇J(R))‖F2(26) s.t. RRT=I,Re=0\begin{array}{l}R^{*}=\arg\underset{\text{R}}{\text{min}} \left|R-\left(\tilde{R}+\frac{1}{L} \nabla J(\tilde{R})\right)\right|_{F}^{2} \quad\quad\quad\quad(26)\\text { s.t. } R R^{T}=I, R \mathbf{e}=\mathbf{0}\end{array}
then J(R∗)≥J(R)J(R∗)≥J(R)J\left(R^{*}\right) \geq J(\tilde{R})
证明:
Since J®J®J® is Lipschitz continuous with constant LL L , from (Nesterov, 2003), we have
J(X)≤J(Y)+⟨X−Y,∇J(X)⟩+L2∥X−Y∥2F,∀X,YJ(X)≤J(Y)+⟨X−Y,∇J(X)⟩+L2‖X−Y‖F2,∀X,YJ(X) \leq J(Y)+\langle X-Y, \nabla J(X)\rangle+\frac{L}{2}|X-Y|_{F}^{2}, \forall X, Y
By apply this inequality, we further obtain
J(R)≤J(R∗)+⟨R−R∗,∇J(R)⟩+L2∥∥R−R∗∥∥2F(27)J(R)≤J(R∗)+⟨R−R∗,∇J(R)⟩+L2‖R−R∗‖F2(27)J(\tilde{R}) \leq J\left(R{*}\right)+\left\langle\tilde{R}-R{*}, \nabla J(\tilde{R})\right\rangle+\frac{L}{2}\left|\tilde{R}-R{*}\right|_{F}{2}\quad\quad\quad(27)
By definition of R∗R∗R^{*} , we have
≤∥∥∥R∗−(R+1L∇J(R))∥∥∥2F∥∥∥R−(R+1L∇J(R))∥∥∥2F=1L2∥∇J(R)∥2F‖R∗−(R+1L∇J(R))‖F2≤‖R−(R+1L∇J(R))‖F2=1L2‖∇J(R)‖F2\begin{aligned}&\left|R^{*}-\left(\tilde{R}+\frac{1}{L} \nabla J(\tilde{R})\right)\right|_{F}^{2} \\leq \quad &\left|\tilde{R}-\left(\tilde{R}+\frac{1}{L} \nabla J(\tilde{R})\right)\right|_{F}{2}=\frac{1}{L{2}}|\nabla J(\tilde{R})|_{F}^{2}\end{aligned}
or
∥∥R∗−R∥∥2F−2⟨R∗−R,1L∇J(R)⟩+1L2∥∇J(R)∥2F≤1L2∥∇J(R)∥2F‖R∗−R‖F2−2⟨R∗−R,1L∇J(R)⟩+1L2‖∇J(R)‖F2≤1L2‖∇J(R)‖F2\left|R{*}-\tilde{R}\right|_{F}{2}-2\left\langle R^{*}-\tilde{R}, \frac{1}{L} \nabla J(\tilde{R})\right\rangle+\frac{1}{L^{2}}|\nabla J(\tilde{R})|_{F}^{2} \ \leq \frac{1}{L^{2}}|\nabla J(\tilde{R})|_{F}^{2}
∥∥R∗−R∥∥2F+2⟨R−R∗,1L∇J(R)⟩≤0(28)‖R∗−R‖F2+2⟨R−R∗,1L∇J(R)⟩≤0(28)\left|R{*}-\tilde{R}\right|_{F}{2}+2\left\langle\tilde{R}-R^{*}, \frac{1}{L} \nabla J(\tilde{R})\right\rangle \leq 0\quad \quad \quad (28)
By combining Eq. (27) and Eq. (28) and notice that L≥0L≥0L \geq 0 , we have
J(R∗)≥J(R)J(R∗)≥J(R)J\left(R^{*}\right) \geq J(\tilde{R})
which completes the proof. Further more, for Eq. (26), we have the following solution,
Theorem 2 R∗=VTR∗=VTR{*}=V{T} is the optimal solution of Eq. (26), where USVT=M(I−eeT/n)USVT=M(I−eeT/n)U S V^{T}=M\left(I-\mathbf{e e}^{T} / n\right) , is the Singular Value Decompotition (S V D) of M(I−eeT/n)M(I−eeT/n)M\left(I-\mathbf{e e}^{T} / n\right) and M=R+1L∇J(R)M=R+1L∇J(R)M=\tilde{R}+ \frac{1}{L} \nabla J(\tilde{R}) .
Proof. Let M=R+1L∇J(R)M=R+1L∇J(R)M=\tilde{R}+\frac{1}{L} \nabla J(\tilde{R}) , by applying the Lagrangian multipliers ΛΛ\Lambda and μμ\mu , we get following Lagrangian function,
L=∥R−M∥2F+⟨RRT−I,Λ⟩+μTRe(29)L=‖R−M‖F2+⟨RRT−I,Λ⟩+μTRe(29)\mathcal{L}=|R-M|_{F}^{2}+\left\langle R R^{T}-I, \Lambda\right\rangle+\mu^{T} R \mathbf{e}\quad \quad(29)
By taking the derivative w.r.t. R , and setting it to zero, we have
2R−2M+ΛR+μeT=0(30)2R−2M+ΛR+μeT=0(30)2 R-2 M+\Lambda R+\mu \mathbf{e}^{T}=0\quad \quad(30)
Since Re=0Re=0R \mathbf{e}=0 , and eTe=neTe=n\mathbf{e}^{T} \mathbf{e}=n , we have μ=2Me/nμ=2Me/n\mu=2 M \mathbf{e} / n , and
(I+Λ)R=M(I−eeT/n)(31)(I+Λ)R=M(I−eeT/n)(31)(I+\Lambda) R=M\left(I-\mathrm{ee}^{T} / n\right)\quad\quad\quad(31)
Since USVT=M(I−eeT/n)USVT=M(I−eeT/n)U S V^{T}=M\left(I-\mathbf{e e}^{T} / n\right) , we let R∗=VTR∗=VTR{*}=V{T} and Λ=US−IΛ=US−I\Lambda=U S-I , then the KKT condition of the Lagrangian function is satisfied. Notice that the objective function of Eq. (26) is convex w.r.t R . Thus R∗=VTR∗=VTR{*}=V{T} is the optimal solution of Eq. (26).
From the above theorem, we use the following algorithm to solve the Cauchy embedding problem.
Algorithm. Starting from an initial solution and an initial guess of Lipschitz continuous constant LLL , we iteratively update the current solution until convergence. Each iteration consists of the following steps: (1) Compute MMM ,
M←R+1L∇J®(32)M←R+1L∇J®(32)M \leftarrow R+\frac{1}{L} \nabla J®\quad\quad\quad(32)
(2) Compute the SVD of M(I−eeT/n):USVT=M(I−eeT/n)M(I−eeT/n):USVT=M(I−eeT/n)M\left(I-\mathbf{e e}^{T} / n\right): U S V^{T}=M(I- ee \left.^{T} / n\right) , and set R←VTR←VTR \leftarrow V^{T} , (3) If Eq. (28) does not hold, increase LLL by L←γLL←γLL \leftarrow \gamma L .We use the Laplacian embedding results as the initial solution for the gradient algorithm.
5. Experimental Results
略
-
Paper Information
-
Abstract
-
1 Introduction
-
2 Laplacian Embedding
-
3 The Local Topology Preserving Property of Graph Embedding
-
3.1 Local Topology Preserving
-
3.2. Experimental Evidences
-
4. Cauchy Embedding
-
4.1. Multi-dimensional Cauchy Embedding
-
4.2. Exponential and Gaussian Embedding
-
4.3. Algorithms to Compute Cauchy Embedding
-
5. Experimental Results
__EOF__
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-P9j7oMJK-1647796630494)(https://blog.csdn.net/BlairGrowing)]Blair - https://blog.csdn.net/BlairGrowing/p/16030228.html
- 评论和私信会在第一时间回复。或者直接私信我。
- 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
- 如果您觉得文章对您有帮助,可以点击文章右下角**【[推荐](javascript:void(0)😉】**一下。