向量范数#

《机器学习数学基础》第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{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} \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 定理三#

\(\text{rank} \pmb{A}=m\) ,即 \(\pmb{A}\) 的列向量线性无关,则 \(\pmb{Ax}=\pmb{b}\) 必有解,且极小范数解为:

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

证明

因为 \(\text{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} \]

因为 \(\text{rank}(\pmb{AA}^T)=\text{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} \begin{split}minimize \quad &\begin{Vmatrix}\pmb{x}\end{Vmatrix}\\subject\quad to \quad& \pmb{Ax}=\pmb{b}\end{split} \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} \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} \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} \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} \end{split}\]

最佳值:

\[\begin{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} \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/广义逆矩阵