Skip to content

Latest commit

 

History

History
194 lines (104 loc) · 7.42 KB

norm.md

File metadata and controls

194 lines (104 loc) · 7.42 KB

向量范数

《机器学习数学基础》第1章1.5.3节介绍了向量范数的基本定义。

本文在上述基础上，介绍向量范数的有关性质。

**注意：**以下均在欧几里得空间讨论，即欧氏范数。

1. 性质

  • 实（或复）向量 $\pmb{x}$ ，范数 $\begin{Vmatrix}\pmb{x}\end{Vmatrix}$ 满足：

    • $\begin{Vmatrix}\pmb{x}\end{Vmatrix}\ge0$
    • $\begin{Vmatrix}\pmb{x}\end{Vmatrix}=0 \Leftrightarrow \pmb{x}=\pmb{0}$
    • $\begin{Vmatrix}c\pmb{x}\end{Vmatrix}=|c|\begin{Vmatrix}\pmb{x}\end{Vmatrix}$ ，$c$ 是标量

  • 设 $\pmb{x,y}\in\mathbb{C}^n$ ，根据施瓦茨不等式：$|\pmb{x}^*\pmb{y}|\le\begin{Vmatrix}\pmb{x}\end{Vmatrix}\begin{Vmatrix}\pmb{y}\end{Vmatrix}$ 。

    若 $n=1$ ，则上式退化为 $|\overline{x}y|\le|x||y|$ ，其中 $x,y\in\mathbb{C}$ 。因为 $|\overline{x}|=|x|$ ，所以 $|\overline{x}y|\le|\overline{x}||y|$

  • 三角不等式：$\pmb{x}+\pmb{y}\le \begin{Vmatrix}\pmb{x}\end{Vmatrix}+\begin{Vmatrix}\pmb{y}\end{Vmatrix}$

    证明

    $$ \begin{split}\begin{Vmatrix}\pmb{x}+\pmb{y}\end{Vmatrix}^2 &= (\pmb{x}+\pmb{y})^(\pmb{x}+\pmb{y})\ &= \pmb{x}^\pmb{x}+\pmb{x}^\pmb{y}+\pmb{y}^\pmb{x}+\pmb{y}^\pmb{y}\&=\begin{Vmatrix}\pmb{x}\end{Vmatrix}^2+\pmb{x}^\pmb{y}+\pmb{y}^*\pmb{x}+\begin{Vmatrix}\pmb{y}\end{Vmatrix}^2\end{split} $$

    根据复数的性质和施瓦茨不等式：

    $$ \pmb{x}^\pmb{y}+\pmb{y}^\pmb{x}=\pmb{x}^\pmb{y}+\overline{\pmb{x}^\pmb{y}}=2Re(\pmb{x}^\pmb{y})\le 2|\pmb{x}^\pmb{y}|\le2\begin{Vmatrix}\pmb{x}\end{Vmatrix}\begin{Vmatrix}\pmb{y}\end{Vmatrix} $$

    由上述结果，可得：

    $$ \begin{Vmatrix}\pmb{x}+\pmb{y}\end{Vmatrix}^2 \le \begin{Vmatrix}\pmb{x}\end{Vmatrix}^2+2\begin{Vmatrix}\pmb{x}\end{Vmatrix}\begin{Vmatrix}\pmb{y}\end{Vmatrix}+\begin{Vmatrix}\pmb{y}\end{Vmatrix}^2=(\begin{Vmatrix}\pmb{x}\end{Vmatrix}+\begin{Vmatrix}\pmb{y}\end{Vmatrix})^2 $$

    证毕。

2. 极小范数

$m\times n$ 的矩阵 $\pmb{A}$ ，列空间 $C(\pmb{A})={\pmb{Ax}|\pmb{x}\in\mathbb{R}^n}$ （ $C(\pmb{A})$ 是 $\mathbb{R}^m$ 的一个子空间），对任一 $\pmb{b}\in C(\pmb{A})$ ，线性方程组 $\pmb{Ax}=\pmb{b}$ 有解。在解集合中，有一个特解，在 $\pmb{A}$ 的行空间，即 $\pmb{A}^T$ 的列空间 $C(\pmb{A}^T)$ ，并且具有最小的 $l_2$ 范数，称为极小范数解（minimum norm solution）$^{[1]}$，记作 $\pmb{x}^+$ ，即：$\pmb{x}^+\in C(\pmb{A}^T)$ 使得 $\pmb{Ax}^+=\pmb{b}$

