浅说范数规范化(二)—— 核范数

矩阵补全(matrix completion)问题

这个问题最早火起来是因为 Netflix 公司悬赏 100 万美金的公开挑战,奖励给能够改进公司现行矩阵补全算法 10% 以上最优胜的队伍。最后的结果是 2009 年 9 月 BellKors Pragmatic 拿走了奖金。

什么是矩阵补全问题呢?用 Netflix 的数据集来作说明。
简单的来说就是一个电影评分系统要根据非常稀疏的现有数据集(一个用户可能只 rate 了几十部电影)来推断整个用户群对不同电影的评分。

这个问题在推荐系统、图像处理等方面都有广泛的应用。
接着,这类问题一般都有隐含的假设,即最终的矩阵应该是低秩(low rank)的。
这其实也很好理解,因为我们一般会觉得:1、不同用户对于电影的偏好可以分成聚落(cliques),比如按照观众的年龄来分,年龄相仿的观众口味往往相近;2、电影也可以分成大致几种不同的题材(genres),如:爱情片、动作片、科幻片等。所以会有低秩的特性。
简单来说,这个矩阵的行和列会有“协同”的特性,这也是这个问题的别名协同过滤(collaborative filtering)的得名原因。
另外,低秩限制会比较实用,人们都比较喜欢得到稀疏解,使得整个问题更有可诠释性。

所以这个问题的目标函数被定义成下面的样子:
$$
\begin{aligned}
&\mathrm{minimize} \quad \mathrm{rank}(Z) \\
&\text{subject to} \quad \sum_{(i,j):\text{Observed}} (Z_{ij} - X_{ij})^{2} \le \delta
\end{aligned} \\
\text{Impute missing } X_{ij} \text{ with } Z_{ij}
$$
然而问题来了,这个问题是非凸的,而且这种问题的规模都非常大,没办法在如此庞大的 NP-hard 问题中找到全局最优解。

早先时候,人们使用了一些启发式算法。
后来人们发现,核范数是矩阵秩的一个很好的凸近似。
(原因有点类似与 L1 范数是 L0 范数的一个凸近似。)
下面就介绍一下核范数的一些性质。

核范数

定义

矩阵 $X$ 的核范数定义为:
$$
\lVert X \rVert _{\ast} = \mathrm{tr}\left( \sqrt{X^{\mathsf{T}}X} \right)
$$
显而易见,核范数也可以等价地定义为矩阵特征值的和,考虑 $X$ 的特征值分解 $X=U \Sigma V^{\mathsf{T}}$ 显然有:
$$
\begin{aligned}
\mathrm{tr}\left( \sqrt{X^{\mathsf{T}}X} \right) & = \mathrm{tr} \left( \sqrt{(U \Sigma V^{\mathsf{T}})^{\mathsf{T}}U \Sigma V^{\mathsf{T}}} \right) \\
& = \mathrm{tr} \left( \sqrt{V \Sigma^{\mathsf{T}} U^{\mathsf{T}} U \Sigma V^{\mathsf{T}}} \right) \\
& = \mathrm{tr} \left( \sqrt{V \Sigma^{2} V^{\mathsf{T}}} \right) \quad \left( \Sigma^{\mathsf{T}} = \Sigma \right) \\
& = \mathrm{tr} \left( \sqrt{V^{\mathsf{T}} V \Sigma^{2}} \right) \\
& = \mathrm{tr} (\Sigma)
\end{aligned}
$$

凸性的证明

首先,矩阵诱导范数是凸的,即:令 $ f_x (A) = \lVert Ax \rVert _{p} \quad (p \ge 1) $ ,则 $f_x$ 凸,故 $\lVert A \rVert _{p} = \sup\limits_{\Vert x \rVert _{p}=1} f_x (A)$ 凸。特别的,$\lVert A \rVert_{2}$ 凸。
因为 $\lVert A \rVert_{\ast}$ 和 $\lVert A \rVert_{2}$ 是对偶范数,所以 $\lVert A \rVert_{\ast}$ 凸。($\lVert A \rVert_{\ast}=\sup \limits_{\lVert X \rVert_{2}=1} \mathrm{tr} \left( A^{\mathsf{T}}X \right)$)

梯度的求解

基于上述 S.V.D 的假设,我们可以轻易地得到,
$$
\frac{\partial \lVert X \rVert_{\ast}}{\partial X} = \frac{\partial \mathrm{tr} (\Sigma)}{\partial X} = \frac{\mathrm{tr} (\partial \Sigma)}{\partial X}
$$
所以我们需要解出 $\partial \Sigma$ ,
考虑 $X=U \Sigma V^{\mathsf{T}}$ ,因此:
$$
\begin{aligned}
& & \partial X & = (\partial U )\Sigma V^{\mathsf{T}} + U (\partial \Sigma) V^{\mathsf{T}} + U \Sigma (\partial V^{\mathsf{T}}) \\
&\Rightarrow \, & \partial \Sigma & = U^{\mathsf{T}} (\partial X) V - U^{\mathsf{T}} (\partial U) \Sigma - \Sigma (\partial V^{\mathsf{T}}) V \\
& & & = U^{\mathsf{T}} (\partial X) V \qquad (- U^{\mathsf{T}} (\partial U) \Sigma - \Sigma (\partial V^{\mathsf{T}}) V = 0)
\end{aligned}
$$
所以:
$$
\frac{\partial \lVert X \rVert_{\ast}}{\partial X} = \frac{\mathrm{tr} (\partial \Sigma)}{\partial X} = \frac{\mathrm{tr} (U^{\mathsf{T}} (\partial X)V)}{\partial X} = \frac{\mathrm{tr} (V U^{\mathsf{T}} (\partial X))}{\partial X} = (V U^{\mathsf{T}})^{\mathsf{T}} = U V^{\mathsf{T}}
$$

低秩问题的近似

定义了核范数以后,我们就可以将低秩优化问题近似成相应的核范数优化问题了。
即:
$$
\begin{aligned}
&\mathrm{minimize} \quad \lVert Z \rVert_{\ast} \\
&\text{subject to} \quad \sum_{(i,j):\text{Observed}} (Z_{ij} - X_{ij})^{2} \le \delta
\end{aligned} \\
\text{Impute missing } X_{ij} \text{ with } Z_{ij}
$$