最小二乘（Least Square）与多项式拟合（fitted polynomial）的理解

最小二乘（Least Square）与多项式拟合（fitted polynomial）的理解

多项式：
$$f(x_i)={\theta }_0+{\theta }_1{x}_i+{\theta }_2{x_i}^2+\cdots +{\theta }_n{x_i}^n$$

存在样本：
$$(x_1,y_1),(x_2,y_2),\cdots ,(x_m,y_m)$$

样本值代入多项式得方程组：
{ θ 0 + θ 1 x 1 + θ 2 x 1 2 + ⋯ + θ n x 1 n = y 1 θ 0 + θ 1 x 2 + θ 2 x 2 2 + ⋯ + θ n x 2 n = y 2 ⋮ θ 0 + θ 1 x m + θ 2 x m 2 + ⋯ + θ n x m n = y m \begin{dcases} \theta_0 + \theta_1x_1+\theta_2{x_1}^2+\cdots+\theta_n{x_1}^n=y_1 \\ \theta_0 + \theta_1x_2+\theta_2{x_2}^2+\cdots+\theta_n{x_2}^n=y_2 \\ \vdots \\ \theta_0 + \theta_1x_m+\theta_2{x_m}^2+\cdots+\theta_n{x_m}^n=y_m \end{dcases}

⎩ ⎨ ⎧​θ0​+θ1​x1​+θ2​x1​2+⋯+θn​x1​n=y1​θ0​+θ1​x2​+θ2​x2​2+⋯+θn​x2​n=y2​⋮θ0​+θ1​xm​+θ2​xm​2+⋯+θn​xm​n=ym​​

$令$
θ = [ θ 0 θ 1 θ 2 ⋯ θ n ] T \theta = [θ0θ1θ2⋯θn]

^T θ=[θ0​​θ1​​θ2​​⋯​θn​​]T
$$A_i=\left[\begin{array}{ccccc}1& x_i& x_i^2& \cdots & x_i^m\end{array}\right]$$
$$b_i=y_i$$
$$i=1，\cdots ，m$$

$则方程组变换为：$
{ A 1 θ = b 1 A 2 θ = b 2 ⋮ A m θ = b m \begin{dcases} A_1\theta=b_1 \\ A_2\theta=b_2 \\ \vdots \\ A_m\theta=b_m \\ \end{dcases}

⎩ ⎨ ⎧​A1​θ=b1​A2​θ=b2​⋮Am​θ=bm​​

$令$
A = [ A 1 A 2 A 3 ⋮ A m ] A=[A1A2A3⋮Am]

A=⎣ ⎡​A1​A2​A3​⋮Am​​⎦ ⎤​
$$b=\left[\begin{array}{c}{b}_1\\ b_2\\ b_3\\ ⋮\\ b_m\end{array}\right]$$

方程组变换为矩阵方程式：
$$A\theta =b$$
A = [ a 1 a 2 a 3 ⋯ a n ] = [ 1 x 1 x 1 2 ⋯ x 1 n 1 x 2 x 2 2 ⋯ x 2 n ⋮ ⋮ ⋮ ⋱ ⋮ 1 x m x m 2 ⋯ x m n ] , θ = [ θ 0 θ 1 θ 2 ⋮ θ n ] , b = [ y 0 y 1 y 2 ⋮ y m ] A=[a1a2a3⋯an]

=[1x1x21⋯xn11x2x22⋯xn2⋮⋮⋮⋱⋮1xmx2m⋯xnm], \theta=[θ0θ1θ2⋮θn], b=[y0y1y2⋮ym] A=[a1​​a2​​a3​​⋯​an​​]=⎣ ⎡​11⋮1​x1​x2​⋮xm​​x12​x22​⋮xm2​​⋯⋯⋱⋯​x1n​x2n​⋮xmn​​⎦ ⎤​,θ=⎣ ⎡​θ0​θ1​θ2​⋮θn​​⎦ ⎤​,b=⎣ ⎡​y0​y1​y2​⋮ym​​⎦ ⎤​

$考虑A\theta =b无解，需要从A的列空间中找出最接近b的向量p（p可以理解为b在A的列空间中的投影，理解如下图所示：）$

如上图所示， p 是 b 在 [ a 1 a 2 ] 列空间中的投影。 如上图所示，p是b在[a1a2]

列空间中的投影。 如上图所示，p是b在[a1​​a2​​]列空间中的投影。
$令e=b-p，最小二乘就是找到\parallel e{\parallel }^2最小的点，最小二乘就是指向量长度的最小平方。$

$由上可知，p位于A的列空间中，即p是A的各列的线性组合：$
$$p=a_1\widetilde{{\theta }_1}+a_2\widetilde{{\theta }_2}+\cdots +a_n\widetilde{{\theta }_n}$$
$即A\tilde{\theta }=p有解。$

$$e=b-p=b-A\tilde{\theta }$$
$e正交于A的列空间，存在：$
$$e\perp a_1,e\perp a_2,\cdots ,e\perp a_n$$

⇒ { a 1 T ( b − A θ ~ ) = 0 a 2 T ( b − A θ ~ ) = 0 ⋮ a n T ( b − A θ ~ ) = 0 \Rarr \begin{dcases} a_1^T(b-A\tilde{\theta})=0 \\ a_2^T(b-A\tilde{\theta})=0 \\ \vdots \\ a_n^T(b-A\tilde{\theta})=0 \end{dcases}

⇒⎩ ⎨ ⎧​a1T​(b−Aθ~)=0a2T​(b−Aθ~)=0⋮anT​(b−Aθ~)=0​

⇒ [ a 1 T a 2 T a 3 T ⋮ a n T ] ( b − A θ ~ ) = [ 0 0 0 ⋮ 0 ] \Rarr [aT1aT2aT3⋮aTn]

(b-A\tilde{\theta})= [000⋮0] ⇒⎣ ⎡​a1T​a2T​a3T​⋮anT​​⎦ ⎤​(b−Aθ~)=⎣ ⎡​000⋮0​⎦ ⎤​

$$\Rightarrow A^T(b-A\tilde{\theta })=0$$
$$\Rightarrow A^{T}A\tilde{\theta }=A^{T}b$$
$$\Rightarrow \tilde{\theta }=(A^{T}A{)}^{-1}{A}^{T}b$$

$上述式子是\boxed{矩阵法}求解推导公式。$
$此外还有\boxed{正规方程法}，\boxed{householderQr分解法}，\boxed{bdcSvd分解法}。$
针对最小二乘几个方法的应用情况：
Eigen 官网在 Solving linear least squares systems 章节中讨论了 SVD 分解、QR 分解和正规方程（即使用 LDLT 解法）三种方法在求解线性最小二乘问题上的差异，并指出：SVD 分解通常精度最高但速度最慢，正规方程速度最快但精度最差，QR 分解性能介于两种方法之间。相比 SVD 分解和 QR 分解，当矩阵 病态时，正规方程解法所得结果将损失两倍精度。

参考：
1、https://zhuanlan.zhihu.com/p/268884807