7
$\begingroup$

I have a $n \times n$ symmetric positive definite matrix $A$ which I will repeatedly update using two consecutive rank-one updates of the form

$A' = A + e_j u^T +u e_j^T$

where $\{e_i: 1 \leq i \leq n\}$ is the standard basis.

I also compute the updates to $A^{-1}$ using Sherman-Morrison. Due to the nature of the updates, the matrix $A'$ is guaranteed to be non-singular and positive definite.

I would like to keep track of the largest and smallest eigenvalue of the matrix. Since I have the inverse, a method for calculating the largest (or smallest) eigenvalue would suffice.

I know I can calculate the eigendecomposition of $A$ and update it in $O(n^2)$ but I was wondering if there was a more efficient method seeing as I only care about one particular eigenvalue (and not at all about the eigenvectors).

A lower bound on the eigenvalue, might also be helpful, but it would have to be tight. Gershgorin discs seem too loose.

Finally, if I do have to go via the eigendecomposition route, any pointers to what algorithms are used in practice for computational efficiency and numerical stability?

$\endgroup$
  • $\begingroup$ you should have a look at the Power iteration method and related links like the Raileigh iteration method $\endgroup$ – Vincent Nivoliers Apr 3 '13 at 22:23
  • $\begingroup$ Thanks! I have looked a bit into those, but they seem to also be at least $O(n^2)$. Also I am not sure how fast these converge in practice... $\endgroup$ – Tzonathan Apr 3 '13 at 22:32
  • 1
    $\begingroup$ I'm no specialist, but when your matrices are sparse, these methods get faster. By the way, isn't it $e_ju^T + ue_j^T$ for your update ? Otherwise I believe you are adding matrices and reals. If I didn't understand, provided that $A$ is initially sparse, the first iterations are sparse as well. $\endgroup$ – Vincent Nivoliers Apr 3 '13 at 22:37
  • $\begingroup$ Thanks again. I corrected the formula. $A$ unfortunately isnt sparse. Besides, isnt even one iteration of the power iteration method $O(n^2)$ or am I missing something? $\endgroup$ – Tzonathan Apr 3 '13 at 22:58
  • $\begingroup$ If your matrices are not sparse, it is indeed the complexity of one step, and therefore these methods are not well suited to your problem. $\endgroup$ – Vincent Nivoliers Apr 3 '13 at 23:10
1
$\begingroup$

You could use randomized SVD to get the dominant eigenvectors of $A'$ and $(A')^{-1}$ through application of them to a handful of random test vectors. It's a probabilistic method, but there are rigorous bounds on the failure probability in terms of the number of test vectors, and you don't have to use very many test vectors before the probability of failure becomes absurdly small like $1e-10$.

You can just keep the same random test vectors from step to step and then you don't have to reapply the original matrix $A$ in subsequent steps.

$\endgroup$
0
$\begingroup$

I am no expert in this field. Here are some obvious bounds, but I am not sure if they can help. $$\lambda_\max(A')=\max\{x^TA'x = x^TAx + 2x_j\langle x,u\rangle:\|x\|_2=1\}.$$ By triangle inequality, an obvious upper bound is $\lambda_\max(A') \le \lambda_\max(A) + 2\|u\|$. Equality occurs when $u$ is a multiple of $e_j$ and $e_j$ is an eigenvector corresponding to $\lambda_\max(A)$.

By considering the three cases $x_j=0,\, x=\frac{u}{\|u\|}$ and $x=e_j$, an obvious lower bound is given by $$\lambda_\max(A') \ge \max\left\{\lambda_\max(A_j),\ \frac{u^TAu}{\|u\|^2} + 2u_j,\ a_{jj} + 2u_j\right\}, $$ where $A_j$ denotes the submatrix of $A$ obtained by removing the $j$-row and the $j$-th column. Equality occurs when, for instance, $A=I$ and $u=e_j$. Using the interlacing inequality, you may get a somewhat weaker bound by replacing $\lambda_\max(A_j)$ with $\lambda_2^\downarrow(A)$, the second largest eigenvalue of $A$.

$\endgroup$

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.