范数是度量向量/矩阵/张量大小的方法
范数定义了向量到实数的某种映射,并且满足正定性、齐次性、三角不等式
∥v∥≥0\| \bold v \| \geq 0∥v∥≥0
∥cv∥=∣c∣∥v∥\|c \bold v \| = |c| \| \bold v \|∥cv∥=∣c∣∥v∥
∥v+w∥≤∥v∥+∥w∥\left\| {\bold v + \bold w} \right\| \le \left\| \bold v \right\| + \left\| \bold w \right\|∥v+w∥≤∥v∥+∥w∥
向量范数
Hölder范数/ p范数/ Lp范数: 为x向量各个元素绝对值p次方之和的1/p次方∥v∥p=(∣v1∣p+⋯+∣vn∣p)1/p{\left\|\bold v \right\|_p} = {({\left| {{v_1}} \right|^p} + \cdots + {\left| {{v_n}} \right|^p})^{1/p}}∥v∥p=(∣v1∣p+⋯+∣vn∣p)1/p
常用的Lp范数(p一般取1到无穷大):
ℓ1\ell ^1ℓ1范数 / 曼哈顿范数:∥v∥1=∣v1∣+⋯+∣vn∣{\left\| \bold v \right\|_1} = \left| {{v_1}} \right| + \cdots + \left| {{v_n}} \right|∥v∥1=∣v1∣+⋯+∣vn∣
ℓ1\ell ^1ℓ1范数较小的向量,表现为稀疏的,即大部分元素为零ℓ2\ell ^2ℓ2范数 / 欧式范数:∥v∥2=∣v1∣2+⋯+∣vn∣2{\left\| \bold v \right\|_2} = \sqrt {{{\left| {{v_1}} \right|}^2} + \cdots + {{\left| {{v_n}} \right|}^2}}∥v∥2=∣v1∣2+⋯+∣vn∣2
ℓ2\ell ^2ℓ2范数较小的向量,包含很多较小分量(这是因为一个大分量平方后比重很大),最小化ℓ2\ell ^2ℓ2范数类似于最小二乘法ℓ∞\ell ^\inftyℓ∞范数:∥v∥∞=max∣vi∣{\left\| \bold v \right\|_\infty } = \max \left| {{v_i}} \right|∥v∥∞=max∣vi∣
类比可得ℓ0\ell ^0ℓ0范数∥v∥0{\left\| \bold v \right\|_0}∥v∥0 = v\bold vv中非零分量的个数,可以描述稀疏性
但是注意,这不是一个真正的范数,因为它违反了范数规则(∥2v∥0{\left\| 2 \bold v \right\|_0}∥2v∥0=∥v∥0{\left\| \bold v \right\|_0}∥v∥0)
向量范数的几何意义
在R2\mathbf R^2R2空间中,在不同Lp范数下,满足范数=1的向量集合如图
(向量起点在原点,这里仅画出了向量的终点)
如图,满足∥v∥1=∣v1∣+∣v2∣=1{\left\|\bold v \right\|_1} = \left| {{v_1}} \right| + \left| {{v_2}} \right| = 1∥v∥1=∣v1∣+∣v2∣=1的向量集合构成一个菱形;满足∥v∥2=∣v1∣2+∣v2∣2=1{\left\| \bold v \right\|_2} = \sqrt {{{\left| {{v_1}} \right|}^2} + {{\left| {{v_2}} \right|}^2}} = 1∥v∥2=∣v1∣2+∣v2∣2=1的向量集合构成一个圆;
从左到右,随着p的增大,该图像不断“向外膨胀”;
另外注意,上图中只有p取1到∞\infty∞时,得到合法的范数(符合范数规则),因而可以说:合法范数的集合图像都是凸的(而当p小于1,图像为凹的,可能对应了三角不等式等属性的丧失)
由图可得推论:对任意向量v\bold vv,有∥v∥∞≤∥v∥2≤∥v∥1≤n∥v∥2{\|\bold v \|_\infty}\le {\|\bold v \|_2}\le {\|\bold v \|_1}\le\sqrt n {\|\bold v \|_2}∥v∥∞≤∥v∥2≤∥v∥1≤n∥v∥2
证明:
①对于向量[12,12][\frac{1}{\sqrt 2},\frac{1}{\sqrt 2}][21,21],绘制各范数的等高线:
显然∥v∥∞≤∥v∥2≤∥v∥1{\|\bold v \|_\infty}\le {\|\bold v \|_2}\le {\|\bold v \|_1}∥v∥∞≤∥v∥2≤∥v∥1
②已经知道∥v∥2≤∥v∥1{\|\bold v \|_2}\le {\|\bold v \|_1}∥v∥2≤∥v∥1,
固定使∥v∥2=1{\|\bold v \|_2}=1∥v∥2=1,对应下图中红色圆上的所有点;
那么圆上所有点中,∥v∥1{\|\bold v \|_1}∥v∥1最小为1,最大为2\sqrt 22,显然∥v∥2≤∥v∥1≤n∥v∥2{\|\bold v \|_2}\le {\|\bold v \|_1}\le\sqrt n {\|\bold v \|_2}∥v∥2≤∥v∥1≤n∥v∥2
另一类范数是椭圆范数/ S范数:∥v∥S=vTSv{\left\|\bold v \right\|_S} = \sqrt {{\bold v^T}\boldsymbol S\bold v}∥v∥S=vTSv其中,S\boldsymbol SS是对称正定矩阵/Hermite正定矩阵,而外面的根号是为了保证范数的性质∥cv∥S=c∥v∥S{\left\|c\bold v \right\|_S}=c{\left\|\bold v \right\|_S}∥cv∥S=c∥v∥S
之所以称为“椭圆范数”,是因为该范数与二次型有关,而且正定二次型的横截面就是椭圆
例如,当S=[]\boldsymbol S=\begin{bmatrix} 2 &0 \\ 0 &3\end{bmatrix}S=[2003],∥v∥S2=2v12+3v22=1{\left\|\bold v \right\|_S^2} = 2v_1^2 + 3v_2^2 = 1∥v∥S2=2v12+3v22=1的图像为一个椭圆,这相当于一种用2和3加权后的范数
当S=I\boldsymbol S=\boldsymbol IS=I,椭圆范数退化为ℓ2\ell ^2ℓ2范数
范数最小化的优化问题
一个经典的优化问题模型是:
min∥x∥,s.t.Ax=b\min \left\| \bold x \right\|, s.t. \boldsymbol A\bold x=\bold bmin∥x∥,s.t.Ax=b
在L1和L2范数下,最优解的图解:
在几何上,Ax=b\boldsymbol A\bold x=\bold bAx=b的解空间构成一个流形(上面的直线);
菱形/圆形对应了L1和L2范数的“等高线”,想象菱形/圆形从原点不断向外扩张,它们第一次与直线的交点,就是问题的解
在最优化中,L1范数最小化的方法,称为基追踪(basis pursuit);
L2范数最小化的方法称为岭回归(ridge regression),有点类似最小二乘法
赋范向量空间与内积空间
若向量空间有定义良好的范数,我们称之为赋范向量空间(normed vector space)
前置知识:内积空间
内积是实或复向量空间中的一种数值函数,内积满足以下性质:
Hermitian 对称性:⟨x,y⟩=⟨y,x⟩‾\left\langle\mathbf{x},\mathbf{y}\right\rangle=\overline{\left\langle\mathbf{y},\mathbf{x}\right\rangle}⟨x,y⟩=⟨y,x⟩(上横线为共轭)共轭双线性:
⟨x,y+z⟩=⟨x,y⟩+⟨x,z⟩\left\langle\mathbf{x},\mathbf{y}+\mathbf{z}\right\rangle=\left\langle\mathbf{x},\mathbf{y}\right\rangle+\left\langle\mathbf{x},\mathbf{z}\right\rangle⟨x,y+z⟩=⟨x,y⟩+⟨x,z⟩、
⟨x,cy⟩=c⟨x,y⟩\left\langle\mathbf{x},c\mathbf{y}\right\rangle=c\left\langle\mathbf{x},\mathbf{y}\right\rangle⟨x,cy⟩=c⟨x,y⟩正定性:⟨x,x⟩≥0\left\langle\mathbf{x},\mathbf{x}\right\rangle\ge 0⟨x,x⟩≥0,⟨x,x⟩=0\left\langle\mathbf{x},\mathbf{x}\right\rangle=0⟨x,x⟩=0当且仅当x=0\mathbf{x}=\mathbf{0}x=0
满足上述条件的向量空间称为内积空间 (inner product space)
详见:内积的定义
在内积空间中,广义矢量范数也可定义于内积运算上:∥x∥=⟨x,x⟩\displaystyle \Vert\mathbf{x}\Vert=\sqrt{\left\langle\mathbf{x},\mathbf{x}\right\rangle}∥x∥=⟨x,x⟩
这就是说,内积空间是一个赋范向量空间
重要不等式
Hölder 不等式:∣xHy∣≤∥x∥p∥y∥q\displaystyle \vert\mathbf{x}^H\mathbf{y}\vert\le\Vert\mathbf{x}\Vert_p\Vert\mathbf{y}\Vert_q∣xHy∣≤∥x∥p∥y∥q(其中p,q>1p,q>1p,q>1且1/p+1/q=11/p+1/q=11/p+1/q=1)当 p=q=2p=q=2p=q=2,Hölder 不等式退化为 Cauchy-Schwarz 不等式
Cauchy-Schwarz 不等式:∣⟨x,y⟩∣=∣xHy∣≤∥x∥∥y∥|{\left\langle\mathbf{x},\mathbf{y}\right\rangle}|=\displaystyle \vert\mathbf{x}^H\mathbf{y}\vert\le\Vert\mathbf{x}\Vert \Vert\mathbf{y}\Vert∣⟨x,y⟩∣=∣xHy∣≤∥x∥∥y∥(内积绝对值<=长度的乘积)
由Cauchy-Schwarz 不等式可以导出三角不等式:∥x+y∥≤∥x∥+∥y∥\displaystyle \Vert\mathbf{x}+\mathbf{y}\Vert\le\Vert\mathbf{x}\Vert+\Vert\mathbf{y}\Vert∥x+y∥≤∥x∥+∥y∥
Hölder 不等式还可以用于证明Minkowski 不等式(“p范数下的三角不等式”)
Minkowski 不等式:∥x+y∥p≤∥x∥p+∥y∥p\Vert \mathbf{x}+\mathbf{y}\Vert_p\le\Vert\mathbf{x}\Vert_p+\Vert\mathbf{y}\Vert_p∥x+y∥p≤∥x∥p+∥y∥p
reference:
MIT 18.065—机器学习中的矩阵方法08 向量和矩阵的范数
赋范向量空间
向量范数
矩阵范数