矩阵学习-QR分解和最小二乘问题求解

QR分解为矩阵分解的一种，在解决矩阵特征值计算和最小二乘问题中有很大的作用。

QR分解定理: 任意的一个满秩实(复)矩阵A，都可唯一的分解为(A=QR),其中(Q)为正交矩阵，(R)为正对角元的上三角矩阵

[ egin{cases} QQ^T=I \ \ R=left{egin{matrix} a_1 & * & * & cdots & * \ 0 & a_2 & * & cdots & * \ 0 & 0 & a_3 & cdots & *\ vdots & vdots & &ddots \ 0 & 0 & 0 & cdots &a_n end{matrix} ight} end{cases} ]

这里介绍一下基于HouseHolder变换的QR分解方法

1. HouseHolder变换介绍

HouseHolder变换可用于QR分解中，又称为反射变换或者为镜像变换，有明确的几何意义。
在(R^3)实数三维空间中，给定一个向量(alpha), 向量(eta)为(alpha)关于以(omega)为法向量的平面(pi)的反射变换所得。
有如下公式

[omega=frac{alpha-eta}{||alpha-eta||_2}in R^3 ]

[H(omega)=I-2omegaomega^T ]

则有 (H(omega)alpha=eta)
即：该变换将向量(alpha)变成了以(omega)为法向量的平面(pi)的对称向量(eta)

(H)矩阵有如下性质

• Hermite矩阵:(H^T=H)
• 酉矩阵:(H^T*H=I)，(H=(H^T)^{-1})
• 对合矩阵:(H*H=I)
• 自逆矩阵：(H=H^{-1})
• (diag(I,H))也是HouseHolder矩阵
• (det(H)=-1)

证明：略 ^_^

推论：

• 对于任意的在复数空间的向量 (xin C^n)，存在HouseHolder矩阵(H)，使得(Hx=ae_1),其中(|a|=left|x ight|_2),(ax^Te)为实数。
• 对于任意的在实数空间的向量 (xin R^n)，存在HouseHolder矩阵(H(omega)=I-2uu^T,(uin R^n,u^Tu=1))，使得(Hx=ae_1),其中(|a|=left|x ight|_2)

因此表明，HouseHolder变换可以将任意的向量(xin R^n)转换为与基向量(e)平行的共线向量

2. 利用HouseHolder变换的QR分解

此处介绍基于HouseHolder变换将矩阵进行QR分解，即(A=QR)

第1步

设有按列分块的矩阵(A=(alpha_1, alpha_2...alpha_n))

取

(omega_1=frac{alpha_1-a_1*e_1}{||alpha_1-a_1*e_1||_2}，a_1=||alpha_1||_2)

(H_1=I-2*omega_1*omega_1^T)

得到

[H_1A=(H_1alpha_1,H_1alpha_2，...，H_1alpha_n) =left{egin{matrix} a_1 & * & cdots & * \ 0 & \ vdots & &B_1 \ 0end{matrix} ight}]

第2步

从第一部得到矩阵(B_1=(eta_2,eta_2,cdots,eta_n)in R^{n-1})

取
(omega_2=frac{eta_2-b_2*e_1}{||eta_2-b_2*e_1||_2}，b_1=||eta_2||_2)

则 (widehat{H_2}=I-2*omega_2*omega_2^T,H_2=left{egin{matrix} 1 & 0^T \ 0 & widehat{H_2}， end{matrix} ight})

得到

[H_2(H_1*A) = left{egin{matrix} a_1 & * & * & cdots &* \ 0 & a_2 & * & cdots &* \ 0 & 0 & &\ vdots & vdots & &C_2& \ 0 & 0 end{matrix} ight}, C_2in R^{n-2}]

依次类推，进行第n步时，得到第n-1个(H_{n-1})阵,使得

[H_{n-1} cdots H_2H_1*A = left{egin{matrix} a_1 & * & * & cdots & * \ 0 & a_2 & * & cdots & * \ 0 & 0 & a_3 & cdots & *\ vdots & vdots & &ddots \ 0 & 0 & 0 & cdots &a_n end{matrix} ight}=R]

其中 (H_{n-1} cdots H_2H_1*A=H)也为HouseHolder矩阵，也为自逆矩阵 (H=H^{-1})

[H_{n-1} cdots H_2H_1*A=R ]

