# Largest eigenvalue of a $A^T A$ matrix?

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.

-
What is $A'$? The transpose? – 1015 Jan 2 '13 at 21:15
Indeed, the transpose. Ill clarify, thanks. – yoki Jan 2 '13 at 21:16
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

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.

-
The problem is that it is too big for me to even calculate $A^T$. – yoki Jan 2 '13 at 21:21
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
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
@Jonas I've edited the answer in case the hat notation isn't standard – user7530 Jan 3 '13 at 4:32