A Rank-One Update Algorithm for Fast Solving Kernel Foley–Sammon Optimal Discriminant Vectors
A Rank-One Update Algorithm for Fast Solving Kernel Foley–Sammon Optimal Discriminant Vectors
复制标题
DOI：
10.1109/tnn.2009.2037149
复制
发表时间：
2010-03
影响因子：
--
通讯作者：
Wenming Zheng;Zhouchen Lin;Xiaoou Tang
中科院分区：
文献类型：
--
作者：
Wenming Zheng;Zhouchen Lin;Xiaoou Tang
判别分析在统计模式识别中起着重要作用。一种流行的方法是 Foley-Sammon 最优判别向量（FSODV）方法，其目的是找到一组最优判别向量，在正交约束下最大化 Fisher 判别准则。 FSODVs 方法优于经典的 Fisher 线性判别分析 (FLDA) 方法，因为它可以解决更多判别向量进行识别。内核 Foley-Sammon 最优判别向量 (KFSODV) 是 FSODV 通过内核技巧的非线性扩展。然而，当前的KFSODVs算法可能会遇到计算量大的问题，因为它在求解每个判别向量时涉及计算矩阵的逆，导致每个判别向量的复杂度为三次方。当要计算的判别向量的数量很大时，这是昂贵的。在本文中，我们提出了一种基于特征系统的秩一更新（ROU）的 KFSODV 求解快速算法。它只需要每个判别向量的平方复杂度。此外，我们还推广了我们的方法来有效地解决一系列最优约束广义瑞利商（OCGRQ）问题，其中包括许多现有的降维技术。我们在几个真实数据集上进行了广泛的实验，以证明所提出算法的有效性。
Discriminant analysis plays an important role in statistical pattern recognition. A popular method is the Foley-Sammon optimal discriminant vectors (FSODVs) method, which aims to find an optimal set of discriminant vectors that maximize the Fisher discriminant criterion under the orthogonal constraint. The FSODVs method outperforms the classic Fisher linear discriminant analysis (FLDA) method in the sense that it can solve more discriminant vectors for recognition. Kernel Foley-Sammon optimal discriminant vectors (KFSODVs) is a nonlinear extension of FSODVs via the kernel trick. However, the current KFSODVs algorithm may suffer from the heavy computation problem since it involves computing the inverse of matrices when solving each discriminant vector, resulting in a cubic complexity for each discriminant vector. This is costly when the number of discriminant vectors to be computed is large. In this paper, we propose a fast algorithm for solving the KFSODVs, which is based on rank-one update (ROU) of the eigensytems. It only requires a square complexity for each discriminant vector. Moreover, we also generalize our method to efficiently solve a family of optimally constrained generalized Rayleigh quotient (OCGRQ) problems which include many existing dimensionality reduction techniques. We conduct extensive experiments on several real data sets to demonstrate the effectiveness of the proposed algorithms.