零、任务背景和定义

1. 列向量形态的任务

给定向量 $\boldsymbol b \in \R ^{N \times 1}+$ 和 $\boldsymbol A \in \R^{N \times R}+$，请你找到 $\boldsymbol x \in \R^{R \times 1}_+$ 使得：$\boldsymbol A \boldsymbol x \approx \boldsymbol b$。
- 一般情况下，$\boldsymbol A$ 各列相互独立，且 $R<N$，如下图所示。这种时候 $\boldsymbol b$ 不太可能能由 $\boldsymbol A$ 的列向量组线性表出，故 $\boldsymbol A \boldsymbol x =\boldsymbol b$ 是一个矛盾方程组，只能尽量让二者差距比较小。
- 因而只能取一种衡量 $\boldsymbol A \boldsymbol x$ 与 $\boldsymbol b$ 接近程度的距离函数 $d(\boldsymbol u, \boldsymbol v)$，在此基础上选出最优的 $\boldsymbol x$，也就是 $L(\boldsymbol x) = d( \boldsymbol A \boldsymbol x, \boldsymbol b)$：
  
  $$ \boldsymbol x^* = \argmin_{\boldsymbol x \in \R^{R \times 1}+} L(\boldsymbol x)= \argmin{\boldsymbol x \in \R^{R \times 1}_+} d(\boldsymbol A \boldsymbol x, \boldsymbol b) $$
- 距离函数 $d$ 可以是：
  1. 最小二乘距离：
    
    $$ d_2(\boldsymbol u, \boldsymbol v) = \| \boldsymbol u -\boldsymbol v \|^2 $$
  2. KL 散度 (Kullback-Leibler Divergence)：
    
    $$ d_{\rm KL}(\boldsymbol u, \boldsymbol v) = \sum_{i=1}^N \left( u_i \ln \frac {u_i}{v_i} + v_i - u_i \right) $$
    - 请注意 $d_{\rm KL}(\boldsymbol u, \boldsymbol v)$ 对 $\boldsymbol u, \boldsymbol v$ 不满足对称性；也不满足三角不等式。
    与原始的 KL 散度的区别：
    - 原始的 KL 散度定义是对于指定空间 ${\mathcal X}$ 上的两个概率分布 $P(x), Q(x)$ 指出的，表征的是基于 $Q$ 的编码来编码来自 $P$ 的样本平均所需的额外的比特个数：
      
      $$ d_{\rm KL} (P, Q) = \sum_{x \in {\mathcal X}} P(x) \ln \frac {P(x)}{Q(x)} $$
    - 既然是概率分布就要求 $\sum_{x\in {\mathcal X}} P(x) = \sum_{x\in {\mathcal X}} Q(x) = 1$，但是将 $P, Q$ 转化为非负向量 $\boldsymbol u, \boldsymbol v$ 后，就不满足归一化条件了。因而添加了 $v_i - u_i$ 的校正项目来推广。至少它能保证 $\boldsymbol u, \boldsymbol v$ 在 $\boldsymbol 1 ^{\rm T} \boldsymbol u = \boldsymbol 1 ^{\rm T} \boldsymbol v = 1$ 时可以等同。
      
      但我觉得更自然的一种推广是 $\boldsymbol p = \frac {\boldsymbol u}{\boldsymbol 1^{\rm T} \boldsymbol u}$ 和 $\boldsymbol q = \frac {\boldsymbol v}{\boldsymbol 1^{\rm T} \boldsymbol v}$ 归一化后代入。展开的结果是：
      
      $$ d_{\rm KL}(\boldsymbol u, \boldsymbol v) = \frac {1}{\boldsymbol 1 ^{\rm T} \boldsymbol u}\sum_{i=1}^N \left( u_i \ln \frac {u_i}{v_i} + \ln \boldsymbol 1 ^{\rm T} \boldsymbol v - \ln\boldsymbol 1 ^{\rm T} \boldsymbol u \right) $$
    - 【具体的介绍可展开】

2. 矩阵形态任务

给定向量 $\boldsymbol B \in \R ^{N \times M}+$ 和 $\boldsymbol A \in \R^{N \times R}+$，请你找到 $\boldsymbol X \in \R^{R \times M}_+$ 使得：$\boldsymbol A \boldsymbol X \approx \boldsymbol B$。
可以将问题分解为多个列向量任务：

$$ \forall i \in [1, M] \cap \Z, \ \boldsymbol A \boldsymbol x_i = \boldsymbol b_i, $$
因而如果距离函数 $d$ 也能相应拆分，那么各个列任务就是相互独立的，$\boldsymbol x_i$ 都各自取最小也就能取到整体 $\boldsymbol X$ 的最小。比如矩阵的 F- 范数（平方和）和推广到非负矩阵的 KL 散度都是可以拆分的。
因而后面只需要讨论列向量形态的任务。

一、最小二乘优化问题

1. 凸优化问题的证明