2.1 定理一

若 $\pmb{b}\in C(\pmb{A})$ ，则存在唯一的 $\pmb{y}\in C(\pmb{A}^T)$ 使得 $\pmb{Ay}=\pmb{b}$ 。

证明

设特解 $\pmb{x}\in \mathbb{R}^n$ 使得 $\pmb{Ax}=\pmb{b}$ 。

在 $\mathbb{R}^n$ 中，$\pmb{A}$ 的列空间 $C(\pmb{A}^T)$ 是零空间 $N(\pmb{A})$ 的正交补（参考：矩阵基本子空间$^{[2]}$）。则 $\pmb{x}$ 可以分解为 $\pmb{x}=\pmb{y}+\pmb{z}$ ，其中 $\pmb{y}\in C(\pmb{A}^T), \pmb{z}\in N(\pmb{A})$ ，得：

$$ \pmb{Ax}=\pmb{A}(\pmb{y}+\pmb{z})=\pmb{Ay}+\pmb{Az}=\pmb{b} $$

这说明 $\pmb{y}$ 也是一个特解。

设 $\pmb{y},\pmb{y}'\in C(\pmb{A}^T)$ 使得 $\pmb{Ay}=\pmb{b},\pmb{Ay}'=\pmb{b}$ 。两式子相减：$\pmb{A}(\pmb{y}-\pmb{y}')=\pmb{0}$

所以 $\pmb{y}-\pmb{y}'\in N(\pmb{A})$ 。

又因为 $\pmb{y}-\pmb{y}'\in C(\pmb{A}^T)$ ，

合并以上结果，得：

$$ \pmb{y}-\pmb{y}'\in N(\pmb{A})\cap C(\pmb{A}^T)={\pmb{0}} $$

即 $\pmb{y}=\pmb{y}'$ 。$\pmb{y}$ 唯一。

证毕。

2.2 定理二

若 $\pmb{b}\in C(\pmb{A})$ 且 $\pmb{y}\in {\pmb{x}|\pmb{Ax}=\pmb{b}}$ 具有最小 $l_2$ 范数，则 $\pmb{y}\in C(\pmb{A}^T)$ 。

证明

由定理一，任意特解可以表示为 $\pmb{x}=\pmb{y}+\pmb{z}$ ，且 $\pmb{y}$ 唯一存在。因为 $\pmb{y}\bot\pmb{z}$ ，则：

$$ \begin{Vmatrix}\pmb{x}\end{Vmatrix}^2=\begin{Vmatrix}\pmb{y}\end{Vmatrix}^2+\begin{Vmatrix}\pmb{z}\end{Vmatrix}^2\ge\begin{Vmatrix}\pmb{y}\end{Vmatrix}^2 $$

当 $\pmb{z}=\pmb{0}$ 时，上式等号成立。

证毕。

2.3 定理三

若 $\rank \pmb{A}=m$ ，即 $\pmb{A}$ 的列向量线性无关，则 $\pmb{Ax}=\pmb{b}$ 必有解，且极小范数解为：

$$ \pmb{x}^+=\pmb{A}^T(\pmb{AA}^T)^{-1}\pmb{b} $$

证明

因为 $\rank \pmb{A}=m$ ，则 $\dim C(\pmb{A})=m$ ，列空间 $C(\pmb{A})$ 充满 $\mathbb{R}^m$ ，所以任一 $\pmb{b}\in\mathbb{R}^m$ 使 $\pmb{Ax}=\pmb{b}$ 有解。

推导方法1

因为 $\pmb{A}$ 的列向量线性无关，所以 $\pmb{x}^+\in C(\pmb{A}^T)$ 可唯一表示为列向量的线性组合，即存在唯一的 $\pmb{c}$ 使得 $\pmb{x}^+=\pmb{A}^T\pmb{c}$ 。代入 $\pmb{Ax}^+=\pmb{b}$ ，得：

$$ \pmb{AA}^T\pmb{c}=\pmb{b} $$

因为 $\rank(\pmb{AA}^T)=\rank(\pmb{A})=m$ ，所以 $\pmb{AA}^T$ 可逆$^{[5]}$。

故：$\pmb{c}=(\pmb{AA}^T)^{-1}\pmb{b}$

解得：$\pmb{x}^+=\pmb{A}^T(\pmb{AA}^T)^{-1}\pmb{b}$

推导方法2，使用拉格朗日乘数法$^{[4]}$ $$ \begin{split}minimize \quad &\begin{Vmatrix}\pmb{x}\end{Vmatrix}\subject\quad to \quad& \pmb{Ax}=\pmb{b}\end{split} $$

最小化 $\begin{Vmatrix}\pmb{x}\end{Vmatrix}$ ，等价于最小化 $\begin{Vmatrix}\pmb{x}\end{Vmatrix}^2=\pmb{x}^T\pmb{x}$

拉格朗日函数：$L(\pmb{x},\pmb{\lambda})=\pmb{x}^T\pmb{x}+\pmb{\lambda}^T(\pmb{Ax}-\pmb{b})$

其中 $\pmb{\lambda}$ 是 $m$ 维拉格朗日乘数向量。计算：

$$ \begin{split}\frac{\partial L}{\partial\pmb{x}}&=2\pmb{x}+\pmb{A}^T\pmb{\lambda}\\frac{\partial L}{\partial\pmb{\lambda}}&=\pmb{Ax}-\pmb{b}\end{split} $$

令上述两式等于零，得到最优化条件式。得：$\pmb{x}^+=-\frac{1}{2}\pmb{A}^T\pmb{\lambda}$ ，代入 $\pmb{Ax}^+=\pmb{b}$ ，得：

$$ -\frac{1}{2}\pmb{AA}^T\pmb{\lambda}=\pmb{b} $$

解得：$\pmb{\lambda}=-2(\pmb{AA}^T)^{-1}\pmb{b}$

所以：$\pmb{x}^+=\pmb{A}^T(\pmb{AA}^T)^{-1}\pmb{b}$

2.4 计算方法

计算 $\pmb{x}^+$ ，可以使用QR分解$^{[5]}$ 。

设 $\pmb{A}^T=\pmb{QR}$ ，其中 $\pmb{Q}$ 是 $n\times m$ 矩阵，且 $\pmb{Q}^T\pmb{Q}=\pmb{I}_m$ ，$\pmb{R}$ 是 $m$ 阶上三角矩阵。

$$ \begin{split}\pmb{x}^+ &= \pmb{A}^T(\pmb{AA}^T)^{-1}\pmb{b}\ &= \pmb{QR}(\pmb{R}^T\pmb{Q}^T\pmb{QR})^{-1}\pmb{b}\&=\pmb{QR}(\pmb{R}^T\pmb{R})^{-1}\pmb{b}\&=\pmb{QRR}^{-1}(\pmb{R}^T)^{-1}\pmb{b}\&=\pmb{Q}(\pmb{R}^T)^{-1}\pmb{b}\end{split} $$

最佳值：

$$ \begin{split}\begin{Vmatrix}\pmb{x}\end{Vmatrix}^2 &= (\pmb{A}^T(\pmb{AA}^T)^{-1}\pmb{b})^T(\pmb{A}^T(\pmb{AA}^T)^{-1}\pmb{b})\&=\pmb{b}^T(\pmb{AA}^T)^{-1}\pmb{b}\&=\pmb{b}^T(\pmb{R}^T\pmb{R})^{-1}\pmb{b}\end{split} $$

注意：

  • 在上述计算中，使用了矩阵求导等相关计算，请参阅《机器学习数学基础》第4章“向量分析”有关内容，书中的附录中也附有各种计算公式。
  • 定理三，仅限于 $\pmb{A}$ 的列向量线性无关。若列向量线性相关，即 $rank\pmb{A}\le m$ ，则 $\pmb{AA}^T$ 不可逆。此时仍有极小范数解，表示为 $\pmb{x}^+=\pmb{A}^+\pmb{b}$ ，其中 $\pmb{A}^+$ 称为 $\pmb{A}$ 的伪逆矩阵（或广义逆矩阵）$^{[6]}$。

参考文献

[1]. 极小范数解[DB/OL]. https://ccjou.wordpress.com/2014/05/21/極小範數解/

[2]. 矩阵基本子空间[DB/OL]. https://lqlab.readthedocs.io/en/latest/math4ML/linearalgebra/basetheory.html

[4]. Lagrange multiplier[DB/OL]. https://en.wikipedia.org/wiki/Lagrange_multiplier

[5]. 齐伟. 机器学习数学基础[M]. 北京：电子工业出版社, 2023年1月第3次印刷

[6]. 广义逆矩阵[DB/OL]. https://zh.wikipedia.org/wiki/广义逆矩阵