Zheng Wenming, Lin Zhouchen, Tang Xiaoou
Key Laboratory of Child Development and Learning Science, Ministry of Education, Research Center for Learning Science, Southeast University, Nanjing, Jiangsu 210096, China.
IEEE Trans Neural Netw. 2010 Mar;21(3):393-403. doi: 10.1109/TNN.2009.2037149. Epub 2010 Jan 19.
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.
判别分析在统计模式识别中起着重要作用。一种流行的方法是福利 - 萨蒙最优判别向量（FSODV）方法，其目的是找到一组最优的判别向量，在正交约束下最大化费希尔判别准则。FSODV方法在能够求解更多用于识别的判别向量这一意义上优于经典的费希尔线性判别分析（FLDA）方法。核福利 - 萨蒙最优判别向量（KFSODV）是通过核技巧对FSODV的非线性扩展。然而，当前的KFSODV算法可能会面临计算量过大的问题，因为在求解每个判别向量时都涉及矩阵求逆运算，导致每个判别向量的计算复杂度为三次方。当需要计算的判别向量数量很大时，这成本很高。在本文中，我们提出了一种求解KFSODV的快速算法，它基于特征系统的秩一更新（ROU）。每个判别向量仅需平方复杂度。此外，我们还将我们的方法进行推广，以有效地求解一类最优约束广义瑞利商（OCGRQ）问题，其中包括许多现有的降维技术。我们在几个真实数据集上进行了广泛的实验，以证明所提出算法的有效性。
