低秩模型

本文最后更新于:2020年6月18日 下午

本文参考了大牛林宙辰老师关于低秩表示的三篇文章[1]\(^,\)[2]\(^,\)[3]

矩阵的秩

  • 高维数据集中在若干低维流形附近,当低维流形为最简单的子空间时,找出样本点所在不同维数子空间的问题就称为子空间聚类问题,它是子空间恢复问题的一种。

  • 低维的流形往往都可以用低维的子空间来近似,比如前几个主分量所张成的线性子空间。行列相关性和低维子空间都表明:秩是矩阵稀疏性度量

  • 由于子空间的维数等于子空间上样本点所构成的数据矩阵的秩,因此子空间恢复问题往往可建模成低秩问题,即求解秩尽可能小的某矩阵的问题。

  • 传统 PCA 只在噪声是高斯噪声时可以准确恢复潜在的低秩结构。对于非高斯噪声,如果噪声很强,即使是极少数的噪声,也会使传统的主元分析失败。

有代表性的低秩模型

  • 矩阵填充(Matrix Completion, MC)模型

\[ \min_A \operatorname{rank}(A) \quad \text{s.t.} \pi_\Omega (D)=\pi_\Omega (A) \]

通过已知矩阵的某些位置的值推断该矩阵的缺失值,并恢复低秩结构

  • 鲁棒主成分分析(Robust Principal Component Analysis, RPCA)模型

\[ \min_{A,E} \operatorname{rank}(A) + \lambda \|E\|_0 \quad \text{s.t.} D=A+E \]

从已知样本点中提取一个低维子空间,使得样本点偏离该子空间的误差稀疏

  • 低秩表示(Low-Rank Representation,LRR)模型

\[ \min_{Z,E} \operatorname{rank}(Z) + \lambda \|E\|_{2,0} \quad \text{s.t.} D=DZ+E \]

从已知样本点中提取多个低维子空间,使得样本点偏离所属子空间的误差稀疏

  • 潜在(或隐性)低秩表示(Latent Low-Rank Representation,LatLRR)模型

\[ \min_{Z,L,E} \operatorname{rank}(Z) +\operatorname{rank}(L) +\lambda \|E\|_{0} \quad \text{s.t.} D=DZ+LD+E \]

为了解决LRR 模型在样本不足时面对的问题而提出

凸松弛模型

  • 松弛的矩阵填充(Relaxed Matrix Completion)模型

\[ \min_A \|A\|_* \quad \text{s.t.} \pi_\Omega (D)=\pi_\Omega (A) \]

  • 松弛的鲁棒主成分分析(Relaxed Robust Principal Component Analysis)模型

\[ \min_{A,E} \|A\|_* + \lambda \|E\|_1 \quad \text{s.t.} D=A+E \]

  • 松弛的低秩表示(Relaxed Low-Rank Representation)模型

\[ \min_{Z,E} \|Z\|_* + \lambda \|E\|_{2,1} \quad \text{s.t.} D=DZ+E \]

  • 松弛的潜在低秩表示(Relaxed Latent Low-Rank Representation)模型

\[ \min_{Z,L,E} \|Z\|_* +\|L\|_* +\lambda \|E\|_{1} \quad \text{s.t.} D=DZ+LD+E \]

无噪低秩模型

\(\operatorname{rank}(Z) = r\),矩阵\(D\)的SVD:\(D=U_D \Sigma_D V_D^T\),则下述松弛的无噪低秩模型 \[ \min_Z \|Z\|_* \quad \text{s.t.} D=DZ \] 具有唯一闭解\(Z^{*} = V_D V_D^T\)。矩阵\(V_D V_D^T\)在立体视觉里被称为形状交互矩阵(Shape Interaction Matrix)。此时\(Z\)的核范数等于\(D\)的秩 \[ \min_{Z\in \{D=DZ\}} \|Z\|_* = \operatorname{rank}(D) \] 该模型的推广形式,即松弛的广义无噪低秩模型 \[ \min_Z \|Z\|_* \quad \text{s.t.} D=BZ \] 具有唯一闭解\(Z^* = B^{\dagger} D\),其中\(^{\dagger}\)为Moore-Penrose 伪逆。更进一步,对任意酉不变范数\(\|\cdot\|_{UI}\),若\(\{D=BZ\}\neq \varnothing\),则 \[ \min_Z \|Z\|_{UI} \quad \text{s.t.} D=BZ \] 都具有唯一闭解\(Z^* = B^{\dagger} D\)。设\(D=U_D \Sigma_D V_D^T\)\(B=U_B \Sigma_B V_B^T\)原始的广义无噪低秩模型 \[ \min_{Z} \operatorname{rank}(Z) \quad \text{s.t.} D=BZ \] 所有解满足形式\(Z^* = B^{\dagger} D + S V_D^T\),其中矩阵\(S\)满足 \(V_B^T S = 0\)

