最小二范数解

子空间投影问题(最小二乘法)

投影向量

$\textbf{b}$b向$z$z轴和$xy$xy平面投影分别为$\textbf{p}_{1}$p1​和$\textbf{p}_{2}$p2​两个变换矩阵$\textbf{P}_{1}$P1​ 和 $\textbf{P}_{2}$P2​满足如下以上的例子中两个子空间是正交补的。
上面的问题可以描述为，在空间$\mathbb{R}^{n}$Rn中，寻找向量$\textbf{b}$b向子空间$\mathbb{R}^{m}$Rm投影的变换矩阵$\textbf{P}$P。

考虑如下情况向量到直线上投影

在二维空间上$\mathbb{R}^{2}$R2,求$\textbf{b}$b在子空间$\textbf{A}=[1 \ 0]^{T}$A=[1 0]T上的投影$\textbf{p}$p。

• 投影方法
  $\textbf{p}$p可以表示为$\textbf{p}=\textbf{A}\textbf{x},\textbf{x}\in \mathbb{R}^{1}$p=Ax,x∈R1
  $\vec{bp}=\textbf{p}-\textbf{b}=\textbf{b}-\textbf{A}\textbf{x}$bp​=p−b=b−Ax
  由于$\textbf{b}-\textbf{A}\textbf{x}\perp\textbf{A}$b−Ax⊥A
  所以$\textbf{A}^{T}(\textbf{b}-\textbf{A}\textbf{x})=0$AT(b−Ax)=0
  $\textbf{A}^{T}\textbf{A}\textbf{x}=\textbf{A}^{T}\textbf{b}$ATAx=ATb
  $\textbf{x}=(\textbf{A}^{T}\textbf{A})^{-1}\textbf{A}^{T}\textbf{b}$x=(ATA)−1ATb，那么最终得到
  $\textbf{p}=\textbf{A}(\textbf{A}^{T}\textbf{A})^{-1}\textbf{A}^{T}\textbf{b}$p=A(ATA)−1ATb
• 优化方法（最小二乘法）
  $\textbf{p}$p可以表示为$\textbf{p}=\textbf{A}\textbf{x},\textbf{x}\in \mathbb{R}^{1}$p=Ax,x∈R1 \优化的过程可以表示为$\min\limits_{\textbf{x}}J(\textbf{x})=\left\|\vec{bp}\right\|_2^2$xmin​J(x)=∥∥∥​bp​∥∥∥​22​其中$J(\textbf{x})=(\textbf{b}-\textbf{A}\textbf{x})^{T}(\textbf{b}-\textbf{A}\textbf{x})$J(x)=(b−Ax)T(b−Ax)\那么$J'(\textbf{x})=\textbf{A}^{T}(\textbf{b}-\textbf{A}\textbf{x})=0$J′(x)=AT(b−Ax)=0得到（具体参见标量函数对矢量/矩阵的导数内容）$\textbf{p}=\textbf{A}(\textbf{A}^{T}\textbf{A})^{-1}\textbf{A}^{T}\textbf{b}$p=A(ATA)−1ATb

子空间投影

之前的叙述中$\textbf{x}$x可以理解为将投影子空间的基线性组合为$\textbf{p}$p的系数，进行如下的叙述：\假设，在空间$\mathbb{R}^{m}$Rm中的$n$n个向量$\textbf{a}_1,\textbf{a}_2,\cdots,\vec{a_n}$a1​,a2​,⋯,an​​是线性不相关的，我们想找到一个线性组合$\textbf{p}=\hat{x}_1\textbf{a}_1+\cdots+\hat{x}_n\textbf{a}_n$p=x^1​a1​+⋯+x^n​an​使得 $\min\limits_{\textbf{x}}J(\textbf{x})=\left\|\vec{bp}\right\|_2^2$xmin​J(x)=∥∥∥​bp​∥∥∥​22​，那么只要$\vec{bp}$bp​垂直于子空间便满足要求，也即$\vec{bp}$bp​垂直于子空间所有向量，得到如下等式：
$\begin{matrix} a_1^T(\textbf{b}-\textbf{A}\textbf{x})=0 \\ \vdots \\ a_n^T(\textbf{b}-\textbf{A}\textbf{x})=0 \\\end{matrix}\quad or\quad\left[ \begin{matrix} a_1^T \\ \vdots \\ a_n^T \\ \end{matrix}\right]\left[\textbf{b}-\textbf{A}\textbf{x}\right]=\textbf{A}^T(\textbf{b}-\textbf{A}\textbf{x})=\textbf{0}$a1T​(b−Ax)=0⋮anT​(b−Ax)=0​or⎣⎢⎡​a1T​⋮anT​​⎦⎥⎤​[b−Ax]=AT(b−Ax)=0
化简
$\textbf{x}=(\textbf{A}^{T}\textbf{A})^{-1}\textbf{A}^{T}\textbf{b}$x=(ATA)−1ATb
$\textbf{p}=\textbf{A}(\textbf{A}^{T}\textbf{A})^{-1}\textbf{A}^{T}\textbf{b}$p=A(ATA)−1ATb

