Differences

This shows you the differences between two versions of the page.

--- keynote:lesson03 [2010/04/09 09:26]
10921013
+++ keynote:lesson03 [2010/04/29 22:52]
11021002
@@ Line 43: / Line 43: @@
   * Eckart-Young定理
 令$S_q$ 为除了最前面的q个对角线元素之外的元素全为0的矩阵。则$\widehat{X_q}=US_qV^T$ 满足$\min_{rank(\widehat{X_q})=q} \big\Vert\widehat{X}-\widehat{X_q}\big\Vert$
+  * 主元分析例子-Eigenfaces(G. D. Finlayson, B. Schiele & J. Crowley.  Comprehensive colour image normalization. ECCV 98 pp. 475~490)
+{{:keynote:pca1.jpg|}} {{:keynote:pca2.jpg|}}
+  * PCA与降维
+通过奇异值分解进行空间变换：$X->Y$，形成从p维到q维的变换，其中p>>q，之后进行重现并计算误差。
 ==== 3.1.6 主成分分析法的不足 ====
-只适用于一般的离散数据集，对于非线性数据集不适用。
+.只适用于一般的离散数据集，对于非线性数据集不适用。
+.虽然如此，PCA 方法还是在许多领域（例如人脸识别）得到广泛应用，此外，也有提出使用 Kernel 方法扩展 PCA 的算法，亦即先将原始数据从特征空间映射到一个高维空间中，消除其非线性的性质，然后在这样的空间中应用 PCA ，亦即 KernelPCA 方法（参见 Scholkopf, B. and Smola, A. and Muller, K.R., //Kernel principal component analysis//, Artificial Neural Networks—ICANN'97）。
+除了 KernelPCA 之外，另一种将 PCA 用在非线性数据分析的方法是使用 LocalPCA ，现在比较热的流形学习中对于数据分布在一个低维流形上的假设实际上就是假定了数据在一个足够小的局部领域内是程线性的，这也正式 PCA 用武的地方，因此，在局部范围内使用 PCA 来分析流形结构也就成了一个顺理成章的事情。比如，在 tangent space learning 中，算法的目的是得出 manifold 的切空间，而如果使用局部方法的话，在一个流行局部的切空间其实就可以直接通过对局部 sample 进行 PCA 分解而求得。
+<note important>Extended by  --- //[[pluskid@gmail.com|张驰原]] 2010/04/26 14:28//</note>
+.以下是对课件的补充和扩展（介绍RPCA及其在CVPR2010人脸图像上的应用）：
+不适用于非高斯噪声污染的数据集。\\
+设数据$m\times n$矩阵$M=L+S$，$L$为潜在的低秩矩阵，$S$噪声矩阵。如果$S$非高斯噪声，例如稀疏且幅值不定的噪声，那么PCA将失效。\\
+{{:keynote:pca_done_well.jpg|}}\\
+{{:keynote:pca_fail.jpg|}}\\
+此时，宜用改进的模型RPCA(Robust PCA)。
+RPCA通过以下目标函数求解：
+<jsmath>\min_{L,S}\|L\|_{*}+\lambda \|S\|_{l_{1}} \;\; s.t. \; M=L+S</jsmath>
+$\lambda$是权重参数，通常设为$\lambda=\frac{1}{\sqrt{\max\{m,n\}}}$。 $\|\cdot\|_{*}$为核范数，即矩阵奇异值之和。$\|\cdot\|_{l_{1}}$为一范数，即矩阵元素绝对值之和。\\
+此凸函数具有唯一最小值。使用ALM(Augmented Lagrange Multiplier)求解，最小化增强的拉格朗日函数：
+<jsmath>\min_{L,S,Y}l(L,S,Y)=\min_{L,S,Y}\|L\|_{*}+\lambda \|S\|_{l_{1}}+ tr\{Y^{T}(M-L-S)\}+\frac{\mu}{2}\|M-L-S\|_{F}^{2}</jsmath>
+$\mu$为另一权重，可取值$\mu=nm/(4\|M\|_{1})$。$\|\cdot\|_{F}$为Frobenius范数，即矩阵元素平方和开根号。
+通过迭代计算求最优值:\\
+.初始化：$S_{0}=Y_{0}=0$，$k=0$\\
+.while $\|M-L-S\|_{F}>10^{-7}\|M\|_{F}$ do\\
+.  $L_{k+1}=D_{1/\mu}(M-S_{k}-Y_{k}/\mu)$\\
+.  $S_{k+1}=S_{\lambda/\mu}(M-L_{k+1}+Y_{k}/\mu)$\\
+.  $Y_{k+1}=Y_{k}+\mu (M-L_{k+1}-S_{k+1})$\\
+.  $k=k+1$\\
+.end while\\
+.输出$L,S$\\
+对于标量$x$，函数$S_{a}(x)=sgn(x)max\{|x|-a,0\}$，即截断操作。当输入为矩阵时，对每一元素独立操作。函数$D_a(X)$也是截断操作，但作用于矩阵奇异值：设矩阵$X$的SVD分解为$X=U\Sigma V^{T}$，那么$D_a(X)=US_{a}(\Sigma)V^{T}$。
+对RPCA做一些修改，可用于人脸对齐与去噪。这是RPCA研究团队一篇CVPR2010的工作：\\
+Yigang Peng, Arvind Ganesh, John Wright, Wenli Xu, and Yi Ma. RASL: Robust Alignment by Sparse and Low-rank Decomposition for Linearly Correlated Images. To appear in CVPR, June 2010.\\
+{{:keynote:rals.jpg|}}\\
+(a)算法输入40张同一人不同光照、遮挡，姿势和表情的图片。(b)-(d)为算法输出，算法同时完成对齐(b)、提取真实人脸（c）和分离噪声（异物）(d)。算法主要思路为寻找一组几何变换$\tau$使对齐后的图像$Dº\tau$能被分解为低秩成分和稀疏噪声。
+ <note important> --- //[[fancij@139.com|胡振方]] 2010/04/27 21:50//</note>
 ===== 3.2 非线性降维算法 =====

Applied Mathematics for Computer Science

User Tools

Site Tools

Differences

Page Tools