潜在低秩表示模型

低秩表示模型在样本不足时,已有样本\(D_O\)可能不足以自我表达。引入未观测的隐藏样本\(D_H\),约束改为\(D_O = [D_O \quad D_H]Z\)。设\([D_O \quad D_H]\)的奇异值分解为\(U \Sigma V^T\),并对\(V\)分块\(\begin{bmatrix} V_O \\ V_H \end{bmatrix}\),则 \[ D_O = U \Sigma V_O^T, D_H = U \Sigma V_H^T, V_O^T = V^T Z \] 以下潜在低秩表示模型 \[ \min_Z \|Z\|_* \quad \text{s.t.} D_O = [D_O \quad D_H]Z \] 解可表示为\(Z^* = VV_O^T\)\[ \begin{aligned} D_O &= [D_O \quad D_H]Z^* = [D_O \quad D_H]\begin{bmatrix} V_O V_O^T \\ V_H V_O^T \end{bmatrix} \\ &= D_O V_O V_O^T + D_H V_H V_O^T = D_O (V_O V_O^T) + (D_H V_H \Sigma^{-1} U^T) D_O \end{aligned} \] 两个括号的矩阵式低秩的,将\(D_O\)写成\(D\)原始无噪潜在低秩表示模型求解两个低秩矩阵 \[ \min_{Z,L,E} \operatorname{rank}(Z) +\operatorname{rank}(L) \quad \text{s.t.} D=DZ+LD \]

其全部解为 \[ Z^* = V_D \hat WV_D^T +S_1 \hat WV_D^T, L^* = U_D \Sigma_D (I-\hat W)\Sigma_D^{-1}U_D^T +U_D \Sigma_D(I-\hat W) S_2 \] 其中\(\hat W\)是任意幂等矩阵,\(S_1, S_2\)满足

  • \[ V_D^T S_1 =0,S_2 U_D = 0 \]

  • \[ \operatorname{rank}(S_1)\leq\operatorname{rank}(\hat W),\operatorname{rank}(S_2)\leq\operatorname{rank}(I-\hat W) \]

松弛的无噪潜在低秩表示模型 \[ \min_{Z,L,E} \|Z\|_* +\|L\|_* \quad \text{s.t.} D=DZ+LD \]

其全部解为 \[ Z^* = V_D \hat WV_D^T , L^* = U_D (I-\hat W)U_D^T \] 其中\(\hat W\)是块对角矩阵,满足:

  • \(\hat W\)的对角块与\(\Sigma_D\)相容
  • \(\hat W\)\(I-\hat W\)半正定。

广义鲁棒主成分分析模型

含噪声情况下,前面四个模型加上关于噪声\(E\)的正则项\(f(E)\),对应的约束条件由\(D=A\)修改为\(A=AZ,D=A+E\),潜在的低秩矩阵为\(Z\)。这些模型均可化解为广义的鲁棒主成分分析问题来解决 \[ \min_{A,E} \operatorname{rank}(A) + \lambda f(E) \quad \text{s.t.} D=A+E \]

graph TB
    A[原始的鲁棒低秩表示模型] --- E(广义鲁棒主成分分析模型)
    B[松弛的鲁棒低秩表示模型] --- E(广义鲁棒主成分分析模型)
	E(广义鲁棒主成分分析模型) --- C[原始的鲁棒潜在低秩表示模型]
	E(广义鲁棒主成分分析模型) --- D[松弛的鲁棒潜在低秩表示模型]
    style E fill:#f9f,stroke:#333,stroke-width:2px

鲁棒主成分分析

单子空间模型

数据中有稀疏大噪声时如何恢复数据的低秩结构 \[ \min_{A,E} \operatorname{rank}(A) + \lambda \|E\|_0 \quad \text{s.t.} D=A+E \] 若矩阵\(D\)可以只在部分位置的观测值,推广后的模型 \[ \min_{A,E} \operatorname{rank}(A) + \lambda \|E\|_0 \quad \text{s.t.} \pi_\Omega (D)= \pi_\Omega (A+E) \] 带稠密高斯噪声的广义 RPCA 模型 \[ \min_{A,E} \operatorname{rank}(A) + \lambda \|E\|_0 \quad \text{s.t.} \|\pi_\Omega (D) - \pi_\Omega (A+E)\|_F^2 \leq \epsilon \] 噪声集中在若干列的情况,提出了 Outlier Pursuit 模型 \[ \min_{A,E} \operatorname{rank}(A) + \lambda \|E\|_{2,0} \quad \text{s.t.} D=A+E \]

多子空间模型

