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

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

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

1. 性质

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

  • $\Vert \begin{array}{c}x\end{array}\Vert \ge 0$
  • $\Vert \begin{array}{c}x\end{array}\Vert =0\iff x=0$
  • $\Vert \begin{array}{c}cx\end{array}\Vert =|c|\Vert \begin{array}{c}x\end{array}\Vert$ ，$c$ 是标量

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

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

• 三角不等式：$x+y\le \Vert \begin{array}{c}x\end{array}\Vert +\Vert \begin{array}{c}y\end{array}\Vert$

  证明

  $$\begin{array}{rl}{\Vert \begin{array}{c}x+y\end{array}\Vert }^2& =(x+y{)}^{\ast }(x+y)\\ & =x^{\ast }x+x^{\ast }y+y^{\ast }x+y^{\ast }y\\ & ={\Vert \begin{array}{c}x\end{array}\Vert }^2+x^{\ast }y+y^{\ast }x+{\Vert \begin{array}{c}y\end{array}\Vert }^2\end{array}$$

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

  $$x^{\ast }y+y^{\ast }x=x^{\ast }y+\overline{x^{\ast }y}=2Re(x^{\ast }y)\le 2|x^{\ast }y|\le 2\Vert \begin{array}{c}x\end{array}\Vert \Vert \begin{array}{c}y\end{array}\Vert$$

  由上述结果，可得：

  $${\Vert \begin{array}{c}x+y\end{array}\Vert }^2\le {\Vert \begin{array}{c}x\end{array}\Vert }^2+2\Vert \begin{array}{c}x\end{array}\Vert \Vert \begin{array}{c}y\end{array}\Vert +{\Vert \begin{array}{c}y\end{array}\Vert }^2=(\Vert \begin{array}{c}x\end{array}\Vert +\Vert \begin{array}{c}y\end{array}\Vert {)}^2$$

  证毕。

2. 极小范数

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

2.1 定理一

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

证明

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

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

$$Ax=A(y+z)=Ay+Az=b$$

这说明 $y$ 也是一个特解。

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

所以 $y-y^{\prime }\in N(A)$ 。

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

合并以上结果，得：

y − y ′ ∈ N ( A ) ∩ C ( A T ) = { 0 } \pmb{y}-\pmb{y}'\in N(\pmb{A})\cap C(\pmb{A}^T)=\{\pmb{0}\} y−y′∈N(A)∩C(AT)={0}

即 $y=y^{\prime }$ 。$y$ 唯一。

证毕。

2.2 定理二

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

证明

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

$${\Vert \begin{array}{c}x\end{array}\Vert }^2={\Vert \begin{array}{c}y\end{array}\Vert }^2+{\Vert \begin{array}{c}z\end{array}\Vert }^2\ge {\Vert \begin{array}{c}y\end{array}\Vert }^2$$

当 $z=0$ 时，上式等号成立。

证毕。

2.3 定理三

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

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

证明

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

推导方法1

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

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

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

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

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

推导方法2，使用拉格朗日乘数法${}^{[4]}$

$$\begin{array}{rl}minimize& \Vert \begin{array}{c}x\end{array}\Vert \\ subjectto& Ax=b\end{array}$$

最小化 $\Vert \begin{array}{c}x\end{array}\Vert$ ，等价于最小化 ${\Vert \begin{array}{c}x\end{array}\Vert }^2=x^{T}x$

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

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

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

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

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

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

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

2.4 计算方法

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

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

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

最佳值：

$$\begin{array}{rl}{\Vert \begin{array}{c}x\end{array}\Vert }^2& =(A^T({AA}^T{)}^{-1}b{)}^T(A^T({AA}^T{)}^{-1}b)\\ & =b^T({AA}^T{)}^{-1}b\\ & =b^T(R^{T}R{)}^{-1}b\end{array}$$

注意：

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