最小二乘法：
W = L(\alpha_1, \cdots, \alpha_s) 为 \mathbb R 上的欧式空间 V 的子空间，\lambda \in W，则对于任意的 \beta \in V，有：
\forall \, \delta \in W,\; ||\beta - \lambda|| \leq ||\beta - \delta|| \Longleftrightarrow \beta \, \bot \, W
即向量到子空间各向量间的距离以垂线为最短。

下面的 Q 表示待求解的问题，A 代表求解方法：

求解线性方程组

• Q_1：
  \begin{aligned} &AX = b \\ &\text{其中} A \in {\mathbb R}^{m \times n} ;\; X \in {\mathbb R}^{n \times 1} ;\; b \in {\mathbb R}^{m \times 1} \end{aligned}

• A_1：
  令 A = (\alpha_1, \cdots, \alpha_n), X = (x_1, \cdots, x_n)^{T}，则有 Y = AX = x_1 \alpha_1 + \cdots + x_n \alpha_n，即 Y \in L(\alpha_1, \cdots, \alpha_n)，这样 Q_1 便可转化为最小二乘问题：

• Q_1^1：
  \begin{aligned} &\displaystyle\min_{Y} ||Y - b|| \Longleftrightarrow b - Y \,\bot \, L(\alpha_1, \cdots, \alpha_n)\\ &(b - Y,\, \alpha_ i) = 0,\;\;\; i \in \{1, \cdots, s\} \Longleftrightarrow A^T(AX - b) = 0 \end{aligned}
  这样原问题便简化了。

几个关键定义

定义1：V 是数域 P 上的一个线性空间，泛函 f: V \times V \rightarrow {\mathbb R}，满足：

1. f(\alpha,\, k_1 \beta_1 + k_2 \beta_2) = k_1 f(\alpha, \,\beta_1) + k_2 f(\alpha,\,\beta_2)；
2. f(k_1 \alpha_1 + k_2 \alpha_2,\, \beta) = k_1 f(\alpha_1, \,\beta) + k_2 f(\alpha_2,\,\beta)，
   其中 \alpha,\; \alpha_1,\; \alpha_2,\; \beta,\; \beta_1,\; \beta_2 \in V 中任意的向量，k_1,\; k_2 \in P，则称 f(\alpha, \beta) 为 V 上的一个双线性函数.

定义2：设 f(\alpha, \beta) 是数域 P 上 n 维线性空间 V 上的一个双线性函数. \varepsilon_1,\, \cdots, \, \varepsilon_n 是 V 的一组基，则矩阵
A = \begin{bmatrix} f(\varepsilon_1,\, \varepsilon_1) & \cdots & f(\varepsilon_1,\, \varepsilon_n)\\ &&&\\ \vdots & \ddots & \vdots \\ &&&\\ f(\varepsilon_n,\, \varepsilon_1) & \cdots & f(\varepsilon_n,\, \varepsilon_n) \end{bmatrix}
叫做 f(\alpha, \beta) 在 \varepsilon_1,\, \cdots, \, \varepsilon_n 下的度量矩阵。 当 \alpha = \beta 时，V 上的函数 f(\alpha, \alpha) 称为与 f(\alpha, \beta) 对应的二次齐次函数。

易推知：同一个双线性函数在不同的基下的度量矩阵是合同的。

设 \varepsilon_1,\, \cdots, \, \varepsilon_n 及 \eta_1,\,\cdots,\,\eta_n 是线性空间 V 的两组基底，且 ( \eta_1,\,\cdots,\,\eta_n) = (\varepsilon_1,\, \cdots, \, \varepsilon_n)C，则有
\alpha = (\varepsilon_1,\, \cdots, \, \varepsilon_n)X = ( \eta_1,\,\cdots,\,\eta_n)X_1
\beta = (\varepsilon_1,\, \cdots, \, \varepsilon_n)Y = ( \eta_1,\,\cdots,\,\eta_n)Y_1
即：
X = CX_1,\;Y = CY_1