要求表达系数矩阵 \(Z\) 低秩,增强 \(Z\) 各列之间的相关性以提高对噪声的抵抗能力,低秩表示模型 \[ \min_{Z,E} \operatorname{rank}(Z) + \lambda \|E\|_{0} \quad \text{s.t.} D=DZ+E \] 其最优表达系数矩阵\(Z^*\)可作为样本间的相似性度量。在样本不足情形,潜在低秩表示模型 \[ \min_{Z,L,E} \operatorname{rank}(Z) +\operatorname{rank}(L) +\lambda \|E\|_{0} \quad \text{s.t.} D=DZ+LD+E \] \(DZ\)Principal Feature\(LD\)Salient Feature\(Z\) 用于子空间聚类,\(L\)则可用于提取数据的鉴别信息以识别。固定秩表示( Fixed Rank Representation, FRR)模型 \[ \min_{Z,E} \|Z- \hat Z\|_F^2+ \lambda \|E\|_{2,0} \quad \text{s.t.} D=DZ+E, \operatorname{rank}(\hat Z) \leq r \] 其中\(\hat Z\)用于度量样本间的相似性。

非线性模型

利用 Kernel 技巧,通过非线性映射\(\phi\)将样本映射至高维空间的线性子空间上,运用LRR模型 \[ \min_Z \|\phi(X) - \phi(X)Z\|_F^2 +\lambda \|Z\|_* \] 第一项展开得到\(\phi^T(X) \phi(X)\),引入核函数\(K(x,y) = \phi^T(x) \phi(y)\)。但当噪声不是高斯时,上述核技巧不适用。

算法

凸优化算法

\(\ell_0\)范数换为\(\ell_1\)范数,秩换位核范数。修改后的模型的全局最优解,但是解有可能不够低秩或稀疏

  • 加速近邻梯度法(Accelerated Proximal Gradient, APG)

对于带线性约束的优化问题,可以把约束的平方放到目标函数里作为惩罚项,再应用 APG 求近似解。为加快收敛速度,惩罚系数要逐渐增加到较大的值,这一重要技巧称为Continuation。

考虑无约束凸优化问题 \[ \min_{x \in \mathbb R ^m} f(x) \] 其中\(f(x)\)\(\mathcal C^{1,1}\)的凸函数,其导数满足Lipschitz 连续性 \[ \|\nabla f(x) - \nabla f(y)\| \leq L(f)\|x-y\|, \quad \forall x,y\in \mathbb R^m \] \(L(f)\)\(f\)的一阶 Lipschitz 系数,令\(R(f)\)为原点到解集\(Q\)的距离。

固定步长的梯度下降法求解 \[ x_{k+1} = x_{k} - \gamma \nabla f(x_k), \gamma \in (0,\frac{2}{L(f)}) \] 则收敛速度是\(\mathcal O(k^{-1})\): \[ f(x_k) - f^* \leq \frac{R^2 (f)}{\gamma (2-\gamma L(f))k} \] Nesterov 算法 \[ \begin{gather} x_k = y_k -\frac{1}{L(f)} \nabla f(y_k)\\ t_{k+1} = \frac{1+\sqrt{1+4t_k^2}}{2}\\ y_{k+1} = x_k + \frac{t_k -1}{t_{k+1}}(x_k - x_{k-1}) \end{gather} \] 则收敛速度是\(\mathcal O(k^{-2})\)\[ f(y_k) - f^* \leq \frac{2 L(f) R^2 (f)}{k^2} \] 目标函数稀疏性和低秩性往往都是不可导的,Nesterov 方法做了推广,处理如下形式的无约束凸优化问题: \[ \min_{x \in \mathbb R ^m} f(x) + g(x) \] 其中\(f(x)\)\(\mathcal C^{1,1}\)的凸函数,凸函数\(g(x)\)可以不可导。APG 算法如下 \[ \begin{gather} x_k = \arg\min_x \left\{g(x) + \frac{L(f)}{2} \left\|x-\left(y_k - \frac{1}{L(f)} \nabla f(y_k)\right)\right\|^2\right\}\\ t_{k+1} = \frac{1+\sqrt{1+4t_k^2}}{2}\\ y_{k+1} = x_k + \frac{t_k -1}{t_{k+1}}(x_k - x_{k-1}) \end{gather} \] 则收敛速度是\(\mathcal O(k^{-2})\)。因为\(g(x)\)一般会取作矩阵或向量的范数,其中的子问题 \[ \min_x g(x) + \frac{\alpha}{2} \|x - z_k\|^2 \] 通常容易求解,甚至有闭解。当\(g(x)\)取为\(\ell_1\)范数是解为软收缩算子(Shrinkage Operator);当\(g(x)\)取为核范数是解为奇异值阈值算子(Singular Value Thresholding)。求解秩极小化问题往往离不开奇异值分解,PROPACK可以计算大于设定阈值的的奇异值及其奇异向量。

