2
$\begingroup$

I have a set of vectors that I am trying to predict from another set of vectors using a matrix $W$. To find this matrix, I decide I want to minimize the $\ell^2$ norm of the error, e.g.:

$$ \text{find} \min_W \|y - Wx\|_2 \\ x,y \in \mathbb{C}^N \quad W\in \mathbb{C}^{N \times N} $$

Where $x$ and $y$ are respective vectors from their sets, and each pair is (I hypothesize) related to eachother by $W$. I start by expanding this out:

$$ \min_W \left[ (y - Wx)^H (y - Wx) \right] \\ = \min_W \left[ (y - Wx)^H y - (y - Wx)^H Wx \right] \\ = \min_W \left[ (y^H y - y^H Wx)^H - (x^H W^H y - x^H W^H Wx)^H \right] \\ = \min_W \left[ y^H y - x^H W^H y - y^H W^H x + x^H W^H W x \right] $$

Where $(\cdot)^H$ denotes Hermitian transpose. I want to take the derivative with respect to $W$ and set it equal to zero, but I'm having a hard time with the derivative as I'm not sure exactly how that works with Hermitian transposes. Taking a look at this page, it looks like I might be in trouble (e.g. I'm going about this the wrong way), but I wanted to pick your brains to see if you all had any ideas on how to move forward from here.

Thank you all!

EDIT Michael C. Grant has pointed out that this question is underdetermined, and he is right, if I only have a single $x$ and $y$. However I have a set of $x$ and $y$ vectors that I assume are related to eachother by $W$ (And since right now I am working with simulations, I can generate as many pairs of $x$'s and $y$'s as I want). This is a kind of "system identification" problem, where I have input-output correspondences and I'm trying to understand how the math is derived.

$\endgroup$
  • 1
    $\begingroup$ Given your clarification, then, I submit that you are not trying to solve the problem above, but rather something more like this:$$\begin{array}{ll}\text{minimize}_W & \|Y-WX\|_F\end{array}$$where $X,Y\in\mathbb{C}^{N\times M}$ with $M\geq N$. The norm here is the Frobenius norm, which when squared is basically the sum of the squares of all of the elements. Also, you might want to carefully check your transposes above--I think you may have at least one wrong in that last line of the minimization. $\endgroup$ – Michael Grant May 14 '13 at 19:24
  • $\begingroup$ This is a good insight. I'm going to go think about it! If I decide that I need help with this new formulation, should I open a new question, or edit this one appropriately? And thank you for your help! $\endgroup$ – staticfloat May 14 '13 at 19:25
  • $\begingroup$ I don't know, actually... but note that the matrix-valued problem with $X$ and $Y$ is just a least-squares problem. There's really no need to do derivatives per se. I'm going to edit my answer to offer a suggestion. $\endgroup$ – Michael Grant May 14 '13 at 19:26
4
$\begingroup$

Yes, I'd suggest that you are in trouble, but not for the reason you may think. :-) You can certainly take the derivative of that expression with respect to $W$.

But more fundamentally, your problem is underdetermined: you have $2N$ complex quantities $x$ and $y$ that you are using to construct a matrix $W$ with $N^2$ complex quantities.

If $x\neq 0$, the minimum value of the norm is zero, and any matrix that satisfies $Wx=y$ is going to attain this minimum value. For instance, $W=(x^Hx)^{-1}yx^H$ will do the trick. But you can add any other matrix $V$ satisfying $Vx=0$ to $W$ and achieve the same result.

If $x=0$, then the minimum value of the norm is $\|y\|$, and any $W$ will achieve it.

EDIT: OK, now we see the problem. What you really want to do is something like this:

$$\begin{array}{ll}\text{minimize}_W & \| Y - W X \|_F\end{array}$$ where $X,Y\in\mathbb{C}^{N\times M}$, with $M\geq N$. This is actually a standard least squares problem, though it may not seem so since it's expressed in matrix form. Using Kronecker products, we can write this as $$\begin{array}{ll}\text{minimize}_W & \| \mathop{\textrm{vec}}(Y) - (X^H\otimes I) \mathop{\textrm{vec}}(W) \|_2\end{array}$$ where $\otimes$ denotes the Kronecker product, and $\mathop{\textrm{vec}}$ stacks the columns of its matrix argument on top of one another. The normal equations for this least squares problem are $$ \begin{aligned} &(X^H\otimes I)^H (X^H\otimes I) \mathop{\textrm{vec}}(W) = (X^H\otimes I)^H \mathop{\textrm{vec}}(Y) \\ &\qquad \Longrightarrow\quad (X\otimes I) (X^H\otimes I) \mathop{\textrm{vec}}(W) = (X\otimes I) \mathop{\textrm{vec}}(Y) \\ &\qquad \Longrightarrow\quad (XX^H\otimes I) \mathop{\textrm{vec}}(W) = (X\otimes I) \mathop{\textrm{vec}}(Y) \\ &\qquad \Longrightarrow\quad WXX^H = YX^H \end{aligned} $$ Therefore, if $XX^H\in\mathbb{C}^{N\times N}$ is invertible---and note that's an important condition that is not guaranteed to be satisfied even if $M\geq N$---then the solution is $$W = YX^H(XX^H)^{-1}$$ The similarity to the single-vector case is not too surprising. If $XX^H$ is singular, then $$W=YX^H(XX^H)^\dagger$$ is a minimizer, where $(XX^H)^\dagger$ is the pseudoinverse of $XX^H$.

$\endgroup$
  • $\begingroup$ An excellent point. I have updated my answer to explain why this question is slightly better posed. Essentially, I have multiple $x$ and $y$ vectors that I can bring in to help narrow the problem down. $\endgroup$ – staticfloat May 14 '13 at 19:07
  • $\begingroup$ Excellent. This is exactly what I needed. I had apriori knowledge that $W = YX^H (X X^H)^{-1}$ but I could not figure out how to get there from the problem statement. I don't fully understand your answer, so I'd like to ask some questions. I understand your expansion with Kronecker products and such, but I don't understand how you isolate $vec(W)$ on the left hand side. I get the last conversion from Kronecker products back to plain matrix multiplication, but I have a hard time pulling things apart in my head for the step before that. Can you help me work that out? $\endgroup$ – staticfloat May 14 '13 at 19:45
  • $\begingroup$ Also, because the $vec(Z)$ operation transforms from a matrix to a vector, must we still use the Frobenius norm notation $\| \cdot \|_F$? It should be functionally equivalent to the $\ell^2$ norm again, right? $\endgroup$ – staticfloat May 14 '13 at 19:52
  • $\begingroup$ I've edited the text to include more intermediate steps, and to change the vector Frobenius norm to the 2 norm. $\endgroup$ – Michael Grant May 14 '13 at 20:31
  • $\begingroup$ I get it! Thank you so much! $\endgroup$ – staticfloat May 14 '13 at 21:26

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.