最小二范数解

对于之前讨论的问题$\min\limits_{\textbf{x}}J(\textbf{x})=\left\|\textbf{b}-\textbf{A}\textbf{x}\right\|_2^2$xmin​J(x)=∥b−Ax∥22​

1. $\textbf{A}\in\mathbb{R}^{m\times n},\textbf{x}\in\mathbb{R}^{n\times 1},\textbf{b}\in\mathbb{R}^{m\times 1}$A∈Rm×n,x∈Rn×1,b∈Rm×1
2. $\textbf{A}$A行满秩或列满秩

设任意一向量$\textbf{vect}=\textbf{b}-\textbf{A}\textbf{x}$vect=b−Ax，移项后具有$\textbf{A}\textbf{x}=\textbf{b}$Ax=b的形式，那么对于$\textbf{A}\textbf{x}=\textbf{b}$Ax=b我们知道：

• $m=n$m=n时，方程具有唯一解
• $m>n$m>n时，方程无解
• $m<n$m<n时，方程有无穷解
  在之前投影的问题$\vec{bp}=\textbf{b}-\textbf{A}\textbf{x}$bp​=b−Ax($\textbf{b}\notin\textbf{A}$b∈/​A)属于方程无解的情况，得到的解$\textbf{x}$x为使$\left\|\textbf{b}-\textbf{A}\textbf{x}\right\|_2^2$∥b−Ax∥22​（或者叫做误差）最小的解。但对于$m<n$m<n，方程有无穷解的情况可以利用最小二乘法求解最小二范数解。
  $\textbf{A}\textbf{x}=\textbf{b}$Ax=b，满足：

1. $\textbf{A}\in\mathbb{R}^{m\times n},\textbf{x}\in\mathbb{R}^{n\times 1},\textbf{b}\in\mathbb{R}^{m\times 1}$A∈Rm×n,x∈Rn×1,b∈Rm×1
2. $\textbf{A}$A行满秩
3. $m<n$m<n

问题描述 $\min\limits_{\textbf{x}}\left\|\textbf{x}\right\|_2^2=\textbf{x}^T\textbf{x}$xmin​∥x∥22​=xTx ($s.t.\textbf{A}\textbf{x}=\textbf{b}$s.t.Ax=b)
引入拉格朗日算子$J(\textbf{x})=\frac{1}{2}\textbf{x}^T\textbf{x}-\lambda(\textbf{A}\textbf{x}-\textbf{b}),(\lambda\in\mathbb{R}^{m\times 1})$J(x)=21​xTx−λ(Ax−b),(λ∈Rm×1)
对上式求导$\nabla J(\textbf{x})=\textbf{x}-\textbf{A}^T\lambda=0$∇J(x)=x−ATλ=0
$\textbf{x}=\textbf{A}^T\lambda$x=ATλ
$\textbf{A}\textbf{x}=\textbf{A}\textbf{A}^T\lambda$Ax=AATλ
$(\textbf{A}\textbf{A}^T)^{-1}\textbf{A}\textbf{x}=\lambda$(AAT)−1Ax=λ
$\lambda=(\textbf{A}\textbf{A}^T)^{-1}\textbf{b}$λ=(AAT)−1b
可以得到
$\textbf{x}=\textbf{A}^T(\textbf{A}\textbf{A}^T)^{-1}\textbf{b}$x=AT(AAT)−1b
结论，对$\textbf{A}\textbf{x}=\textbf{b}$Ax=b：

• $m=n$m=n时，方程具有唯一解- $m>n$m>n时，方程无解 最小二乘解为$\textbf{x}=(\textbf{A}^{T}\textbf{A})^{-1}\textbf{A}^{T}\textbf{b}$x=(ATA)−1ATb
• $m<n$m<n时，方程有无穷解
  最小二范数解为$\textbf{x}=\textbf{A}^T(\textbf{A}\textbf{A}^T)^{-1}\textbf{b}$x=AT(AAT)−1b 其中$(\textbf{A}^{T}\textbf{A})^{-1}\textbf{A}^{T}$(ATA)−1AT和$\textbf{A}^T(\textbf{A}\textbf{A}^T)^{-1}$AT(AAT)−1为$\textbf{A}$A在相应情况下的伪逆矩阵。