Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a large real matrix A of size $40K\times 400K$, is there an efficient way to calculate the largest eigenvalue of $A^T A$ (size $400K\times 400K$)?

Thanks.

share|improve this question
    
What is $A'$? The transpose? –  1015 Jan 2 '13 at 21:15
    
Indeed, the transpose. Ill clarify, thanks. –  ido Jan 2 '13 at 21:16
2  
For what it is worth, this is equal to the largest eigenvalue of $AA^{T}$ (size $40K\times 40K$). –  Jonas Meyer Jan 2 '13 at 22:29

1 Answer 1

up vote 8 down vote accepted

Assuming you want the eigenvalue of largest magnitude (not the largest positive eigenvalue) the most efficient algorithm is power iteration: pick an initial vector $v_0$, then iterate

$$v_i = A^T\left(A\frac{v_{i-1}}{\|v_{i-1}\|}\right).$$

Then $\|v_i\|$ will converge almost surely to the largest magnitude eigenvalue of $A^TA$.

EDIT: Notice that computing $A^TA$ is exceedingly expensive and does not need to be done; the utility of power iteration is that it finds the largest eigenvalue using only matrix-vector products. I've added parentheses to clarify.

EDIT 2: Of course, since $A^TA$ is symmetric positive-semidefinite, the eigenvalues are nonnegative and the largest magnitude eigenvalue is also the largest eigenvalue.

share|improve this answer
    
The problem is that it is too big for me to even calculate $A^T$. –  ido Jan 2 '13 at 21:21
1  
Note that you never explicitly compute $A^TA.$ You only need to compute matrix-vector products $Ax$ and $A^Tx$. If these operations are too expensive... you're out of luck, I'm afraid. –  user7530 Jan 2 '13 at 21:23
    
@user7530, Can you clarify what you mean by "almost surely"? If it does converge, how are you supposed to know if it or isn't the largest magnitude eigenvalue? Regards –  Amzoti Jan 2 '13 at 21:25
2  
You must normalize the vector before you multiply: $\widehat{v_{i-1}} = v_{i-1}/\|v_{i-1}\|$. –  user7530 Jan 2 '13 at 21:35
1  
@Jonas I've edited the answer in case the hat notation isn't standard –  user7530 Jan 3 '13 at 4:32

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.