最小二乘法

最小二乘法（又称最小平方法）是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小。最小二乘法还可用于曲线拟合。其他一些优化问题也可通过最小化能量或最大化熵用最小二乘法来表达。

矩阵方程问题描述

基本问题描述

许多问题可以建模为矩阵方程形式：

$$\mathbf{A} \mathbf{x}=\mathbf{b}$$

其中根据向量$\mathbf{b} \in \mathbb{R}^{m \times 1}$ 和矩阵$\mathbf{A} \in \mathbb{R}^{m \times n}$的不同，矩阵方程的求解主要分为以下三类问题：

1. 超定矩阵方程 
m > n，b和A均已知，其中之一或二者可能存在观测误差、干扰；
2. 盲矩阵方程
仅向量b已知，矩阵A未知；
3. 欠定稀疏矩阵方程
m < n，b和A均已知。

每一类问题，都有对应的方法：如对于超定矩阵方程，观测结果足够多，方程个数大于未知数个数，对应矩阵通常列满秩（不绝对），可以利用最小二乘得到唯一确定解；对于欠定矩阵方程，方程个数小于未知数个数，得出的解有多种可能，所以通常需要添加约束——例如稀疏性，虽然解有多种，最稀疏的可能只用一种，这要就得到了唯一确定解。给出问题与对应求解的示意图：

对于欠定稀疏矩阵求解，核心问题为：

$$\min _{x}\|\mathbf{x}\|_{0} \quad \text { s.t. } \quad \mathbf{A x}=\mathbf{b}$$

这也是稀疏表示和压缩感知的核心问题，由于不免带有噪声，问题通常松弛为：

$$\min _{x}\|\mathbf{x}\|_{0} \quad \text { s.t. } \quad\|\mathbf{A} \mathbf{x}-\mathbf{b}\|_{2} \leq \varepsilon$$

最小二乘问题

最小二乘根据噪声类型的不同，可以分为：普通最小二乘、数据最小二乘、总体最小二乘。

• 普通最小二乘(Ordinary least squares,OLS)
  此时，向量b(观测向量)带有误差，对应的问题为： $$\mathbf{A} \mathbf{x}=\mathbf{b}+\Delta \mathbf{b} \Rightarrow \mathbf{A} \mathbf{x}=\mathbf{b}_{0}$$
• 数据最小二乘(Data least squares,DLS)
  此时，数据矩阵A带有误差，对应的问题是： $$(\mathbf{A}+\Delta \mathbf{A}) \mathbf{x}=\mathbf{b} \Rightarrow \mathbf{A} \mathbf{x}_{0}=\mathbf{b}$$
• 总体最小二乘(Total least squares,TLS)
  此时，数据矩阵A和数据矩阵A都带有误差，对应的问题是： $$(\mathbf{A}+\Delta \mathbf{A}) \mathbf{x}=\mathbf{b}+\Delta \mathbf{b} \Rightarrow \mathbf{A} \mathbf{x}_{0}=\mathbf{b}_{0}$$ 本文仅分析超定方程情况，且只讨论普通最小二乘问题。

普通最小二乘求解

问题描述：

$$\min _{x}\|\Delta \mathbf{b}\|^{2}=\min _{x}(\mathbf{A} \mathbf{x}-\mathbf{b})^{T}(\mathbf{A} \mathbf{x}-\mathbf{b})$$

其偏导为：

$$\mathbf{A}^{T} \mathbf{A} \mathbf{x}=\mathbf{A}^{T} \mathbf{b}$$

case1：列满秩，$\operatorname{rank}((\mathbf{A}))=n$
此时$\left(\mathbf{A}^{T} \mathbf{A}\right)$可逆，对应的解唯一，从而有：

$$\mathbf{x}_{O L S}=\left(\mathbf{A}^{T} \mathbf{A}\right)^{-1} \mathbf{A}^{T} \mathbf{b}$$

case2：秩亏缺，$\operatorname{rank}((\mathbf{A}))<n$
这种情况下，需要借助Moore-Penrose进行广义逆求解，从而有：

$$\mathbf{x}_{O L S}=\left(\mathbf{A}^{T} \mathbf{A}\right)^{\dagger} \mathbf{A}^{T} \mathbf{b}$$

秩亏缺情况下，得到的解不再是唯一的，但基于Moore-Penrose的解是唯一的，这就不免有一个问题——它是增加了何种约束？这里直接给出结论：此时的解为最小范数最小二乘解(minimum norm least squares solution)，或者说此时向量对应欧式距离最短.

普通最小二乘与最大似然

给出数学模型（以多项式拟合为例，N次拟合，共M组样本点）：

$$\left\{\begin{array}{l} a_{0}+a_{1} x_{1}+a_{2} x_{1}^{2}+\ldots a_{N} x_{1}^{N}-y_{1}=\varepsilon_{1} \\ a_{0}+a_{1} x_{2}+a_{2} x_{2}^{2}+\ldots a_{N} x_{2}^{N}-y_{2}=\varepsilon_{2} \\ \cdots \\ a_{0}+a_{1} x_{M}+a_{2} x_{M}^{2}+\ldots a_{N} x_{M}^{N}-y_{M}=\varepsilon_{M} \end{array}\right.$$

普通最小二乘准则函数：

$$J_{1}=\sum_{i=1}^{M}\left|f\left(x_{i}\right)-y_{i}\right|^{2}=\sum_{i=1}^{M}\left|\varepsilon_{i}\right|^{2}$$

最大似然准则：

假设误差均服从$\left(0, \delta^{2}\right)$的正态分布，则有似然函数：

$$L_{2}=\frac{1}{\sqrt{2 \pi} \delta} e^{-\frac{\varepsilon_{1}^{2}}{2 \delta^{2}}} \cdot \frac{1}{\sqrt{2 \pi} \delta} e^{-\frac{\varepsilon_{2}^{2}}{2 \delta^{2}}} \ldots \cdot \frac{1}{\sqrt{2 \pi} \delta} e^{-\frac{\varepsilon_{M}^{2}}{2 \delta^{2}}}$$

求对数之后，最大似然准则函数等价于：

$$J_{2}=\sum_{i=1}^{M}\left|\varepsilon_{i}^{2}\right|=\sum_{i=1}^{M}\left|\varepsilon_{i}\right|^{2}$$

二者等价。

最小二乘与梯度下降

上文一个大前提就是方程可以转化为线性变换：

$$\mathbf{A} \mathbf{x}=\mathbf{b}$$

但很多时候不能实现问题的转化，非线性没有闭式解，这个时候仍然可以借助梯度下降求解，梯度下降在前文有分析。梯度下降是迭代的方式去逼近最优解，虽然可能是局部最优；而最小二乘是利用矩阵的形式直接得出结果。