1
$\begingroup$

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$).

  • 0
    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???2011-10-12
  • 0
    Oops, sorry, edited. $\Phi$ is square matrix.2011-10-12
  • 0
    @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?2011-10-12
  • 0
    Oops, I am having a bad day today, sorry. Should be $\Phi A$, fixed.2011-10-12

2 Answers 2

1

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.

  • 0
    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?2011-10-12
  • 0
    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.2011-10-13
  • 0
    $\Phi$ is not invertible, being rectangular. If it were, the solution would get simplified as you say.2011-10-13
  • 0
    Right, that would be a degenerate case.2011-10-15
0

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.

  • 0
    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.2011-10-15