Perturbation analysis for the trace quotient problem |
| |
Authors: | Lei-Hong Zhang Wei Hong Yang |
| |
Affiliation: | 1. Department of Applied Mathematics , Shanghai University of Finance and Economics , 777 Guoding Road, Shanghai 200433 , P.R. China longzlh@gmail.com;3. School of Mathematical Sciences , Fudan University , Shanghai 200433 , P.R. China |
| |
Abstract: | Given a symmetric matrix B?∈?? m×m and a symmetric and positive-definite matrix W?∈?? m×m , maximizing the ratio trace(V ? BV)/trace(V ? WV) with respect to V?∈?? m×? (??≤?m) subject to the orthogonal constraint V ? V?=?I ? is called the trace quotient problem or the trace ratio problem (TRP). TRP arises originally from the linear discriminant analysis (LDA), which is a popular approach for feature extraction and dimension reduction. It has been known that TRP is equivalent to a nonlinear extreme eigenvalue problem and very efficient method has been proposed to find a global optimal solution successfully. The matrices B and W arising in LDA are constructed from samples, and thereby are contaminated by noises and errors. In this article, we perform a perturbation analysis for TRP assuming the original B and W are perturbed. The upper perturbation bounds of both the global optimal value and the set of global optimal solutions are derived, and numerical investigation is carried out to illustrate these perturbation estimates. |
| |
Keywords: | the trace quotient problem linear discriminant analysis nonlinear eigenvalue problem perturbation analysis |
|
|