矩阵方程求解&最小二乘法

矩阵方程的求解主要分为三类

• 超定矩阵方程，m>n,A,b已知
• 盲矩阵方程：b已知，A未知
• 欠定稀疏矩阵方程:m<n，A，b已知但x未知且稀疏

最小二乘法（LS）

普通最小二乘

考虑超定矩阵方程Ax=b,m>n，为了抵制误差对矩阵方程求解的影响，引入一校正向量△b，并用它去“扰动”有误差的数据向量b。我们的目标是，使校正项△b“尽可能小”

$$Ax=b$$

m>n时为超定方程

$$b=b_0+e$$$$b+\mathrm{\Delta }b\to b_0$$

问题可以理解为使

$$||\mathrm{\Delta }b|{|}^2\to min$$

的优化问题

$$Ax=b+\mathrm{\Delta }b$$$$L(x)=||Ax-b|{|}_2^2$$$$=(Ax-b{)}^H(Ax-b)$$$$\frac{\partial L(x)}{\partial x^{\ast }}=A^{H}Ax-A^{H}b=0$$$$\to x_{LS}=(A^{H}A{)}^{-1}{A}^{H}b$$

对于秩亏缺$（rank（A）<n）$的超定方程，最小二乘解为

$$\to x_{LS}=(A^{H}A{)}^{†}{A}^{H}b$$

高斯马尔可夫定理

在参数估计理论中,称参数向量$\theta$的估计$\hat{\theta }$为无偏估计，若它的数学期望值等于真实的未知参数向量，即$E\hat{\theta }=\theta$。进一步地，如果一个无偏估计还具有最小方差，则称这一无偏估计为最优无偏估计。

类似地，对于数据向量b含有加性噪声或者扰动的超定方程A$\theta$= b+e，若最小二乘解${\theta }_{LS}$的数学期望等于真实参数向量$\theta$，便称最小二乘解是无偏的。如果它还具有最小方差，则称最小二乘解是最优无偏的。

高斯马尔科夫定理指出了最优无偏解的条件，对于线性方程组

$$Ax=b_0+e$$

满足

