Modified Eigenvalue Problems

Suppose we know an eigen decomposition $B=K\Phi K'$ of a real symmetric matrix $B$ of order $n$ , and we want to find an eigen decomposition of the rank-one modification $A=B+\gamma cc'$ , where $\gamma\not= 0$ . The problem was first discussed systematically by Golub [1973]. Also see Bunch, Nielsen, and Sorensen [1978] for a more detailed treatment and implmentation.

Eigen-pairs of $A$ must satisfy $(B+\gamma cc')x=\lambda x.$ Change variables to $y=K'x$ and define $d\mathop{=}\limits^{\Delta}K'c$ . For the time being suppose all elements of $d$ are non-zero and all elements of $\Phi$ are different, with $\phi_1>\cdots>\phi_n$ .

We must solve $(\Phi+\gamma dd')y=\lambda y,$ which we can also write as $(\Phi-\lambda I)y=-\gamma (d'y)d.$

Suppose $(y,\lambda)$ is a solution with $d'y=0$ . Then $(\Phi-\lambda I)y=0$ and because all $\phi_k$ are different $y$ must be a vector with a single element, say $y_k$ , not equal to zero. But then $d'y=y_kd_k$ , which is non-zero. Thus $d'y$ is non-zero at a solution, and because eigenvectors are determined up to a scalar factor we may as well require $e'y=1$ .

Now solve $\begin{align*} (\Phi-\lambda I)y&=-\gamma d,\\ d'y&=1. \end{align*}$ At a solution we must have $\lambda\not=\phi_i$ , because otherwise $d_i$ would be zero. Thus $y_i=-\gamma \frac{d_i}{\phi_i-\lambda},$ and we can find $\lambda$ by solving $1+\gamma\sum_{i=1}^n\frac{d_i^2}{\phi_i-\lambda}=0.$ If we define $f(\lambda)=\sum_{i=1}^n\frac{d_i^2}{\phi_i-\lambda},$ then we must solve $f(\lambda)=-\frac{1}{\gamma}$ . Let's first look at a particular $f$ .

plot of chunk secular1

Figure 1: Linear Secular Equation

We have $f'(\lambda)>0$ for all $\lambda$ , and $\lim_{\lambda\rightarrow-\infty}f(\lambda)=\lim_{\lambda\rightarrow+\infty}f(\lambda)=0.$ There are vertical asymptotes at all $\phi_i$ , and between $\phi_i$ and $\phi_{i+1}$ the function increases from $-\infty$ to $+\infty$ . For $\lambda<\phi_n$ the function increases from 0 to $+\infty$ and for $\lambda>\phi_1$ it increases from $-\infty$ to 0. Thus the equation $f(\lambda)=-1/\gamma$ has one solution in each of the $n-1$ open intervals between the $\phi_i$ . If $\gamma<0$ it has an additional solution smaller than $\phi_n$ and if $\gamma>0$ it has a solution larger than $\phi_1$ . If $\gamma<0$ then $\lambda_n<\phi_n<\lambda_{n-1}<\cdots<\phi_2<\lambda_1<\phi_1,$ and if $\gamma>0$ then $\phi_n<\lambda_n<\phi_{n-1}\cdots<\phi_2<\lambda_2<\phi_1<\lambda_1.$ Finding the actual eigenvalues in their intervals can be done with any root-finding method. Of course some will be better than other for solving this particular problem. See Melman [1995], [1997] [1998] for suggestions and comparisons.

We still have to deal with the assumptions that the elements of $d$ are non-zero and that all $\phi_i$ are different. Suppose $p$ elements of $d_i$ are zero, without loss of generality it can be the last $p$ . Partition $\Phi$ and $d$ accordingly. Then we need to solve the modified eigen-problem for $\begin{bmatrix} \Phi_1+\gamma d_1d_1'&0\\ 0&\Phi_2 \end{bmatrix}.$ But this is a direct sum of smaller matrices and the eigenvalues problems for $\Phi_2$ and $\Phi_1+\gamma d_1d_1'$ can be solved separately.

If not all $\phi_i$ are different we can partitioning the matrix into blocks corresponding with the, say, $p$ different eigenvalues. $\begin{bmatrix} \phi_1I+\gamma d_1d_1'&\gamma d_1d_2'&\cdots&\gamma d_1d_p'\\ \gamma d_2d_1'&\phi_2I+\gamma d_2d_2'&\cdots&\gamma d_2d_p'\\ \vdots&\vdots&\ddots&\vdots\\ \gamma d_pd_1'&\gamma d_pd_2'&\cdots&\phi_pI+d_pd_p' \end{bmatrix}.$ Now use the $p$ matrices $L_s$ which are square orthonormal of order $n_s$ , and have their first column equal to $d_s/\|d_s\|.$ Form the direct sum of the $L_s$ and compute $L_s'(\Phi+\gamma dd')L_s$ . This gives $\begin{bmatrix} \phi_1I+\gamma\|d_1\|^2 e_1e_1'&\gamma\|d_1\|\|d_2\|e_1e_2'&\cdots&\gamma\|d_1\|\|d_p\|e_1e_p'\\ \gamma\|d_2\|\|d_1\|e_2e_1'&\phi_2I+\gamma\|d_2\|^2e_2e_2'&\cdots&\gamma\|d_2\|\|d_p\|e_2e_p'\\ \vdots&\vdots&\ddots&\vdots\\ \gamma \|d_p\|\|d_1\|e_pe_1'&\gamma \|d_p\|\|d_2\|e_pe_2'&\cdots&\phi_pI+\gamma\|d_p\|^2e_pe_p' \end{bmatrix}$ with the $e_s$ unit vectors, i.e. vectors that are zero except for element $s$ that is one.

A row and column permutation makes the matrix a direct sum of the $p$ diagonal matrices $\phi_s I$ of order $n_s-1$ and the $p\times p$ matrix $\begin{bmatrix} \phi_1+\gamma\|d_1\|^2 &\gamma\|d_1\|\|d_2\|&\cdots&\gamma\|d_1\|\|d_p\|\\ \gamma\|d_2\|\|d_1\|e_2e_1'&\phi_2+\gamma\|d_2\|^2&\cdots&\gamma\|d_2\|\|d_p\|\\ \vdots&\vdots&\ddots&\vdots\\ \gamma \|d_p\|\|d_1\|e_pe_1'&\gamma \|d_p\|\|d_2\|&\cdots&\phi_p+\gamma\|d_p\|^2 \end{bmatrix}$ This last matrix satisfies our assumptions of different diagonal elements and nonzero off-diagonal elements, and consequently can be analyzed by using our previous results.

A very similar analysis is possible for modfied singular value decomposition, for which we refer to Bunch and Nielsen [1978].