Reading about Linear Discriminant Analysis, I find many problem formulations, that don't seem to be equivalent. So I'm trying to find the problem formulation whose solution is expressed as the following paragraph shows.

So, let's suppose that $A$ is a symmetric matrix of order $n$, and $B$ is a positive definite matrix of order $n$. I want to check which of the matrix optimization problems have as a solution a matrix constructed by taking the eigenvectors corresponding to the largest eigenvalues of $B^{-1}A$.

The first candidate problem uses the generalized Rayleigh quotient. If the possible solutions $L \in \mathcal{M}_{r\times n}(\mathbb{R})$ have, as row vectors, the vectors $u_1,\dots,u_r$, the proposed optimization problem is $$ \max_L \sum_{i=1}^r \frac{u_i^TAu_i}{u_i^TBu_i}. $$ For this problem I know that there exist a regular matrix $P$ so that $P^TAP = D$ is diagonal and $P^TBP = I$. From this, taking $y_i = P^{-1}u_i$ is possible to rewrite the previous problem as $$ \max_L \sum_{i=1}^r \frac{y_i^TDy_i}{y_i^Ty_i}. $$ This is a (non generalized) Rayleigh quotient sum, and if we add an orthogonality condition to the vectors $y_i$, then we can rewrite it as $$ \max_{UU^T = I} tr(UDU^T), $$ where $U$ contains in its rows the vectors $y_i$. Thanks to the Courant-Fischer theorem, it can be proved that this problem can be solved by adding to $U$ the eigenvectors of $D$ corresponding to its largest eigenvalues (in this particular case, since $D$ is diagonal, we just have to take the first vectors of the canonical basis, if we suppose the diagonal of $D$ ordered). And, as we also have $$ D = P^TAP = (P^TBP)^{-1}P^TAP = P^{-1}B^{-1}AP, $$ we obtain that $D$ is similar to $B^{-1}A$, so the leading eigenvectors of $B^{-1}A$ in the initial generalized Rayleigh problem lead to the same value as the last solution, solving this problem. We have to note that the orthogonality condition assumed in the last problem leads, after applying the isomorphism $P$, just to linear independence for the vectors $u_i$ in the first problem. Is this a correct solution for this problem?

However, related to this there are other problem formulations that not seem to be equivalent to the generalized Rayleigh already presented. These are the following:

$$ \max_{L} tr((LBL^T)^{-1}(LAL^T)$$

$$ \max_{L} \frac{tr(LAL^T)}{tr(LBL^T)} $$

For the first one I didn't get how to express it as a generalized Rayleigh quotient problem, and for the second one I feel that it is not equivalent to the first problem. So, which of these problems really have as a solution the leading eigenvectors of $B^{-1}A$, and how can I see it?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.