线性判别分析的理论和算法的研究

线性判别分析（简称LDA）是当前降维和特征提取中最有效方法之一，广泛应用于模式识别、数据挖掘、生物信息等领域。本项目致力于研究LDA中相关的模型、理论及算法。迹商优化问题（trace ratio optimization problem）来源于LDA最本质的模型，但也是经典Rayleigh商的推广，其本身也有很高的研究价值。关于其初步理论和一个具体算法已在2007年建立。在一个一般条件下，申请者等已证明:在精确和某些不精确的计算下，该算法有全局收敛性和局部二次收敛速度。同时Saad等也建立了它与传统牛顿法的联系。但在无条件下，该算法的收敛性质，如收敛速度，收敛点集的刻画及误差分析等都尚待解决，这便是本项目的目标之一。由于LDA中常要求解的稀疏性，本项目另一目标是建立求迹商优化问题中稀疏解的算法。另外，本项目还将研究LDA中与迹商优化问题相关的其他模型、理论和算法。

本项目研究的是线性判别分析的相关模型与高效的算法，以及应用线性判别分析解决实际问题。线性判别分析是当前降维和特征提取中最有效方法之一，广泛应用于模式识别、数据挖掘、生物信息等领域。本项目着重研究的是迹商优化问题，它是线性判别分析最本质的模型，从数学角度，迹商优化问题也是经典Rayleigh商的推广，其本身也有很高的研究价值。..本研究在项目之初的国际研究结果上进一步深化和扩展，与之相关的具体的研究成果包括：.（1）用一种基于数值代数的方法证明了迹商优化问题中全局最优解和局部最优解的等价关系；.（2）给出了迹商优化问题全局最优值和最优解的扰动分析；.（3）由于在实际计算迹商优化问题时，需要采用块Lanczos方法计算一个大型对称矩阵的若干个最大特征值和对应的特征向量，我们深入细致地研究了块Lanczos方法收敛性，特别是对特征值聚合时的情况给出了深入的理论分析结果；.（4）基于实际应用背景提出了多个迹商和优化的模型，并建立了问题的详细理论分析，以及快速有效的数值算法；.（5）提出了多个迹商和优化模型的子空间版本，该模型用于解决数据挖掘中多视角（multi-view）聚类分析，并深入地分析了该模型的数学性质，同时给出了高效的数值算法，证明了全局收敛性以及局部线性收敛速度。.这些成果基本上按照本项目申请时的预期发展线路，将线性判别分析中的迹商优化问题的研究推进了较大的一步，同时为以后进一步的相关研究铺好了道路。..另外，除了线性判别分析之外，我们在本项目的施行期间还对其他若干问题进行了研究，包括：二阶锥互补问题，线性响应特征值问题，最大相关性问题，非线性规划中的SQP方法，线性规划界面算法，一类DFP拟牛顿算法，以及建立在黎曼流形上的非线性规划的最优性条件等问题，在各个问题上都得到了相应的研究成果。..总结而言，在本项目研究期间，围绕线性判别分析，我们已发表了16篇SCI论文，项目负责人也因线性判别分析的研究成果获得了第四届‘应用数值代数奖’；同时通过参加国内外会议以及一年的美国得克萨斯大学阿灵顿分校的访问，开展了合作交流，为以后的进一步研究做好了准备。