7
$\begingroup$

In deriving a Newton scheme, I end up with a Jacobian matrix of the form $J=I+ab^T$ where $a,b$ are vectors. For practical reasons, I want to approximate it by a symmetric positive definite matrix. Symmetrizing is easy: replace it by $J \approx I+\frac 12(ab^T+ba^T)$. But the (now real) eigenvalues may still be negative, so I further approximate $J \approx \tilde J := I+\frac 12\alpha (ab^T+ba^T)$ where I want to choose $\alpha$ so that $\tilde J$ is s.p.d.

To choose $\alpha$, I need the eigenvalues of the matrix $ab^T$. This ought to be simple enough, but I must be missing the key step to find a closed-form expression for the eigenvalues. Clearly, there will be at most two non-zero eigenvalues, and the corresponding eigenvectors must lie in the plane spanned by the vectors $a,b$. The eigenvalues are then the minimal and maximal value of the Rayleigh quotient $$ R(x) := \frac{x^T (ab^T) x}{x^T x} = \frac{(a^Tx) (b^Tx)}{x^T x} $$ over all $x \in \text{span}(a,b)$.

I suspect that there is a closed form expression for the minimal and maximal value of $R(x)$, but its form eludes me.

$\endgroup$
  • $\begingroup$ Isn't that simply $\lambda_{1,2} = a^Tb$? $\endgroup$ – Christian Clason Jul 6 '16 at 13:08
  • 3
    $\begingroup$ Sorry, should be $\lambda = a^Tb$, because $ab^T$ is rank 1 and therefore only has one non-zero eigenvalue (with eigenvector $a$). $\endgroup$ – Christian Clason Jul 6 '16 at 13:15
  • 2
    $\begingroup$ $(ab^T)a=(b^Ta)a$ implies that the right-eigenvector is $a$ and the eigenvalue is $b^Ta$ $\endgroup$ – Richard Zhang Jul 6 '16 at 13:56
  • 1
    $\begingroup$ Also, since $ab^T$ is nonsymmetric in general, the maximal absolute value of its Rayleigh quotient (i.e. its numerical radius) is in general strictly larger than its maximum absolute eigenvalue (i.e. its spectral radius). $\endgroup$ – Richard Zhang Jul 6 '16 at 14:00
  • $\begingroup$ Ah, interesting question. Maybe I have managed to mislead myself then. What I want is that $\tilde J$ is positive definite. For this, I actually need the minimal value of $R(x)$ (i.e., the most negative value, if $R(x)$ can actually be negative). As @RichardZhang points out, this may be a question unconnected to the eigenvalue(s) of $ab^T$. $\endgroup$ – Wolfgang Bangerth Jul 6 '16 at 20:51
6
$\begingroup$

This is sometimes known as Buzano's inequality (http://www.jstor.org/stable/2159168). In general, if $\|x\|=1$, $P=xx^{\top}$ is a projection operator, so a simple application of Cauchy-Schwarz leads to $$ 2|b^{\top}xx^{\top}a|-|b^{\top}a| \leq |b^{\top}(2P-I)a| \leq \|a\|\,\|b\|, $$ which gives Buzano's inequality $$ |b^{\top}xx^{\top}a| \leq \frac{\|a\|\,\|b\|+|a^{\top}b|}{2}. $$

Without loss of generality let $a=(1,0)$, $b=(p,q)$ ($p^2+q^2=1$, $q\geq0$) and $x = (\alpha, \beta)$ ($\alpha^2+\beta^2=1$, $\alpha\geq0$). Finding the extrema of $ b^{\top}xx^{\top}a = \alpha(\alpha p+\beta q)$ is easily done with Lagrange multipliers, giving the values $$ \frac{p\pm1}{2}. $$ Here $p = \frac{a^{\top}b}{\|a\|\|b\|} = \cos\angle ab$.

From this $$ \frac{a^{\top} b-\|a\|\|b\|}{2} \|x\|^2 \leq a^{\top} xx^{\top}b \leq \frac{ a^{\top}b+\|a\|\|b\|}{2} \|x\|^2 $$ (with both inequalities being tight) so the admissible values of $\alpha$ are given by $$ 1 + \tfrac12(p\pm1)\alpha \|a\|\|b\| > 0, \qquad \frac{-2}{\|a\|\|b\| + a^{\top}b} < \alpha < \frac{2}{\|a\|\|b\|-a^{\top}b}. $$

$\endgroup$
  • $\begingroup$ it's been a while since you wrote this response, and I greatly appreciate it. Out of curiosity, do you agree that Buzano's inequality is not actually necessary? Starting with "Finding the extrema..." you have a second line of reasoning that leads to the result by simply computing the maximum and minimum eigenvalue directly, without apparent recourse to Buzano's inequality. $\endgroup$ – Wolfgang Bangerth Apr 4 '17 at 17:47
  • $\begingroup$ @WolfgangBangerth I think you're right. I don't remember, but I probably just found the inequality first, so then it became part of the answer. $\endgroup$ – Kirill Apr 4 '17 at 18:06
  • $\begingroup$ Then I made the same mistake as you -- I sat down to write out the argument (for the substantially more complex case I actually have) and tried to first make it via Buzano's inequality -- just to remove it all again when I realized that the whole thing can actually be done by just computing the min/max of the Rayleigh quotient by hand. $\endgroup$ – Wolfgang Bangerth Apr 4 '17 at 19:01

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.