坐标下降法坐标下降法

坐标下降法 【坐标下降法】本文讲解如何使用坐标下降法求解最小二乘问题。
原理假设 \(A\in \mathbb{R}^{N\times K}\)，\(b\in \mathbb{R}^N\)，求 \(x = [x_1, \cdots, x_K]^T\in \mathbb{R}^K\)，使得

\[\lVert b - Ax\rVert_2 \]
极小化。
坐标下降法的想法是一次只更新一个分量，假设更新第 \(k\) 个分量 \(x_k\)，即要求一个 \(s\)，

\[x_k \leftarrow x_k + s \]
用以更新 \(x_k\)。怎么选取这个 \(s\) 呢？当然是选可以使损失函数取得最小值的那个 \(s\)。
记更新后的损失函数为

\[g^k(s) = \lVert b - A[x_1, \cdots, x_k+s, \cdots, x_K]^T\rVert_2^2 = \sum_{i=1}^N \bigg( e_i - sA_{ik} \bigg)^2 \]
其中 \(e=b-Ax\in \mathbb{R}^N\)。由于 \(g^k\) 是二次函数，Taylor 展开后与其自身相等，即有

\[g^k(s) = g^k(0) + (g^k)'(0) s+ \frac12 (g^k)''(0)s^2, \]
其极小点为

\[s^{*} = -\frac{(g^k)'(0)}{(g^k)''(0)}. \]
因此可以更新 \(x_k\),

\[x_k \leftarrow x_k + s^{*}. \]
另外，简单计算可知一阶导数和二阶导数在 \(0\) 处的取值为

\[\left\{ \begin{aligned} (g^k)'(0) &= -2\sum_{i=1}^{N}e_iA_{ik} \\ (g^k)''(0) &= 2 \sum_{i=1}^{N}A_{ik}^2 \end{aligned} \right. \]
伪代码上面讲了坐标下降法的原理，写成伪代码如下：

输入：系数矩阵 \(A\in \mathbb{R}^{N\times K}\)，标签向量 \(b\in \mathbb{R}^N\)
过程：

初始化 \(x\in \mathbb{R}^K\)；

计算初始误差：\(e = b - Ax\)；

提前计算每个分量处的二阶导数：\(h (k) = 2\sum_{i=1}^{N}A_{ik}^2\)；

while 达到收敛条件：

选取 \(k \in \{1, ..., K\}\) :
* 计算一阶导数：\(g = -2\sum_{i=1}^Ne_i A_{ik}\)；
* 计算极小点：\(s^{*} = \frac{g}{h (k)}\)；
* 坐标更新：\(x_k = x_k + s^{*}\)；
* 更新误差：\(e_i = e_i - s^{*} A_{ik}, \quad i=1, \cdots, N\)；

输出：\(x\in \mathbb{R}^K\)。