Large scale SVD
SVD is a popular approach for factorization of a matrix and has several applications in many domains. It proceeds by factorizing a given matrix A m x n as A = UΣV^T, where U is a m x m unitary matrix, i.e. U^TU=I, Σ is a m x n diagonal matrix consisting of the eigenvalues and V is a n x n unitary matrix. It is popularly used to find the rank k approximation of a given matrix. One of the main problems of using SVD for large matrices is the computation of the eigenvector decomposition. Lets see how the eigenvector decomposition can be carried out for large sparse matrices. Power Iteration : One of the simplest methods of computation of the largest eigenvalue of a large sparse matrix is the power iteration. It however only computes a single largest eigenvalue and may converge very slowly. The algorithm is as follows: Start with a random vector b0 b_{k+1} = Ab_k || Ab_k|| This algorithm converges to the largest eigenvalue under the assumption that there is a si