66TM-2018《Low-Rank Linear Embedding for Image Recognition》

2. 核心思想

该论文的核心思想是将流形学习（Manifold Learning）与鲁棒回归（Robust Regression）相结合，并引入低秩约束和联合稀疏性，以构建一个更鲁棒、更具判别性的特征提取模型。

传统的流形学习方法（如LPP）通过构建邻域图来保持数据的局部几何结构，但其性能易受噪声和异常值影响，因为它们通常使用对异常值敏感的Frobenius范数（F-norm）作为损失函数。此外，它们学习的投影矩阵通常是非稀疏的，无法进行有效的特征选择。

本文提出的低秩线性嵌入（Low-Rank Linear Embedding, LRLE） 方法从以下几个方面进行了改进：

1. 回归视角重构LPP：将LPP的目标函数重新表述为一个回归问题，即用每个样本的邻域点来回归该样本本身。
2. 鲁棒损失函数：使用对异常值不敏感的 $L_{2,1}$-范数代替F-norm作为损失函数，以最小化重构误差，从而提高模型的鲁棒性。
3. 低秩约束：在回归矩阵上施加低秩约束，以挖掘不同邻居之间的潜在关系，并发现数据的全局结构。
4. 联合稀疏正则化：在目标函数中加入 $L_{2,1}$-范数正则化项，迫使回归矩阵的行趋向于零向量，从而实现联合稀疏性，达到特征选择的目的。

3. 目标函数

论文最终提出的目标函数如下：
$$\underset{A,B}{\min }\sum _{ij}{\Vert x_i^T-x_j^{T}AB\Vert }_2{W}_{ij}+\lambda {\Vert AB\Vert }_{2,1}\text{s.t.}{A}^{T}A=I_d$$
其中：

• $X=[x_1,x_2,...,x_n]\in {\mathbb{R}}^{m\times n}$ 是包含 $n$ 个 $m$ 维样本的数据矩阵。
• $W_{ij}$ 是邻域图的权重，定义了数据点 $x_i$ 和 $x_j$ 之间的局部关系。
• $A\in {\mathbb{R}}^{m\times d}$ 是投影矩阵，用于将高维数据投影到 $d$ 维的低维子空间。
• $B\in {\mathbb{R}}^{d\times m}$ 是回归矩阵。
• $Z=AB\in {\mathbb{R}}^{m\times m}$ 是回归矩阵，其低秩性由 $d$ 控制（因为 $\text{rank}(Z)\le d$）。
• ${\Vert \cdot \Vert }_2$ 是 $L_2$-范数，${\Vert \cdot \Vert }_{2,1}$ 是 $L_{2,1}$-范数，定义为 $\Vert X{\Vert }_{2,1}={\sum }_{i=1}^m\Vert x_i{\Vert }_2$，其中 $x_i$ 是矩阵 $X$ 的第 $i$ 行。
• $\lambda >0$ 是正则化系数。
• $A^{T}A=I_d$ 是正交约束，用于避免平凡解。

这个目标函数有两部分：

1. 第一项 ${\sum }_{ij}{\Vert x_i^T-x_j^{T}AB\Vert }_2{W}_{ij}$ 是 $L_{2,1}$-范数损失函数，旨在让每个样本 $x_i$ 能够被其邻域点 $x_j$ 的低维表示 $x_j^{T}A$ 经过回归矩阵 $B$ 重构回来，从而保持局部流形结构并最小化重构误差。
2. 第二项 $\lambda {\Vert AB\Vert }_{2,1}$ 是 $L_{2,1}$-范数正则化项，它促使 $AB$ 矩阵的行是稀疏的，即某些行会趋近于零，这意味着与这些行对应的原始特征是不重要的，从而实现了特征选择。

4. 目标函数的优化过程

由于目标函数中同时包含 $A$ 和 $B$，并且 $L_{2,1}$-范数不可微，直接求解非常困难。作者设计了一个交替迭代重加权算法（Iterative Reweighted Algorithm）来求解。

优化步骤

1. 引入辅助变量：
   为了处理 $L_{2,1}$-范数，引入两个对角权重矩阵 $D$ 和 $M$ 来近似 $L_{2,1}$-范数。

   • 对于损失项，定义对角矩阵 $D$，其第 $(i,j)$ 个对角元素为：
     $$D_{ij}=\frac{W_{ij}}{2{\Vert x_i^T-x_j^{T}AB\Vert }_2+\delta }$$
     其中 $\delta$ 是一个极小的常数，防止分母为零。这个权重 $D_{ij}$ 与重构误差成反比：重构误差越小，权重越大，反之则越小。
   • 对于正则项，定义对角矩阵 $M$，其第 $i$ 个对角元素为：
     $$M_{ii}=\frac{1}{2{\Vert (AB{)}_i\Vert }_2+\delta }$$
     其中 $(AB{)}_i$ 是矩阵 $AB$ 的第 $i$ 行。这个权重 $M_{ii}$ 与该行的模长成反比：某行的模长越大，其对应的权重越小，正则化对其影响越小；反之，模长小的行权重大会被更严厉地惩罚。