$$\{\begin{array}{l}E(e)=0\\ cov\{e\}=E\{e{e}^H\}={\sigma }^{2}I\end{array}$$

当且仅当$rank(A)=n$时，最优无偏解为最小二乘解

$$x_{LS}=(A^{H}A{)}^{-1}{A}^{H}b$$

LS解与最大似然解的等价性

若加性误差向量$e=[e_1,\dots ,e_m{]}^T$为独立同分布的复高斯随机向量,其概率密度函数为

$$f(e)=\frac{1}{{\pi }^m|{|}_e}exp[-(e-ue{)}^H(e-Ue)]$$$$max\log f(e)==\frac{1}{{\sigma }^2}{e}^{H}e$$$$maxf(e)==min||Ax-b|{|}_2^2$$

所以在高斯马尔科夫条件下，矩阵方程的最大似然解等价于最小二乘解，但误差向量方程不同时，两者不相等

$${\hat{x}}_{ML}={\hat{x}}_{LS}$$

数据最小二乘（DLS）

与普通最小二乘不同，我们假定b无噪声，数据矩阵$A=A_0+E$有噪声,我们加入校正矩阵$\mathrm{\Delta }A$对A进行校准

$$\begin{array}{l}A=A_0+E\\ (A+\mathrm{\Delta }A)x=b\end{array}$$

我们的问题变为

$$min||\mathrm{\Delta }A|{|}_F^2,s.t.(A+\mathrm{\Delta }A)x=b$$

我们采用拉格朗日乘子法进行求解

$$L(x)=||\mathrm{\Delta }A|{|}_F^2+{\lambda }^H(Ax+\mathrm{\Delta }Ax-b)$$$$=tr(\mathrm{\Delta }A\mathrm{\Delta }{A}^H)+{\lambda }^H(Ax+\mathrm{\Delta }Ax-b)$$$$\frac{\partial L(x)}{\partial \mathrm{\Delta }{A}^T}=(\mathrm{\Delta }{A}^H)+x{\lambda }^H=0$$$$\to \mathrm{\Delta }A=-\lambda x^H$$

代入约束条件

$$(A+\mathrm{\Delta }A)x=b$$$$-\lambda x^{H}x+Ax=b$$$$\lambda x^{H}x=Ax-b$$$$\lambda =\frac{Ax-b}{x^{H}x}$$$$\mathrm{\Delta }A=-\frac{Ax-b}{x^{H}x}{x}^H$$$$J(x)=||\mathrm{\Delta }A|{|}_F^2$$$$=tr(\frac{(Ax-b)(Ax-b{)}^H}{x^{H}x})=\frac{||Ax-b|{|}_2^2}{||x|{|}_2^2}$$

得到数据最小二乘

$${\hat{x}}_{DLS}=\arg \underset{x}{min}\frac{(AX-b{)}^H(Ax-b)}{x^{H}x}$$

求导问题

x为一个列向量

• 行向量求偏导$$\frac{\partial }{\partial x^T}=[\frac{\partial }{\partial x_1},...,\frac{\partial }{\partial x_n}]$$
• 列向量$$\frac{\partial }{\partial x^T}=[\frac{\partial }{\partial x_1},...,\frac{\partial }{\partial x_n}{]}^T$$
• example$$\frac{\partial (a^{T}x)}{\partial x^T}=a^T$$$$\frac{\partial (a^{T}x)}{\partial x}=a$$
• 矩阵求导$$L=tr(\mathrm{\Delta }A\mathrm{\Delta }{A}^H)+{\lambda }^H(Ax+\mathrm{\Delta }A-b)$$$$\frac{\partial L}{\partial \mathrm{\Delta }{A}^T}=\mathrm{\Delta }{A}^H+x{\lambda }^H=0$$

Tikhonov 正则化方法

因为在真实问题中往往存在秩亏缺，所以在最小二乘的代价函数的基础上我们进行改进，加入了正则化参数，在神经网络的代价函数经常用到

$$J(x)=mi{n}_x||Ax-b|{|}_2^2+\lambda ||x|{|}_2^2$$$$J(x)=x^H{A}^{H}Ax-x^H{A}^{H}b-b^{H}Ax+b^{H}b+\lambda x^{H}x$$$$\frac{\partial J(x)}{\partial x^{\ast }}=A^{H}Ax-A^{H}b+\lambda x=0$$$$\to (A^{H}A+\lambda I)x=A^{H}b$$$${\hat{x}}_{Tik}=(A^{H}A+\lambda I{)}^{-1}{A}^{H}b$$

这种使用$(A^{H}A+\lambda I{)}^{-1}$代替协方差矩阵的直接求逆$(A^{H}A{)}^{-1}$的方法常称为Tikhonov正则化(Tikhonov regularization)，或简称正则化方法(regularized method)。

Tikhonov正则化方法的本质是:通过对秩亏缺的矩阵A 的协方差矩阵 $A^{H}A$ 的每一个对角元素加一个很小的扰动$\lambda$，使得奇异的协方差矩阵$A^{H}A$ 的求逆变成非奇异矩阵$(A^{H}A+\lambda I)$的求逆，从而大大改善求解秩亏缺矩阵方程 Ax = b 的数值稳定性。

反正则化去燥

显然，若数据矩阵A 满列秩，但存在误差或者噪声时，就需要采用与Tikhonov正则化相反的做法，对被噪声污染的协方差矩阵$A^{H}A$ 加一个很小的负扰动矩阵$-\lambda I$，

$$mi{n}_x||Ax-b|{|}_2^2-\lambda ||x|{|}_2^2$$$$\to \hat{x}=(A^{H}A-\lambda I{)}^{-1}{A}^{H}b$$

总体最小二乘(TLS)

在A，b同时存在误差的最小二乘方法

$$A=A_0+E$$$$b=b_0+e$$$$min||\mathrm{\Delta }A,\mathrm{\Delta }b|{|}_F^2$$

我们的约束优化问题转化为了

$$min||\mathrm{\Delta }A,\mathrm{\Delta }b|{|}_2^2=||\mathrm{\Delta }A|{|}_2^2+||\mathrm{\Delta }b|{|}_2^2,s.t.(A+\mathrm{\Delta }A)x=b+\mathrm{\Delta }b$$$$([A,b]+[\mathrm{\Delta }A,\mathrm{\Delta }b])\left[\begin{array}{c}x\\ 1\end{array}\right]=0$$

令

$$A^{\prime }=[A,b]$$$$\mathrm{\Delta }{A}^{\prime }=[\mathrm{\Delta }A,\mathrm{\Delta }b])$$$$x^{\prime }=\left[\begin{array}{c}x\\ 1\end{array}\right]$$