[Rightarrow (H_{n-1} cdots H_2*H_1)^{-1}*H_{n-1} cdots H_2H_1*A=(H_{n-1} cdots H_2*H_1)^{-1}*R ]

[Rightarrow A=H_1^{-1} cdots H_{n-1}^{-1}*R ]

[Rightarrow A=H_1cdots H_{n-1}*R ]

得到 (A=QR),其中(Q)为正交矩阵，(R)为上三角矩阵

[ egin{cases} Q = H_1cdots H_{n-1}\ R = Q^{-1}A=QA end{cases} ]

3. 最小二乘问题

最小二乘问题为最优化问题的一种，一般形式为

[minlimits_{x}{||f(x)||^2} ]

其中(f(x))为残差函数，表示预测值和测量值之差，(||f(x)||^2)为损失函数

3.1线性最小二乘问题

当(f(x)=Ax-b)为线性方程时，线性最小二乘问题为

[minlimits_{x}{||Ax-b||^2} ]

展开有

[h(x)=||Ax-b||^2=(Ax-b)^T*(Ax-b) ]

[h(x)=(Ax)^T(Ax)-b^TAx-(Ax)^Tb+b^Tb ]

求导有

[frac{partial h(x)}{partial x}=A^TAx-A^Tb ]

当导数为0时，得到损失函数值为最小值，因此

[A^TAx=A^Tb Rightarrow x=(A^TA)^{-1}A^Tb ]

3.2采用QR分解求解线性最小二乘问题

上述说明得到线性最小二乘问题(minlimits_{x}{||Ax-b||^2})的解为(x=(A^TA)^{-1}A^Tb)

但是这里由于要求矩阵倒数，计算上存在一定困难，这里如果采用QR分解可以使得问题简单很多。

首先对A进行QR分解，即(A=QR),其中(QQ^T=I),(R)为上三角矩阵

[x=(A^TA)^{-1}A^Tb ]

[(QR)^T(QR)x=(QR)^Tb ]

[R^TQ^TQRx=R^TQ^Tb ]

[Rx=Q^Tb ]

[x=R^{-1}Qb ]

其中 (R)为上三角矩阵,求逆相对容易很多，规避了直接对((A^TA)^{-1})求逆复杂度高的问题。

3.3非线性最小二乘问题

当(f(x))为非线性方程时，最小二乘问题为(minlimits_{x}{||f(x)||^2})。

一般来说求解非线性最小二乘问题有高斯牛顿法，Levenberg-Marquardt法,高斯牛顿法存在(H)不是正定矩阵时，迭代结果不收敛或者不准确的情况，因此LM算法表现较好。但这个先介绍下高斯牛顿法
设状态向量(x=(x_1,x_2,cdots,x_m))

[f(x)=egin{cases} f_1(x)\ f_2(x)\ vdots\ f_n(x) end{cases}]

一阶Tayor展开

[f(x+Delta x)=f(x)+J(x)Delta x ]

其中 (J(x))为Jacobian矩阵，表示为

[J(x)_{n*m}=left{egin{matrix} frac{partial f_1(x_1)}{partial x} & frac{partial f_1(x_2)}{partial x} & cdots & frac{partial f_1(x_m)}{partial x} \ frac{partial f_2(x_1)}{partial x} & frac{partial f_2(x_2)}{partial x} & cdots & frac{partial f_2(x_m)}{partial x} \ vdots\ frac{partial f_n(x_1)}{partial x} & frac{partial f_n(x_2)}{partial x} & cdots & frac{partial f_n(x_m)}{partial x} \ end{matrix} ight} ]

求解
(minlimits_{x}{||f(x)||^2}Rightarrowminlimits_{x}{||f(x)+J(x)Delta x||^2}),
类比线性最小二乘的方法

[Delta x=(J(x)^TJ(x))^{-1}*J(x)^T*f(x) ]

迭代 (x_{k+1}=x_k+Delta x)，直到收敛为止，即可求出最优解(x)

这里同样可以采用QR分解来求解(Delta x)

设QR分解得到 (J(x_k)=Q(x_k)R(x_k)),类比线性最小二乘方法，(Delta x=R(x_k)^{-1}Q(x_k)f(x_k))

因此非线性最小二乘问题迭代求解

[egin{cases} x_{k+1}=x_k+Delta x \ Delta x=R(x_k)^{-1}Q(x_k)f(x_k) end{cases}]