3
$\begingroup$

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 M\hat M^T. $$ that is, $MM^T - \hat M\hat 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 arrived at the conclusion that minimizing $\| M \|_2$ or $\| M \|_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?

Edit 4: Some more thoughts on the minimization of $\| M \|_2$ and $\| M \|_F$.

For $\| M \|_2$, we have $$ \| M \|_2 = \sqrt{\lambda _{max} (MM^T)}. $$ Since $\sqrt{ x }$ is monotonically increasing for $x>0$, minimizing $\| M \|_2$ is equivalent to minimizing the maximum eigenvalue of $MM^T$ which, intuitively, makes sense if we want to make $MM^T$ "less" positive semi-definite.

For $\| M \|_F$, we have $$ \| M \|_F = \sqrt{\text{trace}(MM^T)} = \sqrt{ \sum_i \lambda_i(MM^T)}. $$ Using the same argument for the minimization of $\sqrt{ x }$ for $x>0$, minimizing $\| M \|_F$ is equivalent to minimizing the sum of the eigenvalues of $MM^T$ which again, intuitively, makes sense if we want to make $MM^T$ "less" positive semi-definite.

$\endgroup$
  • 1
    $\begingroup$ Ah... "skinny" and "fat" are rather uncommon denominations. Prefer for example "$F$ is $n \times p$ with $n>p$" $\endgroup$ – Jean Marie Nov 19 '18 at 21:38
  • 1
    $\begingroup$ @JeanMarie thanks, I edited the question. $\endgroup$ – durdi Nov 19 '18 at 21:55
  • 3
    $\begingroup$ not all pd matrices can be compared, e.g., when A=diag(2,1) and B=diag(1,2), then neither $A\leq B$ nor $A\geq B$. $\endgroup$ – LinAlg Nov 19 '18 at 23:23
  • 2
    $\begingroup$ Your question is still unclear. You should clarify the meaning of $A\le 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. $\endgroup$ – user1551 Nov 20 '18 at 10:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Eric Nov 20 '18 at 13:44
2
$\begingroup$

In this setting the answer is trivial. Let $F=U\pmatrix{S\\ 0}V^T$ be a singular value decomposition. The constraint $MF=I$ then implies that $M$ must be in the form of $V\pmatrix{S^{-1}&X}U^T$. Hence $MM^T=V(S^{-2}+XX^T)V^T$ and its unique global minimum (with respect to the positive semidefinite partial ordering) is given by $X=0$ (because $XX^T$ is positive semidefinite and it equals zero only when $X$ is zero), meaning that $M=F^+$, the Moore-Penrose inverse of $F$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.