Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a Symmetric Positive Semi-Definite matrix $A$ which i know its eigenvalue and eigenvectors. let $v$ and $u$ be a random column vector. i want to know if it is possible to have eigenvalues of matrix $A+uv^T$.

I don't need its eigenvectors, but it is required to have the most precise eigenvalues. We know that $uv^T$ is also a rank one PSD matrix.

Is there a close form to this problem?

${\bf PS:}$ As you see i found the solution, but after implementation of this i can see a very small error in result, it would be appreciated if anyone know why this is happening, because we didn't used any approximation to get the result and it should be exact.

share|improve this question
    
Your "solution" is an order-1 approximation of the variation in the eigenvalues. –  Federico Poloni Nov 7 '12 at 19:01
    
Thank you Federico, I appreciate you helpful tip, i hope you would give me some references about this. Regards –  Amin Nov 8 '12 at 4:04
add comment

2 Answers

Complementing Denis's answer, you can look at the paper Some Modified Matrix Eigenvalue Problems by Golub (http://www.jstor.org/stable/2028604) where this issue is treated at some length.

share|improve this answer
    
Dear Felix As i read the paper its about updating a diagonal matrix. im not 100% sure if i got that right but the $A$ matrix is not diagonal, its a Symmetric PSD matrix. Regards –  Amin Nov 7 '12 at 4:40
    
If you know the eigenvalues and eigenvectors of $A$, then you can reduce to the case in which it is diagonal. –  Federico Poloni Nov 7 '12 at 18:58
add comment

Found the solution in [1], Please let me know if i had any mistake.

we have

$Ax=\lambda x$ (1)

differentiate both side we have

$\Delta Ax+ A\Delta x= \Delta\lambda x+\lambda\Delta x$.

multiply both side with $x^T$ and we have

$x^T\Delta Ax+ x^TA\Delta x= x^T\Delta\lambda x+x^T\lambda\Delta x$ (2)

from (1), by transposing both side we have $x^TA^T=\lambda x^T$. because $A$ is symmetric, we can eliminate the transpose of $A$.

$x^TA=\lambda x^T$

know we can eliminate last terms in both side because equality of them.

$x^T\Delta Ax= x^T\Delta\lambda x$

after a simple manipulation we get

$\frac{x^T\Delta Ax}{x^Tx}= \Delta\lambda $

As we know $x^Tx=1$ the final result will be

$ \Delta\lambda={x^T\Delta Ax} $

[1] Ning, H., Xu, W., Chi, Y., Gong, Y., & Huang, T. S. (2010). Incremental spectral clustering by efficiently updating the eigen-system. Pattern Recognition, 43(1), 113-127.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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