1. 概述

当我们需要根据一堆数据点去拟合出一条近似的直线的时候,就会用到 最小二乘法 .根据矩阵A的情况,有如下四种方法

  • 在r = n = m 时,SVD奇异值分解, A = U Σ V T A=U\Sigma V^T A=UΣVT,伪逆矩阵 A + = V Σ − 1 U T A^{+}=V\Sigma^{-1}U^T A+=VΣ1UT
  • 在矩阵A列满秩的情况下(r=n),直接用方程 A T A x ^ = A T b → x ^ = ( A T A ) − 1 A T b A^TA\hat{x}=A^Tb\rightarrow \hat{x}=(A^TA)^{-1}A^Tb ATAx^=ATbx^=(ATA)1ATb
  • 在条件数 σ 1 σ r \frac{\sigma_1}{\sigma_r} σrσ1太大时,通过Gram-Schmidt生成一个正交列向量, A = Q R → x ^ = R − 1 Q T b A=QR\rightarrow \hat{x}=R^{-1}Q^Tb A=QRx^=R1QTb,通过消除后得到可以求逆的 R − 1 R^{-1} R1
  • 加惩罚项, ( A T A + δ 2 I ) x ^ = A T b → x ^ = ( A T A + δ 2 I ) − 1 A T b (A^TA+\delta ^2 I)\hat{x}=A^Tb\rightarrow \hat{x}=(A^TA+\delta ^2 I)^{-1}A^Tb (ATA+δ2I)x^=ATbx^=(ATA+δ2I)1ATb,通过在对角线上加一个趋近于0的 δ 2 \delta ^2 δ2保证矩阵 ( A T A + δ 2 I ) (A^TA+\delta ^2 I) (ATA+δ2I)可逆,这样通过方程就可以得到想要的 x ^ \hat{x} x^

2. SVD奇异值分解

假设我们矩阵A可逆,那么我们就可以直接得到矩阵A的逆,那么此时的矩阵A的伪逆就等于矩阵A的逆
当矩阵 A 可逆 → A + = A − 1 \begin{equation} 当矩阵A可逆\rightarrow A^{+}=A^{-1} \end{equation} 当矩阵A可逆A+=A1
将矩阵A通过奇异值SVD分解可得如下:
A = U Σ V T , A T = V Σ T U T \begin{equation} A=U\Sigma V^T,A^T=V\Sigma^TU^T \end{equation} A=UΣVT,AT=VΣTUT

  • 得到 A A T , A T A AA^T,A^TA AAT,ATA
    A A T = U Σ Σ T U T , A T A = V Σ T Σ V T \begin{equation} AA^T=U\Sigma\Sigma^T U^T,A^TA=V\Sigma^T\Sigma V^T \end{equation} AAT=UΣΣTUT,ATA=VΣTΣVT
  • A A T AA^T AAT可以看出矩阵A右乘以 A T A^T AT,所以得到结果为列空间向量,所以U为列空间基;同理 A T A A^TA ATA可以看出矩阵A左乘以 A T A^T AT,所以结果为行空间向量,所以V为行空间基。那么我们可以通过 A v i = σ i u i Av_i=\sigma_i u_i Avi=σiui来对看作是行空间基 v i v_i vi 通过 A v i Av_i Avi变换后直接得到列空间基 σ i u i \sigma_i u_i σiui,同理可得, A T u i = σ i v i A^Tu_i=\sigma_i v_i ATui=σivi可以看作是列空间基 u i u_i ui,通过 A T u i A^Tu_i ATui变换后直接得到行空间基 σ i v i \sigma_i v_i σivi,那么对于行空间(r个基向量)和列空间(r个基向量)之间可以通过 A , A T A,A^T A,AT进行转换
    A v i = σ i u i , A T u i = σ i v i → A + = A T \begin{equation} Av_i=\sigma_iu_i,A^Tu_i=\sigma_iv_i\rightarrow A^{+}=A^T \end{equation} Avi=σiui,ATui=σiviA+=AT
    在这里插入图片描述
  • 通过奇异值分解可得:
    A = U Σ V T = [ u 1 u 2 ⋯ u m ] [ σ 1 σ 2 ⋱ σ r 0 ] [ v 1 T v 2 T ⋮ v n T ] \begin{equation} A=U\Sigma V^T=\begin{bmatrix}u_1&u_2&\cdots &u_m\end{bmatrix}\begin{bmatrix}\sigma_1\\\\&\sigma_2\\\\&&\ddots\\\\&&&\sigma_r\\\\&&&&0\end{bmatrix}\begin{bmatrix}v_1^T\\\\v_2^T\\\\\vdots \\\\v_n^T\end{bmatrix} \end{equation} A=UΣVT=[u1u2um] σ1σ2σr0 v1Tv2TvnT
  • 将矩阵A求逆可得:
    A − 1 = V Σ − 1 U T = V [ σ 1 − 1 σ 2 − 1 ⋱ σ r − 1 0 − 1 ] U T \begin{equation} A^{-1}=V\Sigma^{-1} U^T=V\begin{bmatrix}\sigma_1^{-1}\\\\&\sigma_2^{-1}\\\\&&\ddots\\\\&&&\sigma_r^{-1}\\\\&&&&0^{-1}\end{bmatrix}U^T \end{equation} A1=VΣ1UT=V σ11σ21σr101 UT
    Σ Σ − 1 = [ 1 1 ⋱ 1 0 ⋱ 0 ] \begin{equation} \Sigma\Sigma^{-1}=\begin{bmatrix}1\\\\&1\\\\&&\ddots\\\\&&&1\\\\&&&&0\\\\&&&&&\ddots\\\\&&&&&&0\end{bmatrix} \end{equation} ΣΣ1= 11100
  • 我们发现 0 − 1 0^{-1} 01根本不存在,所以奇异值分解直接求伪逆 A − 1 A^{-1} A1也出问题了。出问题的点在于对于特征值为0时候,无法求0的倒数,那就是所如果我们不用零空间的向量和其0特征值,只有行和列空间里面的向量,那么就没这个问题了,这就是Gram-Schmidt的思路,从矩阵A的列空间中挑选向量u_1,其他向量 m 1 m_1 m1 不是列空间的,那就通过正交化Gram-Schmidt 将其变换为 m 1 → u 2 m_1\rightarrow u_2 m1u2,这样我们就能得到一个可逆矩阵M,这样我们就能通过公式 M − 1 M^{-1} M1直接计算所需要的 x ^ \hat{x} x^

