矩阵秩为1的等价（充分必要）条件

Problem1

为什么$\mathbf{W}$是秩$1$的可以等价于$\mathrm{Tr}(\mathbf{W})-{\lambda }_{\max }(\mathbf{W})\le 0$

解答1

这里我们考虑的是一个矩阵 $\mathbf{W}$ 是否是秩1矩阵的问题，等价于判断矩阵 $\mathbf{W}$ 的迹和最大特征值之间的关系。

首先，假设 $\mathbf{W}$ 是秩1矩阵，可以表示为 $\mathbf{W}={\mathbf{uv}}^T$，其中 $\mathbf{u}$ 和 $\mathbf{v}$ 是列向量。那么矩阵 $\mathbf{W}$ 的迹是 $\mathrm{Tr}(\mathbf{W})={\mathbf{u}}^T\mathbf{v}$，最大特征值是 ${\lambda }_{\max }(\mathbf{W})=\Vert \mathbf{W}{\Vert }_2=\Vert {\mathbf{uv}}^T{\Vert }_2=\Vert \mathbf{u}{\Vert }_2\Vert \mathbf{v}{\Vert }_2$。由于矩阵的二范数等于其最大特征值，所以 $\Vert \mathbf{W}{\Vert }_2=\Vert {\mathbf{uv}}^T{\Vert }_2=\Vert \mathbf{u}{\Vert }_2\Vert \mathbf{v}{\Vert }_2=\Vert \mathbf{u}{\Vert }_2\Vert \mathbf{v}{\Vert }_2$。

根据柯西-施瓦茨不等式，${\mathbf{u}}^T\mathbf{v}\le \Vert \mathbf{u}{\Vert }_2\Vert \mathbf{v}{\Vert }_2$，所以$\mathrm{Tr}(\mathbf{W})={\mathbf{u}}^T\mathbf{v}\le \Vert \mathbf{u}{\Vert }_2\Vert \mathbf{v}{\Vert }_2={\lambda }_{\max }(\mathbf{W})$，即 $\mathrm{Tr}(\mathbf{W})-{\lambda }_{\max }(\mathbf{W})\le 0$。

反过来，如果 $\mathrm{Tr}(\mathbf{W})-{\lambda }_{\max }(\mathbf{W})\le 0$则根据柯西-施瓦茨不等式，存在某个单位向量 $\mathbf{u}$ 和向量 $\mathbf{v}$ 使得 ${\mathbf{u}}^T\mathbf{v}=\mathrm{Tr}(\mathbf{W})$ 和 $\Vert \mathbf{u}{\Vert }_2\Vert \mathbf{v}{\Vert }_2={\lambda }_{\max }(\mathbf{W})$ 成立。因此，$\mathbf{W}={\mathbf{uv}}^T$ 是秩1矩阵。

综上所述，$\mathbf{W}$ 是秩1矩阵的充要条件是 $\mathrm{Tr}(\mathbf{W})-{\lambda }_{\max }(\mathbf{W})\le 0$。

Problem2

为什么秩$1$矩阵$\mathbf{W}$如果$\mathbf{W}⪰0$, 必有$\mathrm{Tr}(\mathbf{W})-{\lambda }_{\max }(\mathbf{W})\ge 0$

为什么秩一矩阵的二范数等于其最大特征值

如果给定矩阵 $\mathbf{W}$ 是由列向量 $\mathbf{u}$ 和 $\mathbf{v}$ 的外积形成的，即 $\mathbf{W}={\mathbf{uv}}^T$，那么它的最大特征值可以通过以下方式求解：

由于 $\mathbf{W}={\mathbf{uv}}^T$，所以 $\mathbf{W}$ 的特征值中至少有一个是零，因为它是秩1矩阵。

另外，$\mathbf{W}$ 的非零特征值可以通过求解方程 $\mathbf{Wx}=\lambda \mathbf{x}$ 获得，其中 $\mathbf{x}$ 是非零特征值对应的特征向量，$\lambda$ 是非零特征值。

将 $\mathbf{W}={\mathbf{uv}}^T$ 代入上述方程，得到：

$${\mathbf{uv}}^T\mathbf{x}=\lambda \mathbf{x}$$

由于 ${\mathbf{v}}^T\mathbf{x}$ 是一个标量，记为 $c$，那么上式可以重写为：

$$\mathbf{u}c=\lambda \mathbf{x}$$

这表明非零特征向量 $\mathbf{x}$ 与列向量 $\mathbf{u}$ 共线。因此，非零特征向量可以取 $\mathbf{u}$ 的任意倍数。考虑到特征向量的归一化要求，我们可以假设 $\Vert \mathbf{x}{\Vert }_2=1$，因此有 $c=\Vert \mathbf{u}{\Vert }_2$。

因此，非零特征值 $\lambda$ 就是 $\Vert \mathbf{u}{\Vert }_2$，并且对应的特征向量是 $\mathbf{v}$。所以最大的非零特征值是 ${\lambda }_{\max }=\Vert \mathbf{u}{\Vert }_2$。

