常见的向量范数、矩阵范数和对偶范数-对偶范数详细证明过程

对偶范数

对偶范数的定义帮助我们理解不同范数间的互补关系，特别是在优化问题中。以下是对偶范数的概念及一些常见的特例说明：

一般定义：$p$-范数和$q$-范数的对偶性

对于任意的$p$-范数，定义为：
$$\frac{1}{p}+\frac{1}{q}=1,p,q\ge 1$$
其中$q$-范数定义为：
$$\Vert y{\Vert }_q={\left(\sum _{i=1}^n|y_i{|}^q\right)}^{1/q}$$
换句话说，$p$-范数和$q$-范数构成对偶关系。对于向量$y$，其$q$-范数的定义满足：
$$\Vert y{\Vert }_q=\underset{\Vert x{\Vert }_p\le 1}{\sup }{x}^{T}y$$
即在$\Vert x{\Vert }_p\le 1$的约束下，$x^{T}y$的最大值就是$\Vert y{\Vert }_q$。

特例 1：无穷范数和 1 范数的对偶性

无穷范数（$\infty$-范数）和 1 范数构成对偶关系。当$p=\infty$时，$q=1$。其关系如下：

• 无穷范数定义为：
  $$\Vert x{\Vert }_{\infty }=\underset{i}{\max }|x_i|$$

• 1 范数定义为：
  $$\Vert y{\Vert }_1=\sum _{i=1}^n|y_i|$$

根据对偶性，有
$$\Vert x{\Vert }_{\infty }=\underset{\Vert y{\Vert }_1\le 1}{\sup }{x}^{T}y$$
此时，若$y$满足 1 范数约束，其与$x$的内积达到最大时即为$x$的无穷范数。

特例 2：2 范数的对偶是自身

对于 2 范数（欧几里得范数），有$p=q=2$，即 2 范数的对偶范数是自身：

• 2 范数定义为：
  $$\Vert x{\Vert }_2={\left(\sum _{i=1}^n|x_i{|}^2\right)}^{1/2}$$

在这种情况下，我们可以写成：
$$\Vert y{\Vert }_2=\underset{\Vert x{\Vert }_2\le 1}{\sup }{x}^{T}y$$
也就是说，当$x$的 2 范数不超过 1 时，$x^{T}y$的最大值是$y$的 2 范数。这反映了 2 范数的自对偶性。

除了$p$-范数和$q$-范数的典型对偶组合（如$\infty$-范数与$1$-范数的对偶关系，和$2$-范数的自对偶性）之外，还有其他常见的特例：

特例 3：有限范数与 0 范数的对偶关系（稀疏性）

在一些优化问题中，尤其是稀疏信号处理和压缩感知中，出现了一种与“伪范数”相关的对偶关系。具体而言：

• 0 范数（严格意义上它并不是范数）表示向量中非零元素的数量：
  $$\Vert x{\Vert }_0=\text{number of non-zero elements in }x$$

• 1 范数与 0 范数相关，因为它能够在某种程度上作为 0 范数的凸近似，帮助解决稀疏性问题。

虽然 0 范数和 1 范数没有直接的对偶关系，但在稀疏优化中，经常使用 1 范数作为一种替代方式来促进解的稀疏性。这意味着通过最小化 1 范数来近似最小化 0 范数的效果，尤其是在压缩感知问题中，1 范数能够产生与 0 范数优化类似的稀疏解。

特例 4：核范数（Nuclear Norm）与谱范数（Spectral Norm）的对偶关系

在矩阵的范数理论中，核范数（Nuclear Norm）和谱范数（Spectral Norm）之间具有对偶关系：

• 核范数，也称为迹范数，是矩阵奇异值的和。对于矩阵$X$，核范数定义为：
  $$\Vert X{\Vert }_{\ast }=\sum _{i=1}^n{\sigma }_i(X)$$
  其中${\sigma }_i(X)$是矩阵$X$的第$i$个奇异值。

• 谱范数，也称为算子范数或 2-范数，表示矩阵的最大奇异值：
  $$\Vert X{\Vert }_2=\underset{i}{\max }{\sigma }_i(X)$$

