I have a sparse matrix $A \in \mathbb{R}^{n \times l^{2}}$, and I want to calculate the eigenvalue decomposition of $A^{\top}A$. Since $A^{\top}A$ is positive semidefinite, all the eigenvalues are non-negative. Is there a fast way to accomplish this?
I remember reading on Mathoverflow that eigenvalue decomposition takes the same time as matrix multiplication. Since there is a much faster way to calculate sparse matrix multiplication. I wonder if techniques exist for eigenvalue decomposition.
The context is not necessary, but this arises in some first order method of solving $\operatorname{min}_{Q\succeq 0}\|A vec(Q) - b \|^{2}$. I want to find $\sum_{i=1}^{l^{2}}\sqrt{ \sigma_{i} }u_{i}$ where $\sigma_{i}$ are the eigenvalues and $u_{i}$ are the corresponding eigenvectors.