下面要证明这个优化问题是一个凸优化问题，就可以优化了。
首先要证明，损失函数 $L(\boldsymbol x) = \| \boldsymbol A \boldsymbol x -\boldsymbol b \|^2$ 是一个凸函数。

$$ \begin{align*}

{\rm d} L(\boldsymbol x)

&= 2(\boldsymbol A \boldsymbol x - \boldsymbol b)^{\rm T} {\rm d} (\boldsymbol A \boldsymbol x - \boldsymbol b) \\

&= 2(\boldsymbol A \boldsymbol x - \boldsymbol b)^{\rm T} \boldsymbol A {\rm d} \boldsymbol x

\end{align*} \\

\begin{align*}

\frac {{\rm d} L(\boldsymbol x)}{{\rm d} \boldsymbol x}

&= 2((\boldsymbol A \boldsymbol x - \boldsymbol b)^{\rm T} \boldsymbol A)^{\rm T} \\

&= 2\boldsymbol A^{\rm T} (\boldsymbol A \boldsymbol x - \boldsymbol b)

\end{align*} \\

\frac {{\rm d}^2 L(\boldsymbol x)}{{\rm d} \boldsymbol x} = 2\boldsymbol A^{\rm T} \boldsymbol A {\rm d} \boldsymbol x \\

\frac {{\rm d}^2 L(\boldsymbol x)}{{\rm d} \boldsymbol x^2} = 2(\boldsymbol A^{\rm T} \boldsymbol A)^{\rm T} = 2\boldsymbol A^{\rm T} \boldsymbol A $$
- $\boldsymbol A^{\rm T} \boldsymbol A$ 一定是半正定矩阵，因而是下凸函数；如果 $\boldsymbol A$ 还是列满秩矩阵，$\boldsymbol A^{\rm T} \boldsymbol A$ 是正定矩阵，这时是严格下凸函数。
如果没有对 $\boldsymbol x$ 各元素非负（记为 $\boldsymbol x \ge \boldsymbol 0$）的约束：
- 直接驻点 $\frac {{\rm d} L(\boldsymbol x)}{{\rm d} \boldsymbol x} = \boldsymbol 0$ 处就是最优解，即 $\boldsymbol A^{\rm T} \boldsymbol A \boldsymbol x^* = \boldsymbol A^{\rm T} \boldsymbol b$。这时候是有解析解的：
  - 当 $\boldsymbol A$ 还是列满秩矩阵，$\boldsymbol x^* = (\boldsymbol A^{\rm T} \boldsymbol A)^{-1}\boldsymbol A^{\rm T} \boldsymbol b$。
  - 否则 $\boldsymbol A^{\rm T} \boldsymbol A$ 不可逆，这时候只可能是相容方程组，不会是矛盾方程组。这是因为 $\boldsymbol A^{\rm T} \boldsymbol b$ 始终在 $\boldsymbol A^{\rm T} \boldsymbol A$ 列空间内。因而通过求伪逆 $\boldsymbol x^* = (\boldsymbol A^{\rm T} \boldsymbol A)^+\boldsymbol A^{\rm T} \boldsymbol b$ 逼近最小范数解（见链接中的证明）。
    
    [第A3b章] 广义逆矩阵 · 应用广义逆矩阵解方程
  为什么 $\boldsymbol A^{\rm T} \boldsymbol b$ 始终在 $\boldsymbol A^{\rm T} \boldsymbol A$ 列空间内
  - $\boldsymbol A^{\rm T} \boldsymbol b \in {\rm Col} (\boldsymbol A^{\rm T})$，因为它可以视为投影。
  - ${\rm Col} (\boldsymbol A^{\rm T}) = {\rm Col} (\boldsymbol A^{\rm T}\boldsymbol A)$。因为首先同理 ${\rm Col} (\boldsymbol A^{\rm T} \boldsymbol A) \subseteq {\rm Col} (\boldsymbol A^{\rm T})$；其次有 ${\rm r} (\boldsymbol A^{\rm T} \boldsymbol A) = {\rm r} (\boldsymbol A^{\rm T})$（见链接）。
    
    [第五章] 线性方程组与零空间
- 然而我们具有 $\boldsymbol x \ge \boldsymbol 0$ 约束，因而这种方法不太可行。
不过 $\boldsymbol x \ge \boldsymbol 0$ 约束是一个凸集，因而对凸函数的凸集约束仍然是一个凸优化问题。

2. 梯度下降优化法

既然是一个凸函数，梯度下降法一定可以向最优解下降：

$$ \boldsymbol x \leftarrow \boldsymbol x +\Delta \boldsymbol x, \ \ \Delta \boldsymbol x = -\alpha \frac {{\rm d} L(\boldsymbol x)}{{\rm d} \boldsymbol x} = -2\alpha\boldsymbol A^{\rm T} (\boldsymbol A \boldsymbol x - \boldsymbol b) $$
- 其中 $\alpha$ 是学习率。