今天记录一下第六节课程，主要是LOW RANK的技术
LOW RANK MINIMIZATION
低秩分解（Low-rank Matrix Factorization)
Motivation: Visual Data often has an intrinsic low-rank structure
例如：FACE IMAGES, SURVEILLANCE VIDEO, MULTISPECTRAL IMAGE,这些数据都是高度冗余的(highly redundancy)，所以我们可以使用LOW RANK技术来降维，甚至数据复原和分类等
$$Y = X + E$$
Y是数据样本拉成向量后，堆叠成为的矩阵；X是隐含的低秩结构矩阵；E是Residual Matrix
我们可以这样建模低秩矩阵X，$X \in R^{d*r}$,d为数据的维度，n为样本的数量；构建Basis Matrix $U \in R^{d*r}$，其中$r<<d,n$,这是矩阵的秩;系数矩阵$V \in R^{n*r}$;
$X = U * V^T$, $Y = UV^T+E$
如何构建近似的低秩矩阵，如何估计E？
- 最佳近似估计，依赖于对residual(noise)的分布估计：1.iid GAUSSIAN； 2.iid LAPLACIAN 3.MIXTURE OF GAUSSIAN 4.MORE COMPLEX NOISE
根据MLE得到L2的保真项其实就是对应”误差分布为独立同分布的高斯模型“的假设
其中对于X的分解可以直接用SVD：$X = USV^T$
同理，L1的LRMF对应”误差分布为独立同分布的拉普拉斯模型“的假设
L1的模型具有长尾效应，更适应于outliers和heavy noises的情况。
第三种是之前两种的混合噪声模型：$Y=UV^T+E+N$，一般使用variational bayes方法来求解此类问题。
最后是复杂噪声模型：Mog-LRMF(ICCV-2013), DP-GMM(CVPR,2015), MoEP-LRMF(ICCV,2015; TIP,2016)
LRMF with missing elements
Y可以是不完整矩阵，可以引入一个二元矩阵W：
对于F-norm的做法：
对于L1-norm的做法：
优缺点：
- 矩阵的阶需要预定义
- 清晰地表达子空间和系数关系
- 容易嵌入对子空间的先验
- 不是凸优化问题
Weighted Nuclear Norm Minimization(WNNM)
针对矩阵的秩的正则化$Rank(X) = \Sigma||\sigma_i(X)||_0$
核范数Nuclear Norm: $||X||_* = \Sigma||\sigma_i(X)||_1$
优点：
- Tightest Convex Envelop of rank minimization
- Closed form solution
缺点： - 对于所有的奇异值给以同样的权值，忽略了它们间不同的权值作用
WNNM就是对此Formulation里面的奇异值作加权，但如此一来WNNM是非凸，sub-gradient方法不能用来分析它的优化过程。
以下的定理和引理确保了WNNM的优化可行性。
