大约三周以前，听了一个presentation，讲到了 network 研究中度量关系网络的矩阵的 「低秩」(low rank) 性质。之后我在浏览一些高维计量文章时，又见到了这个概念，以及 「核范数」(nuclear norm, aka trace norm)。我印象里应该见过它们很多次，有些模糊的记忆片段，突然想起和硕士期间导师的交流中他提到过，遂从聊天记录中找到一些珍贵文件，当时他让我学习一下关于 「矩阵补全」(matrix recovery, or matrix completion) 的内容，我没来得及看。那么这几天就学习学习，说不定以后能派上用场。
内容提要
本文将从矩阵恢复问题出发，介绍秩的最小化问题如何转变为一个核范数的最小化问题，前者是一个非凸的优化问题，很难求解，后者是一个凸优化问题，尽管不可求微分，但凸问题总是更易于求解的。
Motivation
我们所感兴趣的问题是，如何基于非常有限的信息复原一个（低秩）矩阵。这一话题原本来自于工程实践的需要，例如计算机视觉领域的图像降噪，我们知道图像是由像素点构成的，因而整个图像可以视为一个大矩阵，当有一些像素被破坏，得到的就是一个不完整的矩阵，对图像降噪就是要补全那些污损或缺失的像素点；又如著名的 Netflix 问题（类似地，在国内语境下是豆瓣问题）：Netflix 用户评分矩阵只包含了某些用户对某些电影的评分，而不是每个用户对所有电影的评分（如下图所示），我们希望能推测出那些缺失的评分。这些问题都涉及到矩阵补全。
那么，这和低秩又有什么关系呢？很显然，在没有任何限制条件下去补全那些未知的项，我们有无数种填充方式。想要唯一地重建一个矩阵，这个矩阵必须有些特殊的结构作为限制，而低秩就是一个合理的结构。低秩意味着，矩阵的列向量高度线性相关──它们扩展形成的线性空间是低维的。说得更加人话就是，数据中的大部分波动都由少数几个因子驱动。
现在可能又要问了，低秩在实践中是一个合理的假设吗？以 Netflix 评分矩阵为例，直觉上，同一类用户群体的行为、特征有很高的相似性，因此他们的潜在评分高度一致，这样评分矩阵的「主成分」实际上就是几个群体的评价，从而是低秩的。
核范数最小化
低秩矩阵的补全可分为两类方法 (Gu et al. 2014)：矩阵分解法 和 求解秩最小化问题法。前者用两个低秩矩阵之积作为构造方式，可留待以后学习；后者是本文要讨论的内容。
秩最小化问题的正式表述
假设真实矩阵是 $\bm{M}$，我们所观测到的元素集合是 $\{M_{i,j}\colon (i,j)\in\Omega\}$。秩最小化问题就表述为
$$ \min_{\bm{X}}\ \text{rank}(\bm{X}) \quad \text{s.t. } X_{i,j} = M_{i,j},\ \text{for every }(i,j)\in\Omega $$为方便起见，定义算子 $\mathcal{P}_{\Omega}$ 如下：
$$ [\mathcal{P}_{\Omega}(\bm{X})]_{i,j} = \begin{cases} X_{i,j} & \text{if }(i,j)\in\Omega \\ 0 & \text{otherwise} \end{cases} $$换言之，$\mathcal{P}_{\Omega}$ 将任意矩阵正交投影到以指标集 $\Omega$ 作为支撑集的所有矩阵构成的空间上。
于是，上述问题就可以方便地写为
$$ \min_{\bm{X}}\ \text{rank}(\bm{X}) \quad \text{s.t. } \mathcal{P}_{\Omega}(\bm{X}) = \mathcal{P}_{\Omega}(\bm{M}) $$问题的解就是我们对真实矩阵 $\bm{M}$ 的估计或者近似。
仿射秩最小化
更一般地，我们不满足于普通的矩阵补全，而是以线性变换作为约束条件：
$$ \min_{\bm{X}}\ \text{rank}(\bm{X}) \quad \text{s.t. } \mathcal{A}(\bm{X}) = \bm{b} $$其中 $\mathcal{A}\colon\mathbb{R}^{m\times n}\to\mathbb{R}^p$ 是一个线性映射，向量 $\bm{b}\in\mathbb{R}^p$ 是给定的。这个问题被称为 仿射秩最小化 (affine rank minimization)。
Note
矩阵空间上的线性变换本质上还是向量空间上的线性变换，$\mathcal{A}(\bm{X})$ 可以表述为
$$ \mathcal{A}(\bm{X}) := \begin{bmatrix} \langle\bm{A}_1,\bm{X}\rangle_{\mathrm{F}} \\ \vdots \\ \langle\bm{A}_p,\bm{X}\rangle_{\mathrm{F}} \end{bmatrix} $$其中 $\langle\bm{A},\bm{B}\rangle_{\mathrm{F}} = \text{trace}(\bm{A}'\bm{B})$ 是矩阵的 Frobenius 内积。见 Stack Exchange。
不难证明，$\mathcal{P}_{\Omega}$ 是一个线性变换，因而 $\mathcal{P}_{\Omega}(\bm{X}) = \mathcal{P}_{\Omega}(\bm{M})$ 构成仿射约束的一个特例。
Convex relaxation
遗憾的是，秩最小化问题不是一个凸优化问题，这不是我们所乐见的。原因是，秩函数（关于矩阵所有元素的函数）是非凸的。这无疑使得直接求解上述问题非常困难。我们希望找到作为替代的一个凸优化问题，它正是核范数最小化。
那么，什么是核范数呢？我们首先得了解 奇异值分解 (singular value decomposition, SVD)。任何一个矩阵 $\bm{X}\in\mathbb{R}^{m\times n}$，都可以作如下分解：
$$ \underset{(m\times n)}{\bm{X}} = \underset{(m\times r)}{\bm{U}}\,\underset{(r\times r)}{\bm{\Sigma}}\,\underset{(r\times n)}{\bm{V}'} $$其中 $\bm{U}$ 和 $\bm{V}$ 各自的列是正交的：$\bm{U}'\bm{U}=\bm{I}_r=\bm{V}'\bm{V}$；$\bm{\Sigma}$ 是一个对角矩阵，对角线元素是从大到小排列的 奇异值：$\sigma_1\geq\sigma_2\geq\dots\geq\sigma_r\geq 0$，它们都是非负的；$r = \min\{m,n\}$。
矩阵的奇异值和秩紧密相关，事实上，一个矩阵的秩等于它所有非零（因而严格正）奇异值的个数，即
$$ \text{rank}(\bm{X}) = \sum_{i=1}^r\mathbb{1}\{\sigma_i\ne 0\} $$如果我们用 $\bm{\sigma}$ 来代表所有奇异值构成的向量，那么上式就是 $\bm{\sigma}$ 的 $\ell_0$ 范数。这里离题一下，向量 $\ell_0$ 范数并不是一个真正的范数，而是 pseudo norm，因为它没有齐次性，但实际应用中仍普遍称之为「范数」，见 Wiki。
现在，我们可以正式定义矩阵核范数：
Definition 1.
可以看到，矩阵的核范数等于其奇异值向量的 $\ell_1$ 范数。核范数是一个真正的范数（要证明这一点，特别是要证明它满足三角不等式，见 Stack Exchange 上的回答）。
我们要做的替换就是将目标函数 $\text{rank}(\bm{X})$ 换为 $\lVert\bm{X}\rVert_*$，也就是我们考虑如下问题
$$ \min_{\bm{X}}\ \lVert\bm{X}\rVert_* \quad \text{s.t. } \mathcal{A}(\bm{X}) = \bm{b} $$这是一个凸优化问题，因为范数总是一个凸函数。核范数是秩函数的一个 convex relaxation。
Note
可以类比 Lasso 的思想，想得到一个稀疏的向量（稀疏性以 $\ell_0$ 度量），用的是 $\ell_1$ 范数。现在是矩阵，度量矩阵列向量线性独立程度的正是秩（奇异值向量的 $\ell_0$ 范数），因而用核范数作为优化目标（奇异值向量的 $\ell_1$ 范数）可以得到低秩矩阵。
两种问题的等价性
现在，我们如愿得到了一个凸优化问题，它比原问题更容易求解。但另一方面，这种替换是否有其正当性？换言之，最小化核范数的解是否就是最小化秩函数的解？如果不是，那显然背离了我们的初衷，我们当然希望两种问题给出的解是相同的。一般意义上，两种最小化当然不同，但在一些正则条件下可以证明它们的局部等价性，有诸多研究进行了论证。
Recht et al. (2010) 证明了，在满足特定的 RIP (restricted isometry property) 条件时，仿射秩最小化问题等价于在相同约束下最小化核范数。Candès and Recht (2012) 则不依赖 RIP，证明了有很大的概率最小化核范数能唯一地复原矩阵，只要已知的元素个数不是太少。
在多数矩阵补全问题中，使用核范数最小化问题作为秩最小化问题的替代是恰当的。
求解核范数最小化问题的算法
尽管核范数最小化问题是一个凸问题（但它仍是不可微分的），可以用一般性的凸优化工具求解，但求解速度可能并不十分理想。对此，有一些更迅速的方法，这里简单提及两种。
Recht et al. (2010) 将核范数最小化问题转变为一个 半定规划 (semidefinite programming)，已有成熟的软件包用于解决这类问题（通常使用 primal-dual interior-point methods）。不过，这类方法在维度很高时速度很慢。
Cai et al. (2010) 使用 近端次梯度下降法 (proximal subgradient descent) 求解，此法特别适用于不可微分的凸优化，而且对于高维情形收敛速度也可令人满意。以普通的矩阵补全为例，此文事实上是求解
$$ \min_{\bm{X}}\ \tau\lVert\bm{X}\rVert_* + \frac12\lVert\bm{X}\rVert_{\bm{F}}^2 \quad \text{s.t. } \mathcal{P}_{\Omega}(\bm{X}) = \mathcal{P}_{\Omega}(\bm{M}) $$当 $\tau$ 很大时，该问题的解可以作为最小化核范数问题解的近似。求解该问题是通过一个渐进程序实现的，本质上是梯度下降，这里不做介绍。
其他
Chandrasekaran et al. (2012) 是一篇很好的文章，从几何角度揭示了范数的选择问题。具体到核范数，简单来说就是核范数是秩函数的凸包 （此概念在 之前的文章 中出现过），因而以核范数替代秩函数是 最紧的凸放松 (tightest convex relaxation)。
Gu et al. (2014) 基于 Cai et al. (2010) 的求解程序，研究了 加权核范数最小化问题，并设计了类似的求解程序。
参考
知乎问答.
Yuejie Chi (2018). Lecture Notes.
Yuxin Chen (2020). Lecture Notes.
Cai, Jian-Feng et al. (2010). “A Singular Value Thresholding Algorithm for Matrix Completion.” SIAM Journal on Optimization, 20(4), 1956–1982. doi: 10.1137/080738970.
Candès, Emmanuel and Recht, Benjamin (2012). “Exact matrix completion via convex optimization.” Communications of the ACM, 55(6), 111–119. doi: 10.1145/2184319.2184343.
Chandrasekaran, Venkat et al. (2012). “The Convex Geometry of Linear Inverse Problems.” Foundations of Computational Mathematics, 12(6), 805–849. doi: 10.1007/s10208-012-9135-7.
Gu, Shuhang et al. (2014). “Weighted Nuclear Norm Minimization with Application to Image Denoising.” In: 2014 IEEE Conference on Computer Vision and Pattern Recognition, Columbus, OH, USA. doi: 10.1109/CVPR.2014.366.
Gu, Shuhang et al. (2017). “Weighted Nuclear Norm Minimization and Its Applications to Low Level Vision.” International Journal of Computer Vision, 121(2), 183–208. doi: 10.1007/s11263-016-0930-5.
Recht, Benjamin et al. (2010). “Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization.” SIAM Review, 52(3), 471–501. doi: 10.1137/070697835.
最后修改于 2024-09-04