原方程转化为数据最下二乘问题

$$(A^{\prime }+\mathrm{\Delta }{A}^{\prime })x^{\prime }=0$$$$\to mi{n}_{x^{\prime }}\frac{(A^{\prime }{x}^{\prime }-b^{\prime })(A^{\prime }{x}^{\prime }-b^{\prime }{)}^H}{x^{\prime H}{x}^{\prime }}$$$$=min\frac{x^{{}^{\prime }H}{A}^{\prime H}{A}^{\prime }{x}^{\prime }}{x^{\prime H}{x}^{\prime }}$$$$=min\frac{||Ax-b|{|}_2^2}{||x|{|}_2^2+1}$$

令

$$B=[A,b]$$

其奇异值分解为

$$B=U\mathrm{\Sigma }{V}^H$$

总体最小二乘的解为

$$x^{\prime }=-\frac{1}{v(n+1,n+1)}{V}_{min}$$

总体最小二乘的几何意义

和点到线的距离相似$ai^T$\mathrm{是}\mathrm{矩}\mathrm{阵}\mathrm{的}\mathrm{第}i\mathrm{行}，$b_i$\mathrm{是}\mathrm{第}i\mathrm{个}\mathrm{元}\mathrm{素}，\mathrm{总}\mathrm{体}\mathrm{最}\mathrm{小}\mathrm{二}\mathrm{乘}\mathrm{的}\mathrm{解}$x{TLS}$是使

$$mi{n}_x\frac{||Ax-b|{|}_2^2}{||x|{|}_2^2+1}=\sum _{i=1}^n\frac{|a_i^{T}x-b_i{|}^2}{x^{T}x+1}$$

问题转化为了点集$(a_i,b_i)$到直线$b=ax$的最小距离平方和

的极小化变量

总体最小二乘闭式解

若增广矩阵$B=[A,b]$的奇异值为$\sigma1≥…\sigma{n+1}$，则总体最小二乘解可表示成

$$x_{TLS}=(A^{H}A-{\sigma }_{n+1}^{2}I{)}^{-1}{A}^{H}b$$

与Tikhonov 正则化比较知，总体最小二乘是一种反正则化方法，可以解释为一种具有噪声清除作用的最小二乘方法:先从协方差矩阵 $A^{T}A$中减去噪声影响项${\sigma }_{n+1}^{2}I$，然后再矩阵求逆，得到最小二乘解。

四种最小二乘的比较

优化目标

对应解

$$\begin{array}{l}{\hat{x}}_{LS}=(A^{H}A{)}^{-1}{A}^{H}b\\ {\hat{x}}_{Tik}=(A^{H}A+\lambda I{)}^{-1}{A}^{H}b\\ {\hat{x}}_{TLS}=(A^{H}A-{\sigma }_{n+1}^{2}I{)}^{-1}{A}^{H}b\end{array}$$

