2
$\begingroup$

I'm writing some code on a distributed platform, using some programming language like Hadoop, and now I need to calculate the K smallest eigenvalues for a Large Matrix.

K is a small constant at most 100. The Matrix is real symmetric and positive semi-definite, but it's large such as 50000 * 50000 matrix. And it ensures all the eigenvalues are non-negative.

I know there are many methods to solve the question, e.g. QR algorithm (based on writing the matrix as a product of an orthogonal matrix and an upper triangular matrix)

But due to the restriction of the platform, it only supports the matrix computation as below:

  1. the sum, difference or product of two matrix
  2. Matrix can be multiplied or divides by a real number
  3. dot product of two vector
  4. the trace or transpose of a Matrix
  5. restricted SVD(Singular Value Decomposition) of a Matrix. Since the matrix $A$ is real symmetric, we get $A^*=A$. I multiply $A$ by itself and have $B=A^*A=A^2$, so the singular value of $B$ is the square of the eigenvalue of $A$, that's the method what I tried before .But the SVD on the platform can only show the 1024 largest singular values of the Matrix(what I need is K smallest), that's why I call it "restricted"

There are also some other methods I write it by myself, such as getting any row or column of the Matrix, but it's not efficient and the cost time is O(n^2),where n is the matrix row size.So if possible, I hope your advice would use the methods not too much, thanks a lot

I have tried to solve the question for 2 weeks, but it seems too hard for me. Any information useful for my question is fine , thank you :D

$\endgroup$
  • $\begingroup$ FYI singular values are not square roots of eigenvalues for symmetric positive definite matrices. They coincide with eigenvalues. However if your matrix $B=A^TA$ where $A$ is rectangular Nx50000 matrix then indeed singular values of $A$ are square roots of eigenvalues of $B$. $\endgroup$ – Alexander Vigodner Jul 7 '14 at 21:34
  • $\begingroup$ I am not sure with efficiency, however you can run SVD about 50 times, cleaning on each step your matrix from the largest eigenvalues. This is stupid but it will use only your methods. $\endgroup$ – Alexander Vigodner Jul 7 '14 at 21:41
  • $\begingroup$ @AlexanderVigodner Thank for your information. I forgot something and just changed the method I tried to get the eigenvalues (see the 5th item in the list of the question above). And I'm not sure what's your meaning of "cleaning on largest eigenvalues", maybe your meaning is reducing the matrix size after SVD, or doing some transform of the matrix and getting a new matrix(Its eigenvalues consist of some zeros and the small eigenvalues of the old one )? $\endgroup$ – labud Jul 8 '14 at 17:08
  • $\begingroup$ I mean on each iteration clean the matrix $B_{i+1}=B_{i}-Z_i$, where $Z_i=U_i \Lambda_i U_i^T$, $\Lambda_i$ is diagonal of 1024 largest eigenvalues and $U_i$ are corresponding eigenvectors. It is slow and stupid, but I don't see a simpler solution. $\endgroup$ – Alexander Vigodner Jul 8 '14 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.