若双线性函数 f(\alpha, \beta) 在 \varepsilon_1,\, \cdots, \, \varepsilon_n 及 \eta_1,\,\cdots,\,\eta_n 下的度量矩阵分别为 A，B. 则有
f(\alpha, \beta) = X^TAY = (CX_1)^TA(CY_1) = X_1^TC^TACY_1 = X_1^TBY_1
因此
B = C^TAC

定义3：设 D = (V, E) 是一个标定的无环有向图，其中设 V = \{v_1,v_2,\cdots,v_n\},\;E = \{e_1,e_2,\cdots,e_m\}，则称 M(D) = (m_{ij})_{n \times m} 为 D 的关联矩阵，其中
m_{ij} = \begin{cases} 1 &\text{$v_i$ 是边 $e_j$ 的始点} \\ -1 &\text{$v_i$ 是边 $e_j$ 的终点} \\ 0 &\text{其他} \end{cases}

基于图的半监督学习

给定 D_l = \{(x_1,y_1), \,(x_2,y_2),\,\cdots,\,(x_l,y_l)\} 和 D_u = \{(x_{l+1},y_{l+1}), \,(x_{l+2},y_{l+2}),\,\cdots,\,(x_{l+u},y_{l+u})\}，l \ll u，l+u=m.我们先基于 D = D_l \bigcup D_u 构建一个图 G = (V, E)，其中节点集 V = \{(x_1,y_1), (x_2,y_2),\cdots,(x_{l+u},y_{l+u})\}，边集的亲和矩阵（affinity matrix，或称为相似度矩阵），常基于高斯函数定义为
(W)_{ij} = \begin{cases} exp(\frac{-||x_i - x_j||_2^2}{2\sigma^2}) &\text{if $i \neq j$} \\ 0 &\text{其他} \end{cases}
其中 i,\,j \in \{1, \,2, \,\cdots, \,m\}; \sigma > 0 是用户指定的高斯带宽参数。

子空间 V = L(x_1, \,x_2,\,\cdots,\,x_m)) 上定义一个映射 f
\begin{aligned} f: V \rightarrow {\mathbb R^C}, && \text{$C$ 是类别个数} \end{aligned}
则可以定义 f 的能量函数为
\begin{aligned} E(f) &= \frac{1}{2} {\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m (W)_{ij} ||f(x_i) - f(x_j)||^2}\\ &= \frac{1}{2}{\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m (W)_{ij}( ||f(x_i)||^2 - 2 f(x_i)^Tf(x_j) + ||f(x_j)||^2)}\\ &= {\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m}(W)_{ij}||f(x_i)||^2 - {\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m}f(x_i)^Tf(x_j)(W)_{ij} & \text{$i$, $j$ 的对称性} \end{aligned}

令
\begin{aligned} &W = (w_1, \, \cdots, w_m)\\ &F = (f(x_1), \cdots, f(x_m)) = (f_1, \cdots, f_m) \end{aligned}
则有
\begin{aligned} FWF^T &= (\sum_{i=1}^m f_i(W)_{1,i},\cdots, \sum_{i=1}^m f_j(W)_{m,i})F^T \\ &= (Fw_1, \cdots, Fw_m)F^T \\ &= \sum_{i=1}^m Fw_if_i^T \\ &= \sum_{i,j=1}^m (W)_{i,j}f_i f_j^T \end{aligned}
故而
\begin{aligned} Tr(FWF^T) &= \sum_{i,j=1}^m Tr(f_i f_j^T)(W)_{i,j} \\ &= {\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m}f(x_i)^Tf(x_j)(W)_{ij} \end{aligned}

令 d_j = {\displaystyle \sum_{j=1}^m (W)_{ij} = ||w_j||_1}，则记
D = diag(d_1, \cdots, d_m)，故而
{\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m}(W)_{ij}||f(x_i)||^2 = Tr(FDF^T)

因而
E(f) = Tr(F(D-W)F^T)

---

令 \Delta = D - W （被称为拉普拉斯矩阵）则有
\begin{aligned} \min_f E(f) = \min_f Tr(F \Delta F^T) \Longleftrightarrow F \Delta = 0 & & \text{最小二乘问题} \end{aligned}