2. 交替优化：
   在每次迭代中，固定一个变量，优化另一个变量。

   • B-step (固定 A，求解 B)：
     将 $L_{2,1}$-范数损失和正则项用其加权平方和近似，目标函数可转化为一个加权的二次型。对 $B$ 求偏导并令其为零，得到 $B$ 的闭式解：
     $$B=(A^{T}XG{X}^{T}A+\lambda A^{T}MA{)}^{-1}{A}^{T}XD{X}^T$$
     其中 $G$ 是一个对角矩阵，其第 $i$ 个对角元素为 $G_{ii}={\sum }_j{D}_{ij}$。

   • A-step (固定 B，求解 A)：
     将上述求得的 $B$ 代回目标函数，经过一系列推导（详见原文），优化问题转化为一个比值迹（Ratio Trace）最大化问题：
     $$\underset{A^{T}A=I_d}{\max }\text{tr}\left[(A^T(XG{X}^T+\lambda M)A{)}^{-1}{A}^{T}XD{X}^{T}X{D}^T{X}^{T}A\right]$$
     这个问题的最优解可以通过求解以下广义特征值问题得到：
     $$(XG{X}^T+\lambda M{)}^{-1}(XD{X}^{T}X{D}^T{X}^T)A=A\tilde{\Lambda }$$
     其中 $\tilde{\Lambda }$ 是特征值矩阵。最优的投影矩阵 $A$ 由该方程的 $d$ 个最大特征值对应的正交特征向量构成。

3. 迭代更新：
   重复执行 B-step 和 A-step，每次迭代后，根据当前的 $A$ 和 $B$ 更新权重矩阵 $D$ 和 $M$，然后用新的权重重新求解 $B$ 和 $A$。这个过程一直持续到目标函数值收敛或达到最大迭代次数。

5. 主要贡献点

该论文的主要贡献可以总结为以下四点：

1. 提出新颖的模型：提出了一个基于低秩约束的流形回归新模型（LRLE）。该模型利用 $L_{2,1}$-范数作为损失函数和正则化项，构建了一个既能保持流形结构、又具备鲁棒性和联合稀疏特征选择能力的统一框架。
2. 解决低秩优化：通过将回归矩阵 $Z$ 分解为投影矩阵 $A$ 和回归矩阵 $B$（即 $Z=AB$），巧妙地将非凸的低秩约束问题融入到模型中，并通过交替迭代的方式进行求解。
3. 提供理论分析：对提出的迭代算法进行了理论分析，证明了其收敛性（定理1），并分析了算法的计算复杂度。此外，还揭示了LRLE与传统OLPP之间的理论联系（定理2）：当正则化参数 $\lambda \to 0$ 时，LRLE退化为在重加权OLPP子空间中的回归。
4. 验证有效性：在多个基准数据集（包括AR, FERET, Yale, Binary alpha, LFW, Fashion-MNIST, CIFAR-10）上进行了大量实验，结果表明LRLE在识别率上优于LPP、OLPP、UDFS、JELSR等现有方法，尤其是在处理含噪声或遮挡的图像时表现出更强的鲁棒性。

6. 算法实现过程详解

根据论文的 Algorithm 1 和优化过程，LRLE的完整实现步骤如下：

输入：数据矩阵 $X\in {\mathbb{R}}^{m\times n}$，目标维度 $d$，近邻数 $k$，正则化参数 $\lambda$，最大迭代次数，收敛阈值。

输出：投影矩阵 $A\in {\mathbb{R}}^{m\times d}$。

过程：

1. 初始化：

   • 使用k近邻法构建邻域图 $W$。
   • 初始化投影矩阵 $A$（例如，随机初始化或使用PCA结果）。
   • 初始化回归矩阵 $B$（例如，随机初始化）。
   • 初始化迭代计数器 $t=0$。

2. 迭代循环（直到收敛或达到最大迭代次数）：

   • 步骤1：计算权重矩阵 $D$ 和 $M$

     • 根据当前的 $A$ 和 $B$，计算重构误差 $e_{ij}=x_i^T-x_j^{T}AB$。
     • 计算 $L_{2,1}$-范数损失的权重矩阵 $D$：
       $$D_{ij}=\frac{W_{ij}}{2{\Vert e_{ij}\Vert }_2+\delta }$$
     • 计算 $L_{2,1}$-范数正则项的权重矩阵 $M$：
       $$M_{ii}=\frac{1}{2{\Vert (AB{)}_i\Vert }_2+\delta }$$
     • 构建对角矩阵 $D$ 和 $M$。

   • 步骤2：更新 $B$ (B-step)

     • 计算对角矩阵 $G$：$G_{ii}={\sum }_j{D}_{ij}$。
     • 计算中间矩阵 $\Gamma =A^{T}XG{X}^{T}A+\lambda A^{T}MA$。
     • 计算 $B$ 的更新值：
       $$B={\Gamma }^{-1}{A}^{T}XD{X}^T$$

   • 步骤3：更新 $A$ (A-step)

     • 计算矩阵 $P=XD{X}^{T}X{D}^T{X}^T$。
     • 计算矩阵 $Q=XG{X}^T+\lambda M$。
     • 求解广义特征值问题：
       $$Q^{-1}PA=A\tilde{\Lambda }$$
     • 将 $A$ 更新为该方程的 $d$ 个最大特征值对应的正交特征向量。

   • 步骤4：检查收敛性

     • 计算当前目标函数值 $J_t={\sum }_{ij}{\Vert x_i^T-x_j^{T}AB\Vert }_2{W}_{ij}+\lambda {\Vert AB\Vert }_{2,1}$。
     • 如果 $|J_t-J_{t-1}|<ϵ$ 或 $t$ 达到最大值，则停止迭代。
     • 否则，$t=t+1$，返回步骤1。

