Trace-Ratio问题的两种解法及其应用

Two solutions of Trace-Ratio problem and its applications

线性判别分析(LDA)作为一种降维技术,已成功应用于许多分类问题中,如语音识别、人脸识别、信息提取等领域.许多降维问题最后都会归结为一个Trace-Ratio(迹比)问题,也就是通过寻找一个列规范正交矩阵X∈Rn×r(n≥r)能够使得比值tr(XTAX)/tr(XTBX)最大化,其中矩A∈Rn×n阵是对称的矩阵,矩阵B∈Rn×n是对称正定矩阵.迹比问题在线性判别分析以及一些其他应用中占有至关重要的地位.但是迹比问题没有解析形式的解.介绍了Foley-Sammon变换的背景和国内外发展现状.给出了求解迹比问题的两种方法:逐次解法和牛顿法.改进了构造逐次解的具体方法,并且给出了逐次解的数值估计;给出了牛顿法的具体算法和二阶收敛性的证明.实验表明若将逐次解作为初始迭代点代入牛顿法中可以大大减少牛顿法的迭代次数,提高牛顿法的迭代速度.

Linear discriminant analysis (LDA) has been successfully used as a dimensionality reduction to many classification problems, such as speech recognition, face recognition and information retrieval. Many dimension reduction problems will eventually be attributed to the trace ratio optimization problem(TRP) which maximizes the ratio of two matrix traces, P(X)=SX(trace(XTAX)trace(XTBX), which X is a n×r,(n≥r)column orthonormal matrix,A∈R^n×n is a symmetric matrix,B∈R^n×n is a symmetric positive definite matrix.It has a crucial role in linear discriminant analysis and has many other applications as well. But TRP does not admit local non-global maximize.This paper reviewed the background and development status of Foley-Sammon transform. Studied some efficient iterative procedures to directly solve the ratio optimization problem, namely, successive solution, Newton method. The main research achievement were as follows: the successive solution was introduced, and the method to construct the successive solution was given, and concluded the numerical estimation of the successive solution. Newton method was introduced, including its specific algorithm. The second-order convergence of Newton method were also given.The successive solution can be substituted into Newton method as initial iteration points to reduce the iteration times of Newton method.