Suppose that $\bf A$ is an $n \times n$ matrix, and $\bf u$ and $\bf v$ are vectors. The matrix determinant lemma lets us easily compute the determinant of ${\bf A} + {\bf u} {\bf v}^\top$, while the Sherman-Morrison formula gives us the inverse. Is there anything at all that can be said about the spectral radius of ${\bf A} + {\bf u} {\bf v}^\top$? (Any kind of bounds would be a help.)
4
-
$\begingroup$ A trivial bound is $r\le \|A\|+\|u\|\, \|v\|$, and I doubt that much more can be said in general. In particular, it's definitely not possible to bound $r(A+uv^t)$ in terms $r(A)$ and $\|u\|$, $\|v\|$, as simple examples show. $\endgroup$– Christian RemlingCommented Jun 20, 2015 at 18:28
-
$\begingroup$ Thanks! That's basically my impression too, but figured it was worth a shot. $\endgroup$– user47305Commented Jun 20, 2015 at 18:39
-
$\begingroup$ I'm not sure I understand why $r\le ||A||+||u||||v||$. $\endgroup$– Alexander MathiasenCommented Aug 28, 2020 at 13:49
-
$\begingroup$ @AlexanderMathiasen I assume it's using the spectral norm as an upper bound. Take a look at the answer I just posted. $\endgroup$– Rodrigo de AzevedoCommented May 10, 2023 at 13:05
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
To complement Christian's comment, since the spectral radius is upper-bounded by the spectral norm,
$$\begin{aligned} \rho \left( {\bf A} + {\bf u} {\bf v}^\top \right) &\leq \left\| {\bf A} + {\bf u} {\bf v}^\top \right\|_2 \\ &\leq \left\| {\bf A} \right\|_2 + \left\| {\bf u} {\bf v}^\top \right\|_2 \\ &= \left\| {\bf A} \right\|_2 + \left\| {\bf u} \right\|_2 \left\| {\bf v} \right\|_2 \end{aligned}$$
$\begingroup$
$\endgroup$
Arguably, the simplest case is where the matrix $\bf A$ is symmetric and positive semidefinite (PSD) and ${\bf u} = {\bf v}$, which ensures that the eigenvalues of the rank-$1$ update are in $\Bbb R_0^+$. Hence,
$$ \begin{array}{ll} \underset {t \in \Bbb R} {\text{minimize}} & t \\ \text{subject to} & {\bf A} + {\bf u} {\bf u}^\top \preceq t \, {\bf I}_n \end{array} $$
which, via the Schur complement, can be rewritten as the following semidefinite program (SDP)
$$ \begin{array}{ll} \underset {t \in \Bbb R} {\text{minimize}} & t \\ \text{subject to} & \begin{bmatrix} t \, {\bf I}_n - {\bf A} & {\bf u}\\ {\bf u}^\top & 1 \end{bmatrix} \succeq {\bf O}_{n+1} \end{array} $$
This is not very satisfactory, but it may be better than nothing.