核范数和谱范数的对偶关系可写为：
$$\Vert X{\Vert }_{\ast }=\underset{\Vert Y{\Vert }_2\le 1}{\sup }\text{Tr}(Y^{T}X)$$
在这里，核范数是对矩阵的稀疏性（低秩）的一个度量，而谱范数对矩阵的行列式约束进行控制。因此，这对对偶性在矩阵稀疏和低秩优化问题中起到重要作用。

2范数自对偶证明

对于 2 范数的对偶性，具体地，我们希望证明 2 范数的对偶范数是自身。也就是说，对于任何向量$y\in {\mathbb{R}}^n$，以下关系成立：
$$\Vert y{\Vert }_2=\underset{\Vert x{\Vert }_2\le 1}{\sup }{x}^{T}y$$
即 2 范数是其自身的对偶范数。

证明过程

1. 2 范数的定义

对于向量$y=(y_1,y_2,\dots ,y_n)\in {\mathbb{R}}^n$，其 2 范数（欧几里得范数）定义为：
$$\Vert y{\Vert }_2={\left(\sum _{i=1}^n{y}_i^2\right)}^{1/2}$$

2. 对偶问题的设定

为了证明 2 范数是自身的对偶范数，我们需要求解在$\Vert x{\Vert }_2\le 1$的约束条件下最大化$x^{T}y$的问题。这相当于找到一个向量$x$，使得$x^{T}y$尽可能大，并满足$x$的 2 范数不超过 1。

所以我们构造以下优化问题：
$$\underset{\Vert x{\Vert }_2\le 1}{\sup }{x}^{T}y$$

3. 计算内积的最大化

为了解决这个优化问题，我们使用柯西-施瓦茨不等式（Cauchy-Schwarz Inequality），它表明对于任意两个向量$x,y\in {\mathbb{R}}^n$：
$$|x^{T}y|\le \Vert x{\Vert }_2\Vert y{\Vert }_2$$
其中等号成立的条件是$x$与$y$共线，即存在实数$\lambda$使得$x=\lambda y$。

4. 取到等号的条件

在$\Vert x{\Vert }_2\le 1$的限制下，要使$x^{T}y$取到最大值，可以选择$x$的方向与$y$相同，即令$x=\frac{y}{\Vert y{\Vert }_2}$。这样可以确保$x$的 2 范数为 1（满足约束条件），并且内积$x^{T}y$达到最大值。

因此，我们有
$$x^{T}y={\left(\frac{y}{\Vert y{\Vert }_2}\right)}^{T}y=\frac{y^{T}y}{\Vert y{\Vert }_2}=\frac{\Vert y{\Vert }_2^2}{\Vert y{\Vert }_2}=\Vert y{\Vert }_2$$

5. 结论

因此，在$\Vert x{\Vert }_2\le 1$的条件下，$x^{T}y$的最大值为$\Vert y{\Vert }_2$，即：
$$\underset{\Vert x{\Vert }_2\le 1}{\sup }{x}^{T}y=\Vert y{\Vert }_2$$
这证明了 2 范数的对偶范数是其自身。

1范数和无穷范数互为对偶证明

我们来详细推导无穷范数（$\Vert \cdot {\Vert }_{\infty }$）和 1 范数（$\Vert \cdot {\Vert }_1$）的对偶关系。

目标

证明对于向量$y\in {\mathbb{R}}^n$，有以下关系成立：
$$\Vert y{\Vert }_1=\underset{\Vert x{\Vert }_{\infty }\le 1}{\sup }{x}^{T}y$$
即 1 范数是无穷范数约束下的内积$x^{T}y$的最大值。

证明步骤

1. 无穷范数和 1 范数的定义

给定向量$y=(y_1,y_2,\dots ,y_n)$和$x=(x_1,x_2,\dots ,x_n)$：

• 无穷范数定义为
  $$\Vert x{\Vert }_{\infty }=\underset{i}{\max }|x_i|$$
  因此约束$\Vert x{\Vert }_{\infty }\le 1$表示$|x_i|\le 1$对于所有$i=1,2,\dots ,n$。

• 1 范数定义为
  $$\Vert y{\Vert }_1=\sum _{i=1}^n|y_i|$$

2. 构造最优$x$