3. 最小二乘法方程解

我们知道,当我们有一个方程 A x = b Ax=b Ax=b时,我们得到的是一堆数据点,我们需要拟合一个直线,使得 ∣ ∣ A x ^ − b ∣ ∣ 2 2 = ( A x ^ − b ) 2 ||A\hat{x}-b||_2^2=(A\hat{x}-b)^2 ∣∣Ax^b22=(Ax^b)2 值最小,所以我们得到如下方程:
y = ( A x − b ) 2 = ( A x − b ) T ( A x − b ) = ( x T A T − b T ) ( A x − b ) \begin{equation} y=(Ax-b)^2=(Ax-b)^T(Ax-b)=(x^TA^T-b^T)(Ax-b) \end{equation} y=(Axb)2=(Axb)T(Axb)=(xTATbT)(Axb)

  • 整理可得:
    y = x T A T A x − x T A T b − b T A x + b T b \begin{equation} y=x^TA^TAx-x^TA^Tb-b^TAx+b^Tb \end{equation} y=xTATAxxTATbbTAx+bTb
  • 因为 b T A x b^TAx bTAx为常数,所以得到 x T A T b = b T A x x^TA^Tb=b^TAx xTATb=bTAx
    y = x T A T A x − 2 b T A x + b T b → ∂ y ∂ x = ∂ x T A T A x ∂ x − 2 ∂ b T A x ∂ x \begin{equation} y=x^TA^TAx-2b^TAx+b^Tb\rightarrow \frac{\partial y}{\partial x}= \frac{\partial x^TA^TAx}{\partial x}-2 \frac{\partial b^TAx}{\partial x} \end{equation} y=xTATAx2bTAx+bTbxy=xxTATAx2xbTAx
  • 根据矩阵求导可得,注意转置符号,别漏了
    ∂ x T A T A x ∂ x = 2 A T A x ; − 2 ∂ b T A x ∂ x = A T b \begin{equation} \frac{\partial x^TA^TAx}{\partial x}=2A^TAx;-2 \frac{\partial b^TAx}{\partial x}=A^Tb \end{equation} xxTATAx=2ATAx;2xbTAx=ATb
  • 所以求导公式可以整理得到:
    ∂ y ∂ x = 2 A T A x − 2 A T b = 0 → A T A x ^ = A T b \begin{equation} \frac{\partial y}{\partial x}=2A^TAx-2A^Tb=0\rightarrow A^TA\hat{x}=A^Tb \end{equation} xy=2ATAx2ATb=0ATAx^=ATb
  • 是不是很神奇,用矩阵求导得到的结果,居然是跟我们用投影法一样的,如果要满足求出上述的 x ^ \hat{x} x^,也就需要 A T A A^TA ATA 可逆,也就是需要矩阵A满秩,所以跟以前对上来了。
  • 当矩阵A列满秩,所以 A T A A^TA ATA 可逆,方程有解如下:
    x ^ = ( A T A ) − 1 A T b \begin{equation} \hat{x}=(A^TA)^{-1}A^Tb \end{equation} x^=(ATA)1ATb

4. 最小二乘法图像解释

假设我们有一个矩阵A和方程 A x = b Ax=b Ax=b,求解最优 b ^ \hat{b} b^?

  • 从四个子空间可以看出,我们画出任意向量b,如下图所示:
    当我们要求的向量b不在由矩阵A的列向量组成的空间时候,我们其实无法得到正确的解,那么怎么办呢?如果我们将向量b分解,一部分通过投影可得向量 p = A x ^ p=A\hat{x} p=Ax^,其在矩阵A的列空间中,另外一部分就是e= A x − b Ax-b Axb,只有投影上去了,我们才能够根据向量p来求得近似的解 x ^ \hat{x} x^
    在这里插入图片描述

5. Gram-Schmidt

Gram-Schmidt 的作用是将矩阵A进行正交分解为 A = Q R A=QR A=QR,本身也是通过投影后相减得到垂直向量,这样通过Gram-Schmidt 变换后的矩阵都正交,得到一个可逆矩阵Q和R
A = Q R , A T = R T Q T , A T A x ^ = A T b → R T Q T Q R x ^ = R T Q T b → R x ^ = Q T b \begin{equation} A=QR,A^T=R^TQ^T,A^TA\hat{x}=A^Tb\rightarrow R^TQ^TQR\hat{x}=R^TQ^Tb\rightarrow R\hat{x}=Q^Tb \end{equation} A=QR,AT=RTQT,ATAx^=ATbRTQTQRx^=RTQTbRx^=QTb

  • 整理可得:
    x ^ = R − 1 Q T b \begin{equation} \hat{x}=R^{-1}Q^Tb \end{equation} x^=R1QTb

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部