最小二乘问题

矩阵分解的应用,与线性回归等问题有着较为密切的联系.

给出一条直线,使得所有点和直线所预测的点的误差的平方和最小.

误差的平方和与2范数的关系

即$min_{k,b}\sum_{i=1}^n(kx_i+b-y_i)^2$

问题实质是求解线性回归的参数问题.

---

给出数据集$x_1,x_2,…,x_n$,和用于预测的函数$y=w^Tx+b$数据的个数为n,数据的维度为m;所以当数据构成组成矩阵$A_{m\times n}$的列.

即 arg($min_x||Ax-b||_2$)

---

$A_x-b$在这里代表的既是误差,又跟方程组$Ax=b$相联系

(1)当$Ax=b$有解时,如何确定$x_0$,

使得$||x_0||_2=min||x||_2$,为极小范数解

(2)当$Ax=b$无解时,给出无解时的极小范数最小二乘解.

有解时,确定x,满足其是解时,所有解中2范数最小的;

无解时,要确定x,使误差Ax-b的2范数是最小的.

---

最小二乘问题和方程组求解的联系

现代数值计算方法 北京大学出版社 主编：肖筱南
我帮你简单叙述下最小二乘法的概念
对于你所述的这种矛盾方程组 是工程上的常见问题
而用最小二乘法是为了得到一个解,使其在每个方程中的误差之和达到最小
但每个误差有正有负,因此我们就以“偏差的平方和最小”为原则
具体的计算方法为
设矩阵A为矛盾方程组的系数矩阵 b为其等号右边的数值矩阵
则方程组用矩阵可表示为AX=b
两边同时左乘A的转置矩阵
即$A（A^T）X=（A^T）b$ （T为上标,即A的转置）
再解这个方程组
得到的解即为最优近似解

定理1

线性最小二乘问题的解总是存在的,而且其解唯一的充分必要条件是null(A)=0;

记最小二乘问题的解为 $X_{LS}$, 即$X_{LS}$ = {*x *∈ Rn : x是 LS 问题(1)的解}

则由定理1知，XLS 总是非空的，而且它仅有一个元素的充分必要条件是 A 的列线性无关。

此外，不难证明，解集中有且仅有一个解其 2 范数最小，我们用 x**LS 表示之，并称其为最小范数解。

定理2

x属于最小二乘的解集,

$A^TAx=A^Tb$;

---

如何理解最小二乘法?

最小二乘法的本质是什么？ - 马同学的回答 - 知乎 https://www.zhihu.com/question/37031188/answer/411760828

---

正规化方法求最小二乘问题

A的广义逆:如果矩阵A是列满rank的话,那么A的广义逆是

$(A^TA)^{-1}A^T$;

故最小二乘问题的解x可表示为x=A的广义逆b.

道，如果目标函数是可微，具有凸性并且问题

是没有约束的，最优点由条件 ∇f(x) = 0 决定。在我们这种情况下，函数 f 在一点 x 处的梯度是非常容易看出是 $∇f(x) = A^T(Ax-b)$.

QR分解法求最小二乘问题

正交变换保持向量长度的不变性:2范数的意义之下.

$||Qx||_2$=$||x||_2$;

1. 首先将A进行正交分解.$A_{m\times n}=Q\begin{pmatrix}R^{n\times n}\O \end{pmatrix}$

2. $||Ax-b||_2=||QRx-b||_2=||Q||_2||\begin{pmatrix}R^{n\times n}\O \end{pmatrix}x-Q^Tb||_2$

   在这里为了保持形式的统一,将b拆成$b_1和b_2$两部分.

3. arg(min||AX-b||_2)=min(Rx-b_1)

4. 根据最小二乘与方程组的联系,只需要求$Rx=b_1$的解.

在计算机中一般使用基于 Householder 变换的 QR 分解，该算法有良好地数值性态，结果通

常要比正则化方法精确。但是运算量也比较大，大约为 $2mn^2 -2n^3/3 $,我们也可以使用 Givens 变换来实现 QR 分解，所需的运算量大约是 Householder 方法地两倍，但是如果 *A** 有较多的零元素，则灵活地使用 Givens 变换会使运算量大为减少.

奇异值分解法求解最小二乘的问题

欠定问题的最小范数解


1. 加权最小二乘,某些方程的残差项是需要拥有权重的.

2. 约束最小二乘,在min的同时,也有Bx=f的约束条件.

3. 总体最小二乘,数据矩阵和数据向量都有误差,不仅用校正向量$\Delta b$去干扰数据向量b,同时用校正矩阵$\Delta A$去干扰数据矩阵A,以便对A和b二者内存在的误差或噪声进行联合补偿.

   自然地，我们希望矫正数据矩阵和校正数据向量都尽量小。因此，总体最小二乘问题可以

   用约束优化问题叙述为：

   $min_{\Delta A,\Delta b},{x||\Delta A,\Delta b||_F^2=||\Delta A||_F^2+||\Delta b||_2^2}$

   subject to (A + ∆A)x = b + ∆b;

   约束条件有时也表示为 (b + ∆b) ∈ Col(A + ∆A)

最小二乘问题的解的敏感性

这个定理告诉我们，在考虑 x 的相差误差时，若 b 有变化。只有它在 Col(A) 上的投影会对解产生影响。此外，这个定理还告诉我们，最小二乘问题之解的敏感性依赖于数 κ2(A)的大小。因此，我们称它为最小二乘问题的条件数。若 κ2(A) 很大，则称最小二乘问题是病态的；否则称为良态的。

赏

谢谢你请我吃糖果❤️

支付宝