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? Jan 2, 2013 at 21:15
• Indeed, the transpose. Ill clarify, thanks.
– yoki
Jan 2, 2013 at 21:16
• For what it is worth, this is equal to the largest eigenvalue of $AA^{T}$ (size $40K\times 40K$). Jan 2, 2013 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, 2013 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. Jan 2, 2013 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 Jan 2, 2013 at 21:25
• You must normalize the vector before you multiply: $\widehat{v_{i-1}} = v_{i-1}/\|v_{i-1}\|$. Jan 2, 2013 at 21:35
• @Jonas I've edited the answer in case the hat notation isn't standard Jan 3, 2013 at 4:32