综上所述，对于矩阵 $\mathbf{W}={\mathbf{uv}}^T$，最大的非零特征值是列向量 $\mathbf{u}$ 的二范数。

---

当我们说矩阵的二范数等于其最大特征值时，我们指的是矩阵的谱范数（或者叫二范数）等于其最大特征值的模。对于实对称矩阵，谱范数即为最大特征值的绝对值。

对于矩阵 ($\mathbf{W}={\mathbf{uv}}^T$)，我们可以按照以下步骤解释这个等式：

1. 首先，($\Vert \mathbf{W}{\Vert }_2$) 表示矩阵 ($\mathbf{W}$) 的谱范数，即 ($\Vert \mathbf{W}{\Vert }_2={\lambda }_{\max }(\mathbf{W})$)，其中 (${\lambda }_{\max }(\mathbf{W})$) 是矩阵 ($\mathbf{W}$) 的最大特征值的模。

2. 对于矩阵 (${\mathbf{uv}}^T$)，我们知道它的特征值是 ($\mathbf{u}$) 的二范数与 ($\mathbf{v}$) 的二范数之积。这意味着 ($\Vert {\mathbf{uv}}^T{\Vert }_2=\Vert \mathbf{u}{\Vert }_2\Vert \mathbf{v}{\Vert }_2$)。

3. 由于 ($\mathbf{W}={\mathbf{uv}}^T$)，所以 ($\Vert \mathbf{W}{\Vert }_2=\Vert {\mathbf{uv}}^T{\Vert }_2$)。

4. 将第2步的结果代入第3步，我们得到 ($\Vert \mathbf{W}{\Vert }_2=\Vert \mathbf{u}{\Vert }_2\Vert \mathbf{v}{\Vert }_2$)。

因此，这个等式说明了矩阵 ($\mathbf{W}$) 的谱范数等于列向量 ($\mathbf{u}$) 的二范数与列向量 ($\mathbf{v}$) 的二范数的乘积。

---

当我们考虑矩阵的二范数时，我们实际上在寻找一个矩阵变换后的向量的长度的最大值。

对于矩阵 ($\mathbf{W}={\mathbf{uv}}^T$)，我们要找到 ($\mathbf{Wx}$) 的最大范数，其中 ($\mathbf{x}$) 是一个单位向量。

由于 ($\mathbf{W}={\mathbf{uv}}^T$)，我们有

[$$\mathbf{Wx}=({\mathbf{uv}}^T)\mathbf{x}=\mathbf{u}({\mathbf{v}}^T\mathbf{x})$$]

注意到 (${\mathbf{v}}^T\mathbf{x}$) 是一个标量，所以我们可以将其记为 ($c$)，这样我们有

[
$$\mathbf{Wx}=\mathbf{u}c$$
]

现在，我们要找到使 ($\Vert \mathbf{Wx}{\Vert }_2$) 最大的单位向量 ($\mathbf{x}$)。因为 ($\Vert \mathbf{Wx}{\Vert }_2=\Vert \mathbf{u}c{\Vert }_2$)，我们实际上在寻找使 ($\Vert \mathbf{u}c{\Vert }_2$) 最大的单位向量 ($\mathbf{x}$)。

注意到 ($\Vert \mathbf{u}c{\Vert }_2=|c|\Vert \mathbf{u}{\Vert }_2$)，所以要使 ($\Vert \mathbf{Wx}{\Vert }_2$) 最大，只需最大化 ($\Vert \mathbf{u}{\Vert }_2$)。

因此，当我们取单位向量 ($\mathbf{x}$) 与向量 ($\mathbf{v}$) 的方向一致时，矩阵 ($\mathbf{Wx}$) 的范数达到最大值，此时最大特征值就等于 ($\Vert \mathbf{u}{\Vert }_2$)，即 ($\Vert \mathbf{W}{\Vert }_2=\Vert \mathbf{u}{\Vert }_2\Vert \mathbf{v}{\Vert }_2$)。

矩阵函数的subgradient

在凸优化中，当我们考虑一个非光滑凸函数的优化问题时，我们通常使用 subgradient 来描述该函数的次梯度。

对于一个凸函数 ($f:{\mathbb{R}}^n\to \mathbb{R}$)，在点 ($\mathbf{x}$) 处的 subgradient 是一个向量或向量集合 ($\mathbf{g}$)，满足对于任意点 ($\mathbf{y}$) ，都有：

[$f(\mathbf{y})\ge f(\mathbf{x})+{\mathbf{g}}^T(\mathbf{y}-\mathbf{x})$]

换句话说，subgradient 是一个在给定点处使得函数值可以被一个一次函数下界的向量。对于光滑凸函数，它在每个点处都有唯一的梯度，但是对于非光滑凸函数，它在某些点可能没有梯度，或者有多个梯度，此时我们使用 subgradient 来扩展梯度的概念。

举例来说，对于绝对值函数 ($f(x)=|x|$)，在 ($x=0$) 处没有定义梯度，但是存在 subgradient，即 ($-1\le g\le 1$)。