2
$\begingroup$

I have an equation and I want to know why it is true. It can be found in Boyd's Convex Optimization book, page 82, line 11-12. It is example 3.9.

\begin{equation} b^T W A (A^T W A)^{-1} A^T W b = \displaystyle\sum\limits_{i=1}^n w_i^2 b_i^2 a_i^T (\displaystyle\sum\limits_{j=1}^n w_j a_j a_j^T)^{-1} a_i \end{equation}

W is a diagonal matrix with size nxn. A is any matrix with size nxm, we designate the term $a_i^T$ to be the i-th row of A. b is a vector with size nx1. So the left and right sides of the equation is a number.

I tried simplifying $b^T W A$ and $A^T W b$, so: \begin{equation} b^T W A = b_1 w_1 a_1^T + b_2 w_2 a_2^T + \cdots + b_n w_n a_n^T. \end{equation}

$$A^T w b = (a_1^T)^T w_1 b_1 + (a_2^T)^T w_2 b_2 + \cdots + (a_n^T)^T w_n b_n$$ $$= a_1 w_1 b_1 + a_2 w_2 b_2 + \cdots + a_n w_n b_n$$ Note that a_i means the i-th column of A.

Also, the inverse can be expressed as such:

$$(A^T W A)^{-1} = (w_1 a_1 a_1^T + w_2 a_2 a_2^T + \cdots + w_n a_n a_n^T)^{-1} $$ $$= (\displaystyle\sum\limits_{j=1}^n w_j a_j a_j^T)^{-1}$$

Then, the question is how do I move the coefficients around so that they match the stated expression? That is, why is this true:

$$(b_1 w_1 a_1^T + b_2 w_2 a_2^T + \cdots b_n w_n a_n^T) (\displaystyle\sum\limits_{j=1}^n w_j a_j a_j^T)^{-1} (a_1 w_1 b_1 + a_2 w_2 b_2 + \cdots + a_n w_n b_n) $$ $$= \displaystyle\sum\limits_{i=1}^n w_i^2 b_i^2 a_i^T (\displaystyle\sum\limits_{j=1}^n w_j a_j a_j^T)^{-1} a_i$$

Thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

I think this is a mistake in the book. The equation is saying that the symmetric matrix between $b^\mathrm{T}$ and $b$ on the left-hand side is diagonal; else there would have to be cross-terms $b_i b_k$ with $i\neq k$ on the right-hand side. But unless there are further conditions on $A$ and $W$, there's no reason for that matrix to be diagonal; in fact you can easily find examples where it isn't, with $W$ the identity and $A$ some small non-square matrix.

More generally, though, to bring the $b$s and $W$s together in an expression like the one on the left-hand side, you can use the cyclic invariance of the trace:

$$\begin{eqnarray} b^T W A (A^T W A)^{-1} A^T W b&=& \mathrm{Tr}\left[b^T W A (A^T W A)^{-1} A^T W b\right]\\\ &=&\mathrm{Tr}\left[W b b^T W A (A^T W A)^{-1} A^T\right]\;. \end{eqnarray}$$

$\endgroup$
6
  • $\begingroup$ Actually, in the book $W$ is diagonal (it's the diagonal matrix of weights in a weighted least squares problem) see p.95 of the pdf-file here: stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf and it's also assumed that $A^T W A$ is positive definite. $\endgroup$
    – t.b.
    Commented Mar 19, 2011 at 22:34
  • $\begingroup$ @Theo: Yes, but the weights in a weighted least squares problem are arbitrary, so that doesn't restrict $W$ beyond being diagonal (which was stated in the question and doesn't imply that the matrix of the quadratic form as a whole is diagonal). $\endgroup$
    – joriki
    Commented Mar 19, 2011 at 22:36
  • $\begingroup$ Interesting, the term $W A (A^T W A)^{-1} A^T W$ is, in fact, diagonal (or was for my test case). I forgot to mention that $A^T W A$ is positive definite. I also tested the last two lines of my question post in MATLAB and they both agree with the original equation. So, all three versions give the same result. I am now trying to figure why $W A (A^T W A)^{-1} A^T W$ is diagonal, with W diagonal, and $A^T W A \succ 0$. $\endgroup$
    – jrand
    Commented Mar 19, 2011 at 22:41
  • $\begingroup$ When you say "is, in fact, diagonal", do you mean for some particular values of $W$ and $A$? For $W$ the identity and $A$ a general non-square matrix I get a non-diagonal matrix: bit.ly/eomB7v $\endgroup$
    – joriki
    Commented Mar 19, 2011 at 22:50
  • $\begingroup$ @jrand, definitely not diagonal in general. Did you, say, pick a square $A$ of full rank for your test? In that case, I definitely believe you'd get a diagonal matrix. In fact, you'd recover $W$ itself! $\endgroup$
    – cardinal
    Commented Mar 19, 2011 at 22:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .