Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

I have two matrices $U$ and $V$. $U$ is $n \times n$ and $V$ is $n \times m$. (Both are empirical results of an experiment.) I would like to find a linear transformation $A$, $m \times n$, such that $VA = \hat{U}$, where $\hat{U} = \underset{X}{\arg \min}$ $m(X, U)$ for some metric $m$.

Is there a closed form or iterative solution to this problem?

share|improve this question
2  
What is the argmin taken over? If it is taken over all n x n matrices, then $\hat{U} = U$, so presumably you are imagining taking the argmin over a different set. What this set is and what the metric is seem potentially crucial to an answer. – Joshua Grochow Mar 17 '12 at 18:26
Your formulation implies that any linear transformation A is acceptable to you as long as the product VA is close to U, but are you sure of this? – Tsuyoshi Ito Mar 17 '12 at 18:28
1  
@JoshuaGrochow even if the argmin is over all $n\times n$ matrices, it's not clear that it's possible to get $U$, so the question is still well defined (the implicit restriction on X is that it's the image of f(A) = VA) – Suresh Venkat♦ Mar 17 '12 at 18:44
@Suresh: That is what I first thought, but it is not correct. Note that if the argmin is really over all n×n matrices, then it has nothing to do with the product VA! – Tsuyoshi Ito Mar 17 '12 at 19:36
Right. So X has to be restricted to matrices that can be formed as VA for a fixed V – Suresh Venkat♦ Mar 17 '12 at 20:41

1 Answer

up vote 6 down vote accepted

If your error norm is the Frobenius distance (that is, $m(X, U) = \|X - U \|_F$, then there is a closed form for your problem. $A = V^+ U$, where $V^+$ is the Moore-Penrose pseudoinverse of $V$ (this is a generalized inverse for non-square matrices).

share|improve this answer
1  
Thanks. This is great. I'm curious whether there is a closed form solution if (1) we take $m$ to be the Schatten $p$-norm of $X - U$ for any $p$ (not just the Frobenius, where $p = 2$); or (2) we take $m$ to be the 2-norm--i.e. the spectral radius of $X - U$. If there is a solution for (2), I wonder whether it is general for a matrix norm induced by a vector $p$-norm for any $p$. – aaronsteven Mar 21 '12 at 21:02
It's a good question. Not sure I know the answer :) – Suresh Venkat♦ Mar 21 '12 at 23:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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