怎么选择使用l0，l1，l2范数

问题描述

精选答案

浅谈L0,L1,L2范数及其应用

在线性代数，函数分析等数学分支中，范数（Norm）是一个函数，其赋予某个向量空间（或矩阵）中的每个向量以长度或大小。对于零向量，另其长度为零。直观的说，向量或矩阵的范数越大，则我们可以说这个向量或矩阵也就越大。有时范数有很多更为常见的叫法，如绝对值其实便是一维向量空间中实数或复数的范数，而Euclidean距离也是一种范数。

范数的一般化定义：设p≥1的实数，p-norm定义为：

||x||p:=(∑i=1n∣∣xi∣∣p)1p(1)

此处，当p=1时，我们称之为taxicab Norm，也叫Manhattan Norm。其来源是曼哈顿的出租车司机在四四方方的曼哈顿街道中从一点到另一点所需要走过的距离。也即我们所要讨论的l1范数。其表示某个向量中所有元素绝对值的和。 而当p=2时，则是我们最为常见的Euclidean norm。也称为Euclidean distance。也即我们要讨论的l2范数。 而当p=0时，因其不再满足三角不等性，严格的说此时p已不算是范数了，但很多人仍然称之为l0范数。 这三个范数有很多非常有意思的特征，尤其是在机器学习中的正则化（Regularization）以及稀疏编码（Sparse Coding）有非常有趣的应用。

下图给出了一个Lp球的形状随着P的减少的可视化图。

1- L0 范数

虽然L0严格说不属于范数，我们可以采用等式1来给出l0-norm得定义：

||x||0:=0∑i=0nx0i‾‾‾‾‾‾⎷(2)

上面的公式仍然让人不是很明白，0的指数和平方根严格意义上是受限条件下才成立的。因此在实际应用中，多数人给出下面的替代定义：

||x||0=#(i)withxi≠0(3)

其表示向量中所有非零元素的个数。正是L0范数的这个属性，使得其非常适合机器学习中稀疏编码，特征选择的应用。通过最小化L0范数，来寻找最少最优的稀疏特征项。但不幸的是，L0范数的最小化问题在实际应用中是NP难问题。因此很多情况下，L0优化问题就会被relaxe为更高维度的范数问题，如L1范数，L2范数最小化问题。

2- L1 范数

对于向量X，其L1范数的定义如下：

||x||1:=∑i=1n∣∣xi∣∣(4)

其应用范围非常的广泛。如在计算机视觉中的Sum of Absolute Differents，Mean Absolute Error，都是利用L1范式的定义。

L1最优化问题的解是稀疏性的，其倾向于选择很少的一些非常大的值和很多的insignificant的小值。而L2最优化则更多的非常少的特别大的值，却又很多相对小的值，但其仍然对最优化解有significant的贡献。但从最优化问题解的平滑性来看，L1范数的最优解相对于L2范数要少，但其往往是最优解，而L2的解很多，但更多的倾向于某种局部最优解。

但由于L1范数并没有平滑的函数表示，起初L1最优化问题解决起来非常困难，但随着计算机技术的到来，利用很多凸优化算法使得L1最优化成为可能。

3- L2 范数

当然范数中最常见，也最著名的非L2范数莫属。其应用也几乎包括科学和工程的各个领域。定义公式如下：

||x||2:=∑i=1nx2i‾‾‾‾‾‾⎷(5)

也Euclidean Norm，如果用于计算两个向量之间的不同，即是Euclidean Distance.

欧几里德范数的最优化问题可以用如下公式表述：

min||x||2subjecttoAx=b(6)

借助拉格朗日乘子，我们便可以解决该最优化问题。由L2衍生，我们还可以定义无限norm，即l-infinity norm：

||x||∞:=∞∑i=1nx∞i‾‾‾‾‾‾⎷(7)

一眼看上去上面的公式还是有点tricky的。我们通过一个简单的数学变换，假设X_j是向量中最大的元素，则根据无限大的特性，我们可以得到：

x∞j>>x∞i∨j≠i

则可知

∑i=1nx∞i=x∞j

则根据公式（7）的定义，我们可以得到：

||x||∞=∞∑i=1nx∞i‾‾‾‾‾‾⎷=∞x∞j‾‾‾√=∣∣xj∣∣

因此我们便可以说l-infinity norm是X向量中最大元素的长度。

||x||∞=max(∣∣xj∣∣)(8)