LMSVD

Limited Memory Block Krylov Subspace Optimization
for Computing Dominant Singular Value Decompositions

Introduction

LMSVD is a MATLAB solver for computing dominant singular value decompositions of large and dense or unstructured matrices. The approach is based on a block Krylov subspace optimization technique which significantly accelerates the classic simultaneous iteration method.

Consider a real matrix $Ain R^{mtimes n}$ ( m le n without loss of generality) and a given positive integer k le min(m,n) . The task is to find two orthogonal matrices $U_k=[u_1,ldots,u_k]in R^{mtimes k}$ and $V_k=[v_1,ldots,v_k]in R^{ntimes k}$ , and a diagonal matrix $Sigma_kin R^{ktimes k}$ whose diagonal entries are the largest singular values of , say, $sigma_1 geqcdots geqsigma_{k} ge 0$ , such that

$A_k := U_k Sigma_k V_k^top= sum_{i=1}^k sigma_i u_i v_i^top = {argmin_{rank(W)le k} ; |A-W|_F}$

The approximation A_k is called the -th dominant singular value decomposition of .

Authors

Xin Liu, LSEC, Chinese Academy of Sciences
Yin Zhang, CAAM, Rice University (work supported in part by NSF DMS-1115950)
Zaiwen Wen, Department of Mathematics, Shanghai Jiaotong University

Technical Reports

Xin Liu, Zaiwen Wen and Yin Zhang, Limited Memory Block Krylov Subspace Optimization for Computing Dominant Singular Value Decompositions, submitted. Rice CAAM Tech Report. (pdf)

Download and install

Download

LMSVD is distributed under the terms of the GNU General Public License.

Version 1.0 (Download)

Installation

Unzip the distribution. This will create a directory called LMSVD. We'll refer to this directory as <lmsvd-root>.
Start Matlab and add <lmsvd-root> to your path:

>> addpath <lmsvd-root>

To verify the LMSVD installation, execute the following command within Matlab:

>> test_lmsvd