3. 输出：返回最终的投影矩阵 $A$。

特征提取：对于一个新的测试样本 $x_{\text{test}}$，其低维特征表示为 $y_{\text{test}}=A^T{x}_{\text{test}}$。

该算法的核心在于通过交替迭代和重加权，将一个复杂的非凸、非光滑优化问题分解为两个相对容易求解的子问题，从而有效地逼近原问题的解。

这个公式：
$$\underset{A,B}{\min }\sum _{ij}{\Vert x_i^T-x_j^{T}AB\Vert }_2{W}_{ij}$$
是论文中提出的低秩线性嵌入（LRLE）模型的核心部分，它通过回归的视角重新定义了流形学习的目标。我们可以从以下几个层面来理解其物理含义：

1. 核心思想：用邻居来“重构”自己

传统的流形学习方法（如LPP）主要关注的是保持数据点之间的相对距离或邻近关系。而这个公式则引入了一个更深层次的、基于重建（Reconstruction）的思想。

• $x_i^T$: 这是原始高维空间中第 $i$ 个样本点 $x_i$ 的转置。
• $x_j^{T}AB$: 这是关键的一环。它表示将第 $j$ 个样本点 $x_j$ 先投影到一个低维子空间（通过 $A$），然后通过一个回归矩阵 $B$ 将其“拉回”或“映射”回原始高维空间的一个估计值。
• ${\Vert x_i^T-x_j^{T}AB\Vert }_2$: 这个项计算的是原始样本 $x_i$ 和由其邻居 $x_j$ 经过投影和回归后得到的估计值之间的欧氏距离（L2范数）。这个距离衡量了重建误差。

因此，整个公式的物理含义可以概括为：

对于每一个样本点 $x_i$，我们都希望它能够被其在邻域图中的邻居 $x_j$ 所“重建”出来。 我们不是简单地要求它们的距离很近，而是要求 $x_i$ 能够被 $x_j$ 经过一个特定的变换（先投影再回归）所很好地逼近。

2. 邻居关系的重要性 ($W_{ij}$)

• $W_{ij}$: 这是邻域图的权重矩阵。如果 $x_i$ 和 $x_j$ 是近邻（例如，$x_j$ 在 $x_i$ 的k近邻集合内），那么 $W_{ij}$ 会是一个较大的正数（通常为1）；否则，$W_{ij}$ 为0。
• 加权求和 ${\sum }_{ij}\cdots W_{ij}$: 这个权重机制确保了只有那些真正相关的邻居才会对总损失产生显著影响。离得远的点，即使有误差，也不会被惩罚。这使得模型能够专注于局部几何结构。

3. 为什么这样设计？——从LPP的视角看

这个公式是对经典LPP（Locality Preserving Projections）目标函数的一种深刻重构。

• LPP的传统目标: LPP的目标是 ${\min }_Q{\sum }_{ij}\Vert Q^T{x}_i-Q^T{x}_j{\Vert }^2{W}_{ij}$。它的物理含义是：在低维空间中，如果两个点在高维空间是邻居，它们的投影也应该靠近。
• LRLE的回归视角重构: LRLE将这个目标转化为一个回归问题。它假设，在高维空间中，一个点 $x_i$ 可以被其邻居 $x_j$ 通过一个线性变换（即 $AB$）来近似。这种“重建”能力不仅保留了局部结构，还隐含地捕捉了数据点之间的内在生成关系。如果一个点能被其邻居很好地重建，说明这些点共享相似的局部模式或特征。

4. 总结物理含义

综合来看，这个目标函数的物理含义是：

我们寻找一个最优的投影矩阵 $A$ 和回归矩阵 $B$，使得在高维空间中，每个数据点 $x_i$ 都能被其附近的邻居 $x_j$ 通过一个线性变换（$AB$）非常精确地重建出来。 换句话说，我们希望数据点与其邻居之间存在一种强的、可预测的线性关系。通过最小化所有这种“重建误差”的加权和，我们就能找到一个既能保持局部流形结构、又能揭示数据内部生成规律的低维表示。

这种基于重建的思路比单纯的距离保持更为严格和鲁棒，因为它要求模型不仅要知道“谁和谁近”，还要知道“如何从一个点推断出另一个点”。