Perturbation analysis for the trace quotient problem
Lei‐Hong Zhang, Wei Hong Yang · Linear and Multilinear Algebra · 2013
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.