Volume 2, Issue 2
A Convergence Analysis on the Iterative Trace Ratio Algorithm and Its Refinements

Zhongxiao Jia & Fuhui Lai

CSIAM Trans. Appl. Math., 2 (2021), pp. 297-312.

Published online: 2021-05

Preview Full PDF 194 4414
Export citation
  • Abstract

In many applications one needs to process massive data of high dimensionality. In order to make data compact and reduce computational complexity, dimensionality reduction algorithms are commonly used. Linear discriminant analysis (LDA) is one of the most used approaches, which leads to a matrix trace ratio problem, i.e., maximization of the trace ratio $ρ(V)=Tr(V^TAV)/Tr(V^TBV)$, where $A$ and $B$ are $n×n$ real symmetric matrices with $B$ positive definite, and $V$ is an $n×p$ column orthonormal matrix. In this paper, we consider a commonly used Iterative Trace Ratio (ITR) algorithm developed by Ngo et al., $The$ $trace$ $ratio$ $optimization$ $problem$, $SIAM$ $Review$, $54 (3) (2012), pp. 545–569$. In implementations, it is common to use the symmetric Lanczos method to compute the $p$ eigenvectors of a certain large matrix corresponding to its $p$ largest eigenvalues at each iteration, and the resulting algorithm is abbreviated as ITR_L. We establish the global convergence and local quadratic convergence of the trace ratio itself. We then make two improvements over ITR_L: (i) using the refined Lanczos method to compute the desired eigenvectors at each iteration and (ii) providing a better initial guess via solving a generalized eigenvalue problem of the matrix pair $(A,B)$. The resulting algorithms are abbreviated as ITR_RL and ITR_GeigRL, respectively. Numerical experiments demonstrate that ITR_RL and ITR_GeigRL outperform ITR_L substantially.

  • Keywords

Dimensionality reduction, trace ratio, global convergence, eigenvalue, eigenvector, refined projection, refined Lanczos algorithm, implicitly restarted, preprocess.

  • AMS Subject Headings

65F15, 65F30, 62H30, 15A18

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{CSIAM-AM-2-297, author = {Zhongxiao Jia , and Fuhui Lai , }, title = {A Convergence Analysis on the Iterative Trace Ratio Algorithm and Its Refinements}, journal = {CSIAM Transactions on Applied Mathematics}, year = {2021}, volume = {2}, number = {2}, pages = {297--312}, abstract = {

In many applications one needs to process massive data of high dimensionality. In order to make data compact and reduce computational complexity, dimensionality reduction algorithms are commonly used. Linear discriminant analysis (LDA) is one of the most used approaches, which leads to a matrix trace ratio problem, i.e., maximization of the trace ratio $ρ(V)=Tr(V^TAV)/Tr(V^TBV)$, where $A$ and $B$ are $n×n$ real symmetric matrices with $B$ positive definite, and $V$ is an $n×p$ column orthonormal matrix. In this paper, we consider a commonly used Iterative Trace Ratio (ITR) algorithm developed by Ngo et al., $The$ $trace$ $ratio$ $optimization$ $problem$, $SIAM$ $Review$, $54 (3) (2012), pp. 545–569$. In implementations, it is common to use the symmetric Lanczos method to compute the $p$ eigenvectors of a certain large matrix corresponding to its $p$ largest eigenvalues at each iteration, and the resulting algorithm is abbreviated as ITR_L. We establish the global convergence and local quadratic convergence of the trace ratio itself. We then make two improvements over ITR_L: (i) using the refined Lanczos method to compute the desired eigenvectors at each iteration and (ii) providing a better initial guess via solving a generalized eigenvalue problem of the matrix pair $(A,B)$. The resulting algorithms are abbreviated as ITR_RL and ITR_GeigRL, respectively. Numerical experiments demonstrate that ITR_RL and ITR_GeigRL outperform ITR_L substantially.

}, issn = {2708-0579}, doi = {https://doi.org/10.4208/csiam-am.2021.nla.03}, url = {http://global-sci.org/intro/article_detail/csiam-am/18886.html} }
TY - JOUR T1 - A Convergence Analysis on the Iterative Trace Ratio Algorithm and Its Refinements AU - Zhongxiao Jia , AU - Fuhui Lai , JO - CSIAM Transactions on Applied Mathematics VL - 2 SP - 297 EP - 312 PY - 2021 DA - 2021/05 SN - 2 DO - http://doi.org/10.4208/csiam-am.2021.nla.03 UR - https://global-sci.org/intro/article_detail/csiam-am/18886.html KW - Dimensionality reduction, trace ratio, global convergence, eigenvalue, eigenvector, refined projection, refined Lanczos algorithm, implicitly restarted, preprocess. AB -

In many applications one needs to process massive data of high dimensionality. In order to make data compact and reduce computational complexity, dimensionality reduction algorithms are commonly used. Linear discriminant analysis (LDA) is one of the most used approaches, which leads to a matrix trace ratio problem, i.e., maximization of the trace ratio $ρ(V)=Tr(V^TAV)/Tr(V^TBV)$, where $A$ and $B$ are $n×n$ real symmetric matrices with $B$ positive definite, and $V$ is an $n×p$ column orthonormal matrix. In this paper, we consider a commonly used Iterative Trace Ratio (ITR) algorithm developed by Ngo et al., $The$ $trace$ $ratio$ $optimization$ $problem$, $SIAM$ $Review$, $54 (3) (2012), pp. 545–569$. In implementations, it is common to use the symmetric Lanczos method to compute the $p$ eigenvectors of a certain large matrix corresponding to its $p$ largest eigenvalues at each iteration, and the resulting algorithm is abbreviated as ITR_L. We establish the global convergence and local quadratic convergence of the trace ratio itself. We then make two improvements over ITR_L: (i) using the refined Lanczos method to compute the desired eigenvectors at each iteration and (ii) providing a better initial guess via solving a generalized eigenvalue problem of the matrix pair $(A,B)$. The resulting algorithms are abbreviated as ITR_RL and ITR_GeigRL, respectively. Numerical experiments demonstrate that ITR_RL and ITR_GeigRL outperform ITR_L substantially.

Zhongxiao Jia & Fuhui Lai. (2021). A Convergence Analysis on the Iterative Trace Ratio Algorithm and Its Refinements. CSIAM Transactions on Applied Mathematics. 2 (2). 297-312. doi:10.4208/csiam-am.2021.nla.03
Copy to clipboard
The citation has been copied to your clipboard