范数、稀疏与过拟合合集（1）范数的定义与常用范数介绍
范数、稀疏与过拟合合集（2）有监督模型下的过拟合与正则化加入后缓解过拟合的原理
范数、稀疏与过拟合合集（3）范数与稀疏化的原理、L0L1L2范数的比较以及数学分析
范数、稀疏与过拟合合集（4）L2范数对condition number较差情况的缓解
范数、稀疏与过拟合合集（5）Dropout原理，操作实现，为什么可以缓解过拟合，使用中的技巧

1、范数简介

范数是具有“长度”概念的函数。在向量空间内，为所有的向量的赋予非零的增长度或者大小。不同的范数，所求的向量的长度或者大小是不同的。

1.1 范数分类

• 向量范数
• 矩阵范数：

1.2 向量范数的定义

假设有一个函数$f$

$f$完成的映射为${\mathbb{R}}^n\to \mathbb{R}$

非负性：对于$\forall \mathbf{x}\in {\mathbb{R}}^n$，满足$f(\mathbf{x})\ge 0$，等号当且仅当$\mathbf{x}=0$时成立

齐次性：对于$\forall x\in {\mathbb{R}}^n,\forall \alpha \in \mathbb{R}$，满足$f(\alpha \mathbf{x})=|\alpha |\cdot f(\mathbf{x})$

三角不等式：$f(x+y)\le f(x)+f(y)$

则称$f$为${\mathbb{R}}^n$上的（向量）范数，通常记为$||\cdot ||$

1.3 矩阵范数的定义

假设有一个函数$f$

$f$完成的映射为${\mathbb{R}}^{n\times n}\to \mathbb{R}$

非负性：对于$\forall \mathbf{A}\in {\mathbb{R}}^{n\times n}$，满足$f(\mathbf{A})\ge 0$，等号当且仅当$\mathbf{A}=0$时成立

齐次性：对于$\forall A\in {\mathbb{R}}^{n\times n},\forall \alpha \in \mathbb{R}$，满足$f(\alpha \mathbf{A})=|\alpha |\cdot f(\mathbf{A})$

三角不等式：$f(\mathbf{A}+\mathbf{B})\le f(\mathbf{A})+f(\mathbf{B})$

三角不等式：$f(\mathbf{A}\mathbf{B})\le f(\mathbf{A})f(\mathbf{B})$

则称$f$为${\mathbb{R}}^{n\times n}$上的（矩阵）范数，通常记为$||\cdot ||$

2、常用向量范数

2.1 $L_p$范数：

一般将任意向量$\mathbf{x}$的$L_p$范数定义为
$$\Vert \mathbf{x}{\Vert }_p=\sqrt[p]{\sum _i{\left|x_i\right|}^p}$$

2.2 $L_0$范数：向量$\mathbf{x}$中非零元素的个数

$$\Vert \mathbf{x}{\Vert }_0=\sqrt[0]{\sum _i{\left|x_i\right|}^0}$$

等同于如下计算公式
$$\Vert \mathbf{x}{\Vert }_0=\#\left(i\mid x_i\ne 0\right)$$
在诸多机器学习模型中，比如压缩感知 (compressive sensing)，我们很多时候希望最小化向量的 $L_0$范数。一个标准的$L_0$范数优化问题往往可以写成如下形式：
min ⁡ ∥ x ∥ 0  s.t.  A x = b

$$\begin{array}{c} \min \|\boldsymbol{x}\|_{0} \\ \text { s.t. } A \boldsymbol{x}=\boldsymbol{b} \end{array}$$ min∥x∥0​ s.t. Ax=b​
然而，由于$L_0$范数仅仅表示向量中非0元素的个数，因此，这个优化模型在数学上被认为是一个NP-hard问题，即直接求解它很复杂、也不可能找到解。

需要注意的是，正是由于该类优化问题难以求解，因此，压缩感知模型是将$L_0$范数最小化问题转换成$L_1$范数最小化问题。

2.2 $L_1$范数：向量中所有元素绝对值之和

也称为稀疏规则化算子（Lasso regularization)，是$L_0$范数的最优凸近似。
$$\Vert \mathbf{x}{\Vert }_1=\sum _i\left|x_i\right|$$

一个$L_1$范数优化问题为
min ⁡ ∥ x ∥ 1  s.t.  A x = b

$$\begin{array}{c} \min \|\boldsymbol{x}\|_{1} \\ \text { s.t. } A \boldsymbol{x}=\boldsymbol{b} \end{array}$$ min∥x∥1​ s.t. Ax=b​
这个问题相比于$L_0$范数优化问题更容易求解，借助现有凸优化算法（线性规划或是非线性规划），就能够找到我们想要的可行解。鉴于此，依赖于$L_1$范数优化问题的机器学习模型如压缩感知就能够进行求解了。

2.3 $L_2$范数：向量（或矩阵）的元素平方和开根号

$L_2$范数又称Euclidean范数或者Frobenius范数，也表示向量模长，即
$$\Vert \mathbf{x}{\Vert }_2=\sqrt{\sum _i{x}_i^2}$$
$L_2$范数的优化模型如下：
min ⁡ ∥ x ∥ 2  s.t.  A x = b

$$\begin{array}{c} \min \|\boldsymbol{x}\|_{2} \\ \text { s.t. } A \boldsymbol{x}=\boldsymbol{b} \end{array}$$ min∥x∥2​ s.t. Ax=b​

2.4 $L_{\infty }$范数：向量元素绝对值中最大值

$$\underset{k\to \infty }{\lim }{\left(\sum _{i=1}^n{\left|p_i-q_i\right|}^k\right)}^{1/k}$$

3、常用矩阵范数

对于矩阵$A\in {\mathbb{R}}^{m\times n}$

3.1 1-范数：列和范数

即所有矩阵列向量绝对值之和的最大值
$$\Vert A{\Vert }_1=\underset{j}{\max }\sum _{i=1}^m\left|a_{i,j}\right|$$

3.2 2-范数：谱范数

$$\Vert A{\Vert }_2=\sqrt{{\lambda }_1}$$

${\lambda }_1$表示$A^{T}A$的最大特征值的开平方

]

3.3 $\infty$-范数：行和范数

$$\Vert A{\Vert }_{\infty }=\underset{i}{\max }\sum _{j=1}^m\left|a_{i,j}\right|$$

即所有矩阵行向量绝对值之和的最大值

3.4 F-范数：Frobenius范数

$$\Vert A{\Vert }_F={\left(\sum _{i=1}^m\sum _{j=1}^n{a}_{i,j}^2\right)}^{\frac{1}{2}}$$

即矩阵元素绝对值的平方和再开平方

LAST、参考文献

各种范数的解释_u011484045的专栏-CSDN博客
如何通俗易懂地解释「范数」？ - 知乎
范数_weixin_34233618的博客-CSDN博客
范数、L1范数和L2范数的基本概念_lioncv的专栏-CSDN博客_l1范数的定义
过拟合以及正则化（L0,L1,L2范数）_yeal-CSDN博客
谱范数的理解与论述_MathThinker的博客-CSDN博客
向量范数与矩阵范数 - 知乎
L1范数和L2范数的区别 - 程序员大本营
L1范数与L2范数的区别 - 知乎
范数、L1范数和L2范数的基本概念_lioncv的专栏-CSDN博客_l1范数的定义
机器学习中的范数规则化之（一）L0、L1与L2范数_bitcarmanlee的博客-CSDN博客
L1范数与L2范数的区别_不二的博客-CSDN博客_l2范数