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$
7
  • $\begingroup$ Isn't that simply $\lambda_{1,2} = a^Tb$? $\endgroup$ Commented Jul 6, 2016 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$ Commented Jul 6, 2016 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$ Commented Jul 6, 2016 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$ Commented Jul 6, 2016 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$ Commented Jul 6, 2016 at 20:51

1 Answer 1

7
$\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$
4
  • $\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$ Commented Apr 4, 2017 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
    Commented Apr 4, 2017 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$ Commented Apr 4, 2017 at 19:01
  • $\begingroup$ @WolfgangBangerth Could you be any more arrogant? You ask such questions and you're a professor...? That's embarrassing, I'm glad I didn't take any of your classes. $\endgroup$ Commented Jul 15, 2021 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.