Mixing
Optimize $M$ such that $MM^T$ is the “smallest” (in a positive semi-definite sense)
up vote
2
down vote
favorite
I want to solve the following problem:
begin{alignat}{}
underset{M}{text{minimize}} quad & MM^T \
text{subject to} quad & MF=I.
end{alignat}
where by minimize $MM^T$ I mean to find $M$ such that for any other matrix $hat M$ that satisfies the constraint, I have
$$
MM^T le hat Mhat M^T.
$$
that is, $MM^T - hat Mhat M^T$ is negative semi-definite. $F$ is (full rank) $n times p$ with $n>p$ and $I$ the identity matrix.
How can I translate this "smallest" concept into the objective function of the minimization problem? Should I perhaps minimize some kind of norm of $MM^T$? And after formalizing the problem, what is its solution?
Edit 1: For context, I am working on the minimum-variance unbiased linear estimator problem.
I am given the vector $y$ and a matrix $F$ such that
$$
y = Fx + epsilon
$$
where $F in mathbb{R}^{m times n}$ ($m>n$) full rank, $y in mathbb{R}^m$, $x in mathbb{R}^n$ and $epsilon$ is a random vector with zero mean and covariance matrix $I in mathbb{R}^{m times m}$ (identity matrix) and I want to estimate $x$.
I want to derive a linear estimator ($hat x = My$) such that it is unbiased ($E[hat x]=x$) and its covariance matrix satisfies
$$
E[(hat x - x)(hat x - x)^T] le E[(tilde{x} - x)(tilde{x} - x)^T]
$$
for any unbiased linear estimate $tilde{x}=tilde{M}y$.
For this problem, I know that such a linear estimator is unbiased if $MF=I$ (identity matrix) and its covariance matrix is
$$
E[(hat x - x)(hat x - x)^T] = MM^T
$$
and this is the point I am stuck.
I know that the solution for this problem is $M=(F^TF)^{-1}F^T$, and all the proofs I found assume this $M$ as an estimator, and then go on to prove that it is in fact the minimum-variance unbiased one. However, I want to arrive at this result starting from first principles, as if I did not know the solution a priori.
Edit 2: For reference, this pdf also discusses the topic using this informal notion of "smallest" and "largest" covariance matrix.
Edit 3: After some numerical tests, I got to the conclusion that minimizing $| MM^T |_2$ or $| MM^T |_{F}$ will both lead to the desired answer, that is, $M = (F^TF)^{-1}F^T$. Could someone give a formal argument for why this is the case?
linear-algebra optimization estimation least-squares covariance
asked 2 days ago
pedroszattoni
183110
|
show 7 more comments
up vote
2
down vote
favorite
I want to solve the following problem:
begin{alignat}{}
underset{M}{text{minimize}} quad & MM^T \
text{subject to} quad & MF=I.
end{alignat}
where by minimize $MM^T$ I mean to find $M$ such that for any other matrix $hat M$ that satisfies the constraint, I have
$$
MM^T le hat Mhat M^T.
$$
that is, $MM^T - hat Mhat M^T$ is negative semi-definite. $F$ is (full rank) $n times p$ with $n>p$ and $I$ the identity matrix.
How can I translate this "smallest" concept into the objective function of the minimization problem? Should I perhaps minimize some kind of norm of $MM^T$? And after formalizing the problem, what is its solution?
Edit 1: For context, I am working on the minimum-variance unbiased linear estimator problem.
I am given the vector $y$ and a matrix $F$ such that
$$
y = Fx + epsilon
$$
where $F in mathbb{R}^{m times n}$ ($m>n$) full rank, $y in mathbb{R}^m$, $x in mathbb{R}^n$ and $epsilon$ is a random vector with zero mean and covariance matrix $I in mathbb{R}^{m times m}$ (identity matrix) and I want to estimate $x$.
I want to derive a linear estimator ($hat x = My$) such that it is unbiased ($E[hat x]=x$) and its covariance matrix satisfies
$$
E[(hat x - x)(hat x - x)^T] le E[(tilde{x} - x)(tilde{x} - x)^T]
$$
for any unbiased linear estimate $tilde{x}=tilde{M}y$.
For this problem, I know that such a linear estimator is unbiased if $MF=I$ (identity matrix) and its covariance matrix is
$$
E[(hat x - x)(hat x - x)^T] = MM^T
$$
and this is the point I am stuck.
I know that the solution for this problem is $M=(F^TF)^{-1}F^T$, and all the proofs I found assume this $M$ as an estimator, and then go on to prove that it is in fact the minimum-variance unbiased one. However, I want to arrive at this result starting from first principles, as if I did not know the solution a priori.
Edit 2: For reference, this pdf also discusses the topic using this informal notion of "smallest" and "largest" covariance matrix.
Edit 3: After some numerical tests, I got to the conclusion that minimizing $| MM^T |_2$ or $| MM^T |_{F}$ will both lead to the desired answer, that is, $M = (F^TF)^{-1}F^T$. Could someone give a formal argument for why this is the case?
linear-algebra optimization estimation least-squares covariance
asked 2 days ago
pedroszattoni
183110
1
Ah... "skinny" and "fat" are rather uncommon denominations. Prefer for example "$F$ is $n times p$ with $n>p$"
– Jean Marie
2 days ago
1
@JeanMarie thanks, I edited the question.
– pedroszattoni
2 days ago
2
not all pd matrices can be compared, e.g., when A=diag(2,1) and B=diag(1,2), then neither $Aleq B$ nor $Ageq B$.
– LinAlg
2 days ago
1
Your question is still unclear. You should clarify the meaning of $Ale B$ for two matrices $A$ and $B$. Your question title seems to suggest that you are talking about positive semidefinite partial ordering, but in the question body, when you are comparing covariance matrices, my impression is that you are talking about entrywise comparison.
– user1551
2 days ago
1
I seem to recall that every left inverse of a matrix $F$ can be expressed in the form $(F^* F)^{-1} F^*+K$ where $K$ is a matrix which satisfies $KF=0$. Once you have this, it is not too hard to show that there is a smallest solution (in the ordering $A leq B$ means $B-A$ is positive semidefinite) and that it is obtained by taking $K=0$. I am leaving this as a comment rather than an answer since I don't fully remember on the claim that every left inverse has this form.
– Eric
yesterday
|
show 7 more comments
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I want to solve the following problem:
begin{alignat}{}
underset{M}{text{minimize}} quad & MM^T \
text{subject to} quad & MF=I.
end{alignat}
where by minimize $MM^T$ I mean to find $M$ such that for any other matrix $hat M$ that satisfies the constraint, I have
$$
MM^T le hat Mhat M^T.
$$
that is, $MM^T - hat Mhat M^T$ is negative semi-definite. $F$ is (full rank) $n times p$ with $n>p$ and $I$ the identity matrix.
How can I translate this "smallest" concept into the objective function of the minimization problem? Should I perhaps minimize some kind of norm of $MM^T$? And after formalizing the problem, what is its solution?
Edit 1: For context, I am working on the minimum-variance unbiased linear estimator problem.
I am given the vector $y$ and a matrix $F$ such that
$$
y = Fx + epsilon
$$
where $F in mathbb{R}^{m times n}$ ($m>n$) full rank, $y in mathbb{R}^m$, $x in mathbb{R}^n$ and $epsilon$ is a random vector with zero mean and covariance matrix $I in mathbb{R}^{m times m}$ (identity matrix) and I want to estimate $x$.
I want to derive a linear estimator ($hat x = My$) such that it is unbiased ($E[hat x]=x$) and its covariance matrix satisfies
$$
E[(hat x - x)(hat x - x)^T] le E[(tilde{x} - x)(tilde{x} - x)^T]
$$
for any unbiased linear estimate $tilde{x}=tilde{M}y$.
For this problem, I know that such a linear estimator is unbiased if $MF=I$ (identity matrix) and its covariance matrix is
$$
E[(hat x - x)(hat x - x)^T] = MM^T
$$
and this is the point I am stuck.
I know that the solution for this problem is $M=(F^TF)^{-1}F^T$, and all the proofs I found assume this $M$ as an estimator, and then go on to prove that it is in fact the minimum-variance unbiased one. However, I want to arrive at this result starting from first principles, as if I did not know the solution a priori.
Edit 2: For reference, this pdf also discusses the topic using this informal notion of "smallest" and "largest" covariance matrix.
Edit 3: After some numerical tests, I got to the conclusion that minimizing $| MM^T |_2$ or $| MM^T |_{F}$ will both lead to the desired answer, that is, $M = (F^TF)^{-1}F^T$. Could someone give a formal argument for why this is the case?
linear-algebra optimization estimation least-squares covariance
asked 2 days ago
pedroszattoni
183110
I want to solve the following problem:
begin{alignat}{}
underset{M}{text{minimize}} quad & MM^T \
text{subject to} quad & MF=I.
end{alignat}
where by minimize $MM^T$ I mean to find $M$ such that for any other matrix $hat M$ that satisfies the constraint, I have
$$
MM^T le hat Mhat M^T.
$$
that is, $MM^T - hat Mhat M^T$ is negative semi-definite. $F$ is (full rank) $n times p$ with $n>p$ and $I$ the identity matrix.
How can I translate this "smallest" concept into the objective function of the minimization problem? Should I perhaps minimize some kind of norm of $MM^T$? And after formalizing the problem, what is its solution?
Edit 1: For context, I am working on the minimum-variance unbiased linear estimator problem.
I am given the vector $y$ and a matrix $F$ such that
$$
y = Fx + epsilon
$$
where $F in mathbb{R}^{m times n}$ ($m>n$) full rank, $y in mathbb{R}^m$, $x in mathbb{R}^n$ and $epsilon$ is a random vector with zero mean and covariance matrix $I in mathbb{R}^{m times m}$ (identity matrix) and I want to estimate $x$.
I want to derive a linear estimator ($hat x = My$) such that it is unbiased ($E[hat x]=x$) and its covariance matrix satisfies
$$
E[(hat x - x)(hat x - x)^T] le E[(tilde{x} - x)(tilde{x} - x)^T]
$$
for any unbiased linear estimate $tilde{x}=tilde{M}y$.
For this problem, I know that such a linear estimator is unbiased if $MF=I$ (identity matrix) and its covariance matrix is
$$
E[(hat x - x)(hat x - x)^T] = MM^T
$$
and this is the point I am stuck.
I know that the solution for this problem is $M=(F^TF)^{-1}F^T$, and all the proofs I found assume this $M$ as an estimator, and then go on to prove that it is in fact the minimum-variance unbiased one. However, I want to arrive at this result starting from first principles, as if I did not know the solution a priori.
Edit 2: For reference, this pdf also discusses the topic using this informal notion of "smallest" and "largest" covariance matrix.
Edit 3: After some numerical tests, I got to the conclusion that minimizing $| MM^T |_2$ or $| MM^T |_{F}$ will both lead to the desired answer, that is, $M = (F^TF)^{-1}F^T$. Could someone give a formal argument for why this is the case?
linear-algebra optimization estimation least-squares covariance
linear-algebra optimization estimation least-squares covariance
asked 2 days ago
pedroszattoni
183110
asked 2 days ago
pedroszattoni
183110
edited yesterday
asked 2 days ago
pedroszattoni
183110
asked 2 days ago
pedroszattoni
183110
asked 2 days ago
pedroszattoni
183110
183110
1
Ah... "skinny" and "fat" are rather uncommon denominations. Prefer for example "$F$ is $n times p$ with $n>p$"
– Jean Marie
2 days ago
1
@JeanMarie thanks, I edited the question.
– pedroszattoni
2 days ago
2
not all pd matrices can be compared, e.g., when A=diag(2,1) and B=diag(1,2), then neither $Aleq B$ nor $Ageq B$.
– LinAlg
2 days ago
1
Your question is still unclear. You should clarify the meaning of $Ale B$ for two matrices $A$ and $B$. Your question title seems to suggest that you are talking about positive semidefinite partial ordering, but in the question body, when you are comparing covariance matrices, my impression is that you are talking about entrywise comparison.
– user1551
2 days ago
1
I seem to recall that every left inverse of a matrix $F$ can be expressed in the form $(F^* F)^{-1} F^*+K$ where $K$ is a matrix which satisfies $KF=0$. Once you have this, it is not too hard to show that there is a smallest solution (in the ordering $A leq B$ means $B-A$ is positive semidefinite) and that it is obtained by taking $K=0$. I am leaving this as a comment rather than an answer since I don't fully remember on the claim that every left inverse has this form.
– Eric
yesterday
|
show 7 more comments
1
Ah... "skinny" and "fat" are rather uncommon denominations. Prefer for example "$F$ is $n times p$ with $n>p$"
– Jean Marie
2 days ago
1
@JeanMarie thanks, I edited the question.
– pedroszattoni
2 days ago
2
not all pd matrices can be compared, e.g., when A=diag(2,1) and B=diag(1,2), then neither $Aleq B$ nor $Ageq B$.
– LinAlg
2 days ago
1
Your question is still unclear. You should clarify the meaning of $Ale B$ for two matrices $A$ and $B$. Your question title seems to suggest that you are talking about positive semidefinite partial ordering, but in the question body, when you are comparing covariance matrices, my impression is that you are talking about entrywise comparison.
– user1551
2 days ago
1
I seem to recall that every left inverse of a matrix $F$ can be expressed in the form $(F^* F)^{-1} F^*+K$ where $K$ is a matrix which satisfies $KF=0$. Once you have this, it is not too hard to show that there is a smallest solution (in the ordering $A leq B$ means $B-A$ is positive semidefinite) and that it is obtained by taking $K=0$. I am leaving this as a comment rather than an answer since I don't fully remember on the claim that every left inverse has this form.
– Eric
yesterday
1
1
Ah... "skinny" and "fat" are rather uncommon denominations. Prefer for example "$F$ is $n times p$ with $n>p$"
– Jean Marie
2 days ago
Ah... "skinny" and "fat" are rather uncommon denominations. Prefer for example "$F$ is $n times p$ with $n>p$"
– Jean Marie
2 days ago
1
1
@JeanMarie thanks, I edited the question.
– pedroszattoni
2 days ago
@JeanMarie thanks, I edited the question.
– pedroszattoni
2 days ago
2
2
not all pd matrices can be compared, e.g., when A=diag(2,1) and B=diag(1,2), then neither $Aleq B$ nor $Ageq B$.
– LinAlg
2 days ago
not all pd matrices can be compared, e.g., when A=diag(2,1) and B=diag(1,2), then neither $Aleq B$ nor $Ageq B$.
– LinAlg
2 days ago
1
1
Your question is still unclear. You should clarify the meaning of $Ale B$ for two matrices $A$ and $B$. Your question title seems to suggest that you are talking about positive semidefinite partial ordering, but in the question body, when you are comparing covariance matrices, my impression is that you are talking about entrywise comparison.
– user1551
2 days ago
Your question is still unclear. You should clarify the meaning of $Ale B$ for two matrices $A$ and $B$. Your question title seems to suggest that you are talking about positive semidefinite partial ordering, but in the question body, when you are comparing covariance matrices, my impression is that you are talking about entrywise comparison.
– user1551
2 days ago
1
1
I seem to recall that every left inverse of a matrix $F$ can be expressed in the form $(F^* F)^{-1} F^*+K$ where $K$ is a matrix which satisfies $KF=0$. Once you have this, it is not too hard to show that there is a smallest solution (in the ordering $A leq B$ means $B-A$ is positive semidefinite) and that it is obtained by taking $K=0$. I am leaving this as a comment rather than an answer since I don't fully remember on the claim that every left inverse has this form.
– Eric
yesterday
I seem to recall that every left inverse of a matrix $F$ can be expressed in the form $(F^* F)^{-1} F^*+K$ where $K$ is a matrix which satisfies $KF=0$. Once you have this, it is not too hard to show that there is a smallest solution (in the ordering $A leq B$ means $B-A$ is positive semidefinite) and that it is obtained by taking $K=0$. I am leaving this as a comment rather than an answer since I don't fully remember on the claim that every left inverse has this form.
– Eric
yesterday
|
show 7 more comments
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3005533%2foptimize-m-such-that-mmt-is-the-smallest-in-a-positive-semi-definite-sen%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Ah... "skinny" and "fat" are rather uncommon denominations. Prefer for example "$F$ is $n times p$ with $n>p$"
– Jean Marie
2 days ago
1
@JeanMarie thanks, I edited the question.
– pedroszattoni
2 days ago
2
not all pd matrices can be compared, e.g., when A=diag(2,1) and B=diag(1,2), then neither $Aleq B$ nor $Ageq B$.
– LinAlg
2 days ago
1
Your question is still unclear. You should clarify the meaning of $Ale B$ for two matrices $A$ and $B$. Your question title seems to suggest that you are talking about positive semidefinite partial ordering, but in the question body, when you are comparing covariance matrices, my impression is that you are talking about entrywise comparison.
– user1551
2 days ago
1
I seem to recall that every left inverse of a matrix $F$ can be expressed in the form $(F^* F)^{-1} F^*+K$ where $K$ is a matrix which satisfies $KF=0$. Once you have this, it is not too hard to show that there is a smallest solution (in the ordering $A leq B$ means $B-A$ is positive semidefinite) and that it is obtained by taking $K=0$. I am leaving this as a comment rather than an answer since I don't fully remember on the claim that every left inverse has this form.
– Eric
yesterday