在约束$\Vert x{\Vert }_{\infty }\le 1$下，我们希望最大化$x^{T}y={\sum }_{i=1}^n{x}_i{y}_i$。为了使内积$x^{T}y$最大，我们需要选择$x_i$的符号与$y_i$的符号一致，并取$x_i=\mathrm{sign}(y_i)$（即$x_i=1$当$y_i\ge 0$，否则$x_i=-1$）。这样可以确保每一项$x_i{y}_i$的值都为正，从而使得和最大化。

因此，对于每个$i$，我们设
$$x_i=\{\begin{array}{ll}1& \text{如果 }{y}_i\ge 0\\ -1& \text{如果 }{y}_i<0\end{array}$$

3. 计算$x^{T}y$的最大值

在上述选择下，内积$x^{T}y$成为
$$x^{T}y=\sum _{i=1}^n{x}_i{y}_i=\sum _{i=1}^n|y_i|$$

这正是$y$的 1 范数，即
$$\Vert y{\Vert }_1=\sum _{i=1}^n|y_i|$$

4. 取上确界

因此，我们得出
$$\underset{\Vert x{\Vert }_{\infty }\le 1}{\sup }{x}^{T}y=\Vert y{\Vert }_1$$
这表明在无穷范数限制下，$x^{T}y$的最大值等于$y$的 1 范数，从而证明了无穷范数与 1 范数的对偶性。

结论

无穷范数和 1 范数是对偶范数对，因为在$\Vert x{\Vert }_{\infty }\le 1$的条件下，$x^{T}y$的最大值恰好是 $y$的 1 范数，即
$$\Vert y{\Vert }_1=\underset{\Vert x{\Vert }_{\infty }\le 1}{\sup }{x}^{T}y$$

在上述选择下，内积$x^{T}y$成为
$$x^{T}y=\sum _{i=1}^n{x}_i{y}_i=\sum _{i=1}^n|y_i|$$

这正是$y$的 1 范数，即
$$\Vert y{\Vert }_1=\sum _{i=1}^n|y_i|$$

4. 取上确界

因此，我们得出
$$\underset{\Vert x{\Vert }_{\infty }\le 1}{\sup }{x}^{T}y=\Vert y{\Vert }_1$$
这表明在无穷范数限制下，$x^{T}y$的最大值等于$y$的 1 范数，从而证明了无穷范数与 1 范数的对偶性。

结论

无穷范数和 1 范数是对偶范数对，因为在$\Vert x{\Vert }_{\infty }\le 1$的条件下，$x^{T}y$的最大值恰好是 $y$的 1 范数，即
$$\Vert y{\Vert }_1=\underset{\Vert x{\Vert }_{\infty }\le 1}{\sup }{x}^{T}y$$

对偶范数中既有向量范数也有矩阵范数

谱范数是矩阵范数，而不是向量范数。谱范数（2-范数）定义为矩阵的最大奇异值，适用于矩阵而不是单独的向量。它用于衡量线性变换对向量的伸缩程度。

向量范数

对于向量$x$而言，$p$-范数$\Vert x{\Vert }_p$）定义为
$$\Vert x{\Vert }_p={\left(\sum _{i=1}^n|x_i{|}^p\right)}^{1/p}$$
矩阵范数
而矩阵的谱范数$\Vert X{\Vert }_2$则是矩阵作用在向量上时的最大伸缩量。对于矩阵$X$的谱范数，有
$$\Vert X{\Vert }_2=\underset{\Vert x{\Vert }_2\le 1}{\sup }\Vert Xx{\Vert }_2$$
即，谱范数是使得$Xx$达到最大长度的$x$的伸缩量。这也是为什么谱范数涉及奇异值，因为奇异值表示矩阵作用下的尺度变化。

向量范数和矩阵范数

一、向量范数

向量范数用于衡量向量的大小或长度。常见的向量范数包括 1 范数、2 范数（欧几里得范数）和无穷范数。

向量范数定义

给定向量$x=(x_1,x_2,\dots ,x_n)$，定义如下：

1. 1 范数（曼哈顿范数）：
   $$\Vert x{\Vert }_1=\sum _{i=1}^n|x_i|$$

2. 2 范数（欧几里得范数）：
   $$\Vert x{\Vert }_2={\left(\sum _{i=1}^n|x_i{|}^2\right)}^{1/2}$$

3. 无穷范数（最大范数）：
   $$\Vert x{\Vert }_{\infty }=\underset{i}{\max }|x_i|$$

例子：计算向量范数

设定向量$x=(3,-4)$，计算它的 1 范数、2 范数和无穷范数。

1. 1 范数：
   $$\Vert x{\Vert }_1=|3|+|-4|=3+4=7$$

2. 2 范数：
   $$\Vert x{\Vert }_2=\sqrt{3^2+(-4{)}^2}=\sqrt{9+16}=\sqrt{25}=5$$

3. 无穷范数：
   $$\Vert x{\Vert }_{\infty }=\max (|3|,|-4|)=\max (3,4)=4$$

二、矩阵范数

矩阵范数用于衡量矩阵作为线性变换的“伸缩效应”。常见的矩阵范数包括 1 范数、Frobenius 范数、无穷范数和谱范数（2-范数）。

矩阵范数定义

对于矩阵$X=(x_{ij})\in {\mathbb{R}}^{m\times n}$，定义如下：

1. 1 范数（列和范数）：最大列和
   $$\Vert X{\Vert }_1=\underset{1\le j\le n}{\max }\sum _{i=1}^m|x_{ij}|$$

2. Frobenius 范数（矩阵的 2 范数）：矩阵元素平方和的平方根
   $$\Vert X{\Vert }_F=\sqrt{\sum _{i=1}^m\sum _{j=1}^n|x_{ij}{|}^2}$$

3. 无穷范数（行和范数）：最大行和
   $$\Vert X{\Vert }_{\infty }=\underset{1\le i\le m}{\max }\sum _{j=1}^n|x_{ij}|$$

4. 谱范数（最大奇异值）：矩阵的最大奇异值
   $$\Vert X{\Vert }_2={\sigma }_{\max }(X)$$
   谱范数$\Vert X{\Vert }_2$是矩阵$X$的最大奇异值。如果矩阵$X\in {\mathbb{R}}^{m\times n}$的奇异值为${\sigma }_1,{\sigma }_2,\dots ,{\sigma }_{\min (m,n)}$，则谱范数为：

$$\Vert X{\Vert }_2=\underset{i}{\max }{\sigma }_i(X)$$
奇异值是从矩阵$X$的协方差矩阵$X^{T}X$的特征值中得出的。假设特征值为${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_{\min (m,n)}$，则奇异值为${\sigma }_i=\sqrt{{\lambda }_i}$。

例子：计算矩阵范数

设定矩阵
$$X=\left(\begin{array}{cc}1& -2\\ -3& 4\end{array}\right)$$

1. 1 范数：
   $$\Vert X{\Vert }_1=\max (|1|+|-3|,|-2|+|4|)=\max (4,6)=6$$

2. Frobenius 范数：
   $$\Vert X{\Vert }_F=\sqrt{1^2+(-2{)}^2+(-3{)}^2+4^2}=\sqrt{1+4+9+16}=\sqrt{30}$$

3. 无穷范数：
   $$\Vert X{\Vert }_{\infty }=\max (|1|+|-2|,|-3|+|4|)=\max (3,7)=7$$

4. 谱范数：
   计算$X^{T}X$并求特征值，取平方根得到最大奇异值。

• 谱范数例子1【矩阵维度相等】
  考虑一个简单的 2x2 矩阵：
  $$X=\left(\begin{array}{cc}3& 1\\ 1& 3\end{array}\right)$$

  步骤 1：计算$X^{T}X$

  为了找到奇异值，我们首先计算$X^{T}X$：

  $$X^{T}X=\left(\begin{array}{cc}3& 1\\ 1& 3\end{array}\right)\left(\begin{array}{cc}3& 1\\ 1& 3\end{array}\right)=\left(\begin{array}{cc}3\cdot 3+1\cdot 1& 3\cdot 1+1\cdot 3\\ 1\cdot 3+3\cdot 1& 1\cdot 1+3\cdot 3\end{array}\right)$$

  $$=\left(\begin{array}{cc}9+1& 3+3\\ 3+3& 1+9\end{array}\right)=\left(\begin{array}{cc}10& 6\\ 6& 10\end{array}\right)$$

  步骤 2：计算$X^{T}X$的特征值

  特征值$\lambda$满足特征方程：
  $$\det (X^{T}X-\lambda I)=0$$
  即：
  $$\left|\begin{array}{cc}10-\lambda & 6\\ 6& 10-\lambda \end{array}\right|=0$$
  展开行列式：
  $$(10-\lambda )(10-\lambda )-6\cdot 6=0$$

  $${\lambda }^2-20\lambda +64=0$$

  解得：
  $$\lambda =16\text{和}\lambda =4$$

  步骤 3：计算奇异值

  奇异值为特征值的平方根，因此：
  $${\sigma }_1=\sqrt{16}=4,{\sigma }_2=\sqrt{4}=2$$

  步骤 4：求谱范数

  谱范数是最大奇异值，因此：
  $$\Vert X{\Vert }_2=\max ({\sigma }_1,{\sigma }_2)=4$$

  总结
  通过计算奇异值的最大值，我们得到矩阵$X$的谱范数为 4。对称矩阵的谱范数也是奇异值的最大值。

• 谱范数例子2【矩阵维度不相等】

  我们可以通过一个非方阵（矩阵维数不相等）的例子来理解谱范数的计算。假设我们有一个$3\times 2$矩阵：
  $$X=\left(\begin{array}{cc}1& 2\\ 3& 4\\ 5& 6\end{array}\right)$$

  步骤 1：计算$X^{T}X$

  因为谱范数等于最大奇异值，我们可以通过计算矩阵$X^{T}X$的特征值来获得奇异值。首先，计算$X^{T}X$：
  $$X^T=\left(\begin{array}{ccc}1& 3& 5\\ 2& 4& 6\end{array}\right)$$

  $$X^{T}X=\left(\begin{array}{ccc}1& 3& 5\\ 2& 4& 6\end{array}\right)\left(\begin{array}{cc}1& 2\\ 3& 4\\ 5& 6\end{array}\right)$$

  执行矩阵乘法：
  $$X^{T}X=\left(\begin{array}{cc}1\cdot 1+3\cdot 3+5\cdot 5& 1\cdot 2+3\cdot 4+5\cdot 6\\ 2\cdot 1+4\cdot 3+6\cdot 5& 2\cdot 2+4\cdot 4+6\cdot 6\end{array}\right)$$

  $$=\left(\begin{array}{cc}1+9+25& 2+12+30\\ 2+12+30& 4+16+36\end{array}\right)=\left(\begin{array}{cc}35& 44\\ 44& 56\end{array}\right)$$

  步骤 2：计算$X^{T}X$的特征值

  特征值$\lambda$满足以下特征方程：
  $$\det (X^{T}X-\lambda I)=0$$
  即：

  $$\left|\begin{array}{cc}35-\lambda & 44\\ 44& 56-\lambda \end{array}\right|=0$$
  展开行列式得到特征方程：

  $$(35-\lambda )(56-\lambda )-44^2=0$$
  计算：

  $${\lambda }^2-91\lambda +36=0$$
  解得两个特征值

  接着求解上一步的特征值方程：

  我们得到特征方程为：
  $${\lambda }^2-91\lambda +36=0$$
  可以使用二次方程公式求解：
  $$\lambda =\frac{91\pm \sqrt{91^2-4\cdot 1\cdot 36}}{2}$$
  计算根号内部分：
  $$91^2=8281$$

  $$4\cdot 1\cdot 36=144$$

  $$8281-144=8137$$

  因此，
  $$\lambda =\frac{91\pm \sqrt{8137}}{2}$$
  计算出两个特征值（记为${\lambda }_1$和${\lambda }_2$），然后取平方根得到奇异值${\sigma }_1=\sqrt{{\lambda }_1}$和${\sigma }_2=\sqrt{{\lambda }_2}$。

  最终步骤：谱范数

  矩阵$X$的谱范数$\Vert X{\Vert }_2$为最大奇异值：
  $$\Vert X{\Vert }_2=\max ({\sigma }_1,{\sigma }_2)$$
  通过这个过程，我们可以得到非方矩阵的谱范数，即奇异值中的最大值。