总体最小二乘拟合直线

普通最小二乘考虑拟合误差平方和最小化,对于直线$m(x-\overline{x})+(y-\overline{y})=0$，代价函数为

$$\begin{array}{l}{D}_{LS}^{(1)}=\sum _{i=1}^n[(x_i-\overline{x})+m(y_i-\overline{y}){]}^2\\ D_{LS}^{(2)}=\sum _{i=1}^n[m(x_i-\overline{x})-(y_i-\overline{y}){]}^2\end{array}$$

对于若干数据点集，我们用直线ax+by+c=0拟合，，总体最小二乘考虑数据点距离平方和的最小化

$$D_{TLS}=\frac{\sum _{i=1}^n[a(x_i-\hat{x})+b(y_i-\hat{y}){]}^2}{a^2+b^2}$$

我们把D转化为单位向量t与M的乘积

对此，我们有定理，单位法向量$t=(a^2+b^2{)}^{-1/2}[a,b{]}^T$取矩阵$M^{t}M$的最小特征值$\lambda{min}$\mathrm{对}\mathrm{应}\mathrm{的}\mathrm{特}\mathrm{征}\mathrm{向}\mathrm{量}，\mathrm{距}\mathrm{离}\mathrm{平}\mathrm{方}\mathrm{和}\mathrm{取}\mathrm{最}\mathrm{小}\mathrm{值}$\lambda{min}$

$$D_{TSL}=\frac{(Mt{)}^{T}Mt}{||t|{|}_2^2}=\frac{t^T{M}^{T}Mt}{||t|{|}_2^2}$$

example

对于三个数据点(2,1),(2,4),(5,1)

$$\begin{array}{l}\overline{x}=\frac{1}{3}(2+2+5)=3\\ \overline{y}=\frac{1}{3}(1+4+1)=2\end{array}$$$$M=\left[\begin{array}{cc}2-3& 1-2\\ 2-3& 4-2\\ 5-3& 1-2\end{array}\right]=\left[\begin{array}{cc}-1& -1\\ -1& 2\\ 2& -1\end{array}\right]$$$$M^{T}M=\left[\begin{array}{cc}6& -3\\ -3& 6\end{array}\right]=\left[\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\end{array}\right]\left[\begin{array}{cc}9& 0\\ 0& 3\end{array}\right]\left[\begin{array}{cc}\frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\end{array}\right]$$

所以法向量$t=[1/\sqrt{2},1/\sqrt{2}{]}^T$
得到拟合直线为

$$\frac{1}{\sqrt{2}}(x-3)+\frac{1}{\sqrt{2}}(y-2)=0$$

距离平方和为

$$D_{TLS}=3$$

如果采用普通最小二乘

$$D_{LS}^{(1)}=\frac{1}{m^2+1}\sum _{i=1}^n[(x_i-\overline{x})+m(y_i-\overline{y}){]}^2$$$$\frac{\partial D_{LS}^{(1)}}{\partial m}=6m-3=0$$

平均约束的总体最小二乘

$$[A,b]\left[\begin{array}{c}x\\ -1\end{array}\right]=0\to Cx=0$$

考虑存在于增广矩阵中的噪声矩阵

$$D=[E,e]$$

引入校正矩阵,矩阵中每个列向量都与向量u相关

$$\mathrm{\Delta }C=[G_{1}u,G_{2}u...G_{n+1}u]\in R^{m\times (n+1)}$$

我们的问题转化为了约束优化问题

$$\underset{u,x}{min}{u}^{T}Wu$$$$s.t.(A+\mathrm{\Delta }A)x=b+\mathrm{\Delta }b$$$$[\mathrm{\Delta }A,\mathrm{\Delta }b]=[G_{1}u,G_{2}u...G_{n+1}u]$$

W为加权矩阵，通常为对角矩阵，或者单位矩阵

$$min||u|{|}_2^2$$