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
    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
    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