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



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

  • $\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. Mar 19 '11 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 Mar 19 '11 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 Mar 19 '11 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 Mar 19 '11 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 Mar 19 '11 at 22:52

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.