Mixing
Trace ratios, ratio traces and generalized Rayleigh quotient
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
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^-1A$.
The first candidate problem uses the generalized Rayleigh quotient. If the possible solutions $L in mathcalM_rtimes n(mathbbR)$ have, as row vectors, the vectors $u_1,dots,u_r$, the proposed optimization problem is
$$ max_L sum_i=1^r fracu_i^TAu_iu_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^-1u_i$ is possible to rewrite the previous problem as
$$ max_L sum_i=1^r fracy_i^TDy_iy_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)^-1P^TAP = P^-1B^-1AP, $$
we obtain that $D$ is similar to $B^-1A$, so the leading eigenvectors of $B^-1A$ 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 fractr(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^-1A$, and how can I see it?
matrices optimization eigenvalues-eigenvectors trace positive-definite
asked Jul 28 at 10:39
gtf
205
add a comment |Â
up vote
0
down vote
favorite
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^-1A$.
The first candidate problem uses the generalized Rayleigh quotient. If the possible solutions $L in mathcalM_rtimes n(mathbbR)$ have, as row vectors, the vectors $u_1,dots,u_r$, the proposed optimization problem is
$$ max_L sum_i=1^r fracu_i^TAu_iu_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^-1u_i$ is possible to rewrite the previous problem as
$$ max_L sum_i=1^r fracy_i^TDy_iy_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)^-1P^TAP = P^-1B^-1AP, $$
we obtain that $D$ is similar to $B^-1A$, so the leading eigenvectors of $B^-1A$ 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 fractr(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^-1A$, and how can I see it?
matrices optimization eigenvalues-eigenvectors trace positive-definite
asked Jul 28 at 10:39
gtf
205
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
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^-1A$.
The first candidate problem uses the generalized Rayleigh quotient. If the possible solutions $L in mathcalM_rtimes n(mathbbR)$ have, as row vectors, the vectors $u_1,dots,u_r$, the proposed optimization problem is
$$ max_L sum_i=1^r fracu_i^TAu_iu_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^-1u_i$ is possible to rewrite the previous problem as
$$ max_L sum_i=1^r fracy_i^TDy_iy_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)^-1P^TAP = P^-1B^-1AP, $$
we obtain that $D$ is similar to $B^-1A$, so the leading eigenvectors of $B^-1A$ 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 fractr(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^-1A$, and how can I see it?
matrices optimization eigenvalues-eigenvectors trace positive-definite
asked Jul 28 at 10:39
gtf
205
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^-1A$.
The first candidate problem uses the generalized Rayleigh quotient. If the possible solutions $L in mathcalM_rtimes n(mathbbR)$ have, as row vectors, the vectors $u_1,dots,u_r$, the proposed optimization problem is
$$ max_L sum_i=1^r fracu_i^TAu_iu_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^-1u_i$ is possible to rewrite the previous problem as
$$ max_L sum_i=1^r fracy_i^TDy_iy_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)^-1P^TAP = P^-1B^-1AP, $$
we obtain that $D$ is similar to $B^-1A$, so the leading eigenvectors of $B^-1A$ 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 fractr(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^-1A$, and how can I see it?
matrices optimization eigenvalues-eigenvectors trace positive-definite
asked Jul 28 at 10:39
gtf
205
asked Jul 28 at 10:39
gtf
205
asked Jul 28 at 10:39
gtf
205
asked Jul 28 at 10:39
gtf
205
205
add a comment |Â
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2865159%2ftrace-ratios-ratio-traces-and-generalized-rayleigh-quotient%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password