Inexact implementation using Krylov subspace methods for large scale exponential discriminant analysis with applications to high dimensionality reduction problems

PATTERN RECOGNITION

卷:66

Article

Wu, Gang^1,2  Feng, Ting-ting³  Zhang, Li-jia²  Yang, Meng⁴ 

[1] China Univ Min & Technol, Dept Math, Xuzhou 221116, Jiangsu, Peoples R China

[2] Jiangsu Normal Univ, Sch Math & Stat, Xuzhou 221116, Jiangsu, Peoples R China

[3] East China Normal Univ, Dept Math, Shanghai Key Lab Pure Math & Math Practice, Dongchuan RD 500, Shanghai 200241, Peoples R China

[4] Soochow Univ, Sch Comp Sci & Technol, Suzhou 215006, Jiangsu, Peoples R China

关键词: Dimensionality reduction;    Linear discriminant analysis (LDA);    Exponential discriminant analysis (EDA);    Matrix exponential;    Krylov subspace;   

DOI  :  10.1016/j.patcog.2016.08.020

来源: Elsevier

【 摘 要 】

Exponential discriminant analysis (EDA) is a generalized discriminant analysis method based on matrix exponential. It can essentially overcome the intrinsic difficulty of small-sample-size problem that exists in the classical linear discriminant analysis (LDA). However, for data with high dimensionality, one has to solve a large matrix exponential eigenproblem in this method, and the time complexity is dominated by the computation of exponential of large matrices. In this paper, we propose two inexact Krylov subspace algorithms for solving the large matrix exponential eigenproblem efficiently. The contribution of this work is threefold. First, we consider how to compute matrix exponential-vector products efficiently, which is the key step in the Krylov subspace method. Second, we compare the discriminant analysis criterion of EDA and that of LDA from a theoretical point of view. Third, we establish the relationship between the accuracy of the approximate eigenvectors and the distance to nearest neighbor classifier, and show why the matrix exponential eigenproblem can be solved approximately in practice. Numerical experiments on some real-world databases show the superiority of our new algorithms over their original counterpart for face recognition.

【 授权许可】

Free