Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Find a closed-form solution for vector $A$ minimizing the expression$$\frac{1}{2}\left|W(\Phi A-F)\right|^2$$ where $W$ is non-singular diagonal, $\Phi$ is full rectangular matrix, and $A$, $F$ are column vectors (of possibly different dimensions); $|\bullet|^2\equiv\bullet^T \cdot \bullet$.

Motivation: The problem in question finds the best projection $A$ of point-wise function $F$ into space generated by basis $\Phi$, where points are weighted with diagonal matrix W. Basis dimension (number of rows of $\Phi$, length of $A$) and number of points, where $F$ is defined (columns of $\Phi$, size of $W$ and length of $F$) are different.

EDIT: ANSWER ATTEMPT: I did the following algebra, is it correct?

$\begin{align} \frac{1}{2}\left|W(\Phi A-F)\right|^2&=\frac{1}{2}(W\Phi A-WF)^T(W\Phi A -WF)=\\&=((W\Phi A)^T-(WF)^T)(W\Phi A -WF)=\\ &=\frac{1}{2}\left[A^T\Phi^TW^2\Phi A-A^T\Phi^T W^2 F - F^TW^2\Phi A+F^TW^2F \right] \end{align}$

(making use of $W^TW=W^2$) With rules for matrix calculus from wikipedia:

$\begin{align} \frac{\partial}{\partial A}\bullet&=\frac{1}{2}\left[\Phi^T W^2\Phi A +(\Phi^T W^2\Phi)^TA-\Phi^TW^2F-(F^TW^2\Phi)^T\right] =\\ &=\Phi^T W^2 \Phi A - \Phi^TW^2F \end{align}$

Setting the first derivative equal to zero vector yields $\Phi^T W^2\Phi A=\Phi^TW^2F$, from which finally

$\boxed{A=(\Phi^TW^2\Phi)^{-1}\Phi^TW^2F}$

I suppose no further simplification is possible (in particular expanding the inversion to $(W\Phi)^{-1}(\Phi^T W^T)^{-1}$ produces matrix size mismatch, therefore is not possible).

EDIT2: after looking around at wikipedia, I found out I derived normal equation for weighted least-squares (that article uses $\hat\beta$, $W$, $X$, $y$ where I used $A$, $W^2$, $\Phi$, $F$).

share|improve this question
    
I think something is wrong. If $A,\Phi,$ and $F$ are column vectors, then $A^T\Phi$ is a scalar so $A^T\Phi-F$ = scalar - vector??? –  Bill Cook Oct 12 '11 at 14:20
    
Oops, sorry, edited. $\Phi$ is square matrix. –  eudoxos Oct 12 '11 at 14:25
    
@user1551: diagonal $\equiv$ zeros off-diagonal, which implies symetry (I will remove the $W=W^T$ from the post though, it is redundant); non-singular = no zeros on the diagonal. What is unclear? –  eudoxos Oct 12 '11 at 14:44
    
Oops, I am having a bad day today, sorry. Should be $\Phi A$, fixed. –  eudoxos Oct 12 '11 at 15:00

2 Answers 2

up vote 1 down vote accepted

Edit: Your derivation is correct, except perhaps the last step -- when your system is under-determined, i.e. when $\Phi$ is "wide" instead of square or "tall", the product $\Phi^TW^2\Phi$ is bound to be rank-deficient and hence non-invertible. In this case you must use pseudoinverse.

share|improve this answer
    
Thanks, I know about the pseudo-inverse, but was trying to derive it somehow directly. Contrary to what you write, I arrived at a closed-form solution, did I do some mistake then? Or is it in this particular case that is exists? –  eudoxos Oct 12 '11 at 23:31
    
I guess you assumed my problem was over-determined, but in fact it is not: there is as many elements in $A$ as there is conditions on the derivative. Hence pseudo-inversion does not come into play at all, explaining why I god the closed-form solution. –  eudoxos Oct 13 '11 at 0:05
    
$\Phi$ is not invertible, being rectangular. If it were, the solution would get simplified as you say. –  eudoxos Oct 13 '11 at 14:26
    
Right, that would be a degenerate case. –  eudoxos Oct 15 '11 at 7:28

Substituting $C = W\Phi$ and $B = WF$ will reduce your problem to a form: $$\min \left|CA-B\right|^2$$

whose norm minimizing solution is available "by inspection": $$A = C^{+}B = (W\Phi)^{+} WF$$

Your particular $W$ matrix is diagonal, so $W^TW = W^2$.

Further, assuming that $C^TC$ has full rank, you can use the expansion $C^+ = (C^TC)^{-1}C^T$ to produce the boxed form of your solution.

share|improve this answer
    
I like this "by inspection" (seriously; though it is "obvious" only if you had done that derivation properly in your life already, I guess). Though the use of pseudo-inverse is not necessary, the system is not over-determined ($A$ is unknown vector, and the zero conditions hold for all derivatives with respect to $A_i$); I should have stressed that perhaps. –  eudoxos Oct 15 '11 at 7:27

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.