回到Lipschitz条件,其本质是 \[ f(x) \leq f(y) + \langle x-y, \nabla f(y)\rangle + \frac{1}{2} L(f) \|x-y\|^2, \quad \forall x,y \in \mathbb R \] 可以放宽为 \[ f(x) \leq f(y) + \langle x-y, \nabla f(y)\rangle + \frac{1}{2} L(f) \|x-y\|_{L_f}^2, \quad \forall x,y \in \mathbb R \] 其中\(\|x\|_{L_f} = \sqrt{x^T L_f x}\)\(L_f\)可以选成对角阵,为不同的变量提供不同的一阶 Lipschitz 系数,因此可以加速收敛。

  • 交错方向法(Alternating Direction Method, ADM)

ADM 面向目标函数可分解(即为两个不同变量凸函数的和)、带线性约束和凸集约束的问题,它是 Lagrange 乘子法的一种变形。它先构造问题的增广Lagrangian 函数,然后通过交替极小化增广 Lagrangian 函数来更新两个变量,最后更新 Lagrange 乘子,如此迭代。

考虑带约束凸优化问题 \[ \min_x f(x) \quad \text{s.t.} Ax = b \] 对应的增广 Lagrange 函数 \[ L(x,\lambda,\beta) = f(x) + \langle \lambda, Ax - b\rangle + \frac{\beta}{2}\|Ax - b\|^2 \] ALM 算法 \[ \begin{gather} x_{k+1} = \arg\min_x L(x,\lambda_{k},\beta)\\ \lambda_{k+1} = \lambda_k + \beta(Ax_{k+1}-b) \end{gather} \]\(f(x)\)具有可分解性结构,即 \[ f(x) = f_1 (y) + f_2 (z), x=(y^T, z^T)^T \] 约束条件\(Ax = b\)分解为 \[ A_1 y + A_2 z = b \] 交错方向法迭代过程 \[ \begin{gather} y_{k+1} = \arg\min_x f_1(y) + \frac{\beta}{2} \|A_1 y + A_2 z_k - b + \frac{\lambda_k}{\beta}\|^2\\ z_{k+1} = \arg\min_x f_2(z) + \frac{\beta}{2} \|A_1 y_{k+1} + A_2 z - b + \frac{\lambda_k}{\beta}\|^2\\ \lambda_{k+1} = \lambda_k + \beta(A_1 y_{k+1} + A_2 z_{k+1} - b) \end{gather} \] 在子问题不容易求解的情形,可以考虑线性化增广 Lagrangian 函数的增广项,把问题进一步简化,这一技术称为线性化交错方向法(Linearized Alternating Direction Method, LADM)

对于如下一般的无约束问题 \[ \min_x f(x) +\frac{\alpha}{2}\|Ax - b\|^2 \] 二次项通过做一阶 Taylor展开并加上一个近邻项(proximal term)来近似 \[ \begin{aligned} & \min_x f(x) + \beta \langle A^T(Ax-b), x-x_k\rangle + \frac{\alpha \eta}{2}\|x - x_k\|^2 \\ = & \min_x f(x) + \frac{\alpha \eta}{2}\|x - x_k + \frac{A^T(Ax-b)}{\eta}\|^2 \\ \end{aligned} \]

非凸优化算法

非凸的连续函数来近似,如Schatten-p 范数近似秩,\(\ell_p (p\in(0,1))\)范数近似\(\ell_0\)范数。往往能得到更低秩和更稀疏的解,但是不能得到修改后的模型的全局最优解,解的质量可能依赖于初值。

  • 迭代重加权最小二乘法

\(tr((XX^T)^{\frac{p}{2}})\)近似为\(tr((X_k X_k^T)^{\frac{p}{2}-1}XX^T)\)\(|x_i|^p\)近似为\(|x_i^{(k)}|^{p-2} x_i^2\)

  • 截断核范数

\[ \|X\|_r = \sum_{i=r+1}^{\min(m,n)} \sigma_i(X) \]

代表性应用

图像批量对齐(RASL)或变换不变低秩纹理(TILT):通过几何变换\(\tau\)\(D\)所代表的信息校正,这些特性可以通过低秩性来进行刻画。 \[ \min_{\tau,A,E} \|A\|_* + \lambda \|E\|_1 \quad \text{s.t.} D \circ \tau = A + E \]\(\tau\)局部线性化的迭代直至\(\Delta\tau_k\)足够小 \[ \begin{gather} \min_{\Delta\tau_k,A,E} \|A\|_* + \lambda \|E\|_1 \quad \text{s.t.} \quad D \circ \tau_k + J\Delta\tau_k= A + E\\ \tau_{k+1} = \tau_k + \Delta\tau_{k} \end{gather} \]

小结

有些问题的数据本身可能没有低秩性,此时可以引入适当变换增强其低秩性(如 RASL/TILT 对 RPCA 的改进)

参考