File Exchange

image thumbnail

lmsvd.m

version 1.3 (5.93 KB) by

LMSVD ver. 1.3 is available for computing truncated SVD

20 Downloads

Updated

View License

LMSVD is a Matlab solver for computing truncated (dominant) singular value decompositions of relatively large matrices. The code uses a subspace optimization technique to achieve significant accelerations to the classic simultaneous subspace iterations method, and is typically much faster than the Matlab's default function "svds".
In the case you use LMSVD in your published work, please make a reference to the following paper.
Xin Liu, Zaiwen Wen and Yin Zhang, Limited Memory Block Krylov Subspace Optimization for Computing Dominant Singular Value Decompositions, SIAM Journal on Scientific Computing, 35-3 (2013), A1641-A1668.

Comments and Ratings (28)

Ahmed Fasih

My coworker found the source of the bug low-rank bug (see my post on 11 Dec 2017): instead of `Lm = max(0,round(L/k))*k;` you want `Lm = max(0, ceil(L / k) - 1) * k;` to implement equation (37) in the authors' SIAM JSC 2013 paper. With this fix in place, the function returns the correct SVD for low-rank matrixes. Users of this function are urged to at least test their copies with the following test: `rng(1); x = randn(200, 4) * randn(4, 50); opts = struct('maxit', 150, 'tol', 1e-8); rng(2); [u s v o] = lmsvd(x, 9, opts); assert(norm(u * s * v' - x) < eps() * numel(x))`.

(My other bug report, about the ordering of eigenvalues, reported in the comment from 17 Nov 2017, is less important to fix than this low-rank bug.)

Ahmed Fasih

There's also an actual bug in this package: it returns incorrect left-singular vectors when you ask for more singular vectors than matrix rank. I.e., make a 200 by 50 matrix that is rank-4 and ask for the rank-9 approximation: `x = randn(200, 4) * randn(4, 50); [u, s, v, o] = lmsvd(x, 9, struct('maxit', 150, 'tol', 1e-8))` and confirm that `norm(x - u*s*v')` is much greater than 0. If you have real-world data, where noise will always ensure full column-rank, then you don't have to worry about this bug, but if you have synthetic matrixes, beware.

Ahmed Fasih

Is there a bug in line 270 of lmsvd.m, in the function `lm_lbo()`, in the block of code with the comment, "orthonormalize Px"? Specifically, this code `ev(idx(Icut))`. If you fill in what `Icut` is, the code reads `ev(idx(idx(cut:end)))`, and I don't think you want *two* `idx` nested like that, because that will not give you the largest `cut`-number of eigenvalues. I think what you want is just `ev(Icut)`?

I think this bug is silent because `eig` tends to return a sorted list of eigenvalues (i.e., `ev` is already sorted coming out of `eig`, since the eigensolver tends to find eigenvalues in order). If `ev` is already sorted, then `ev(idx(idx(Icut)))` (current code) will produce the same result as `ev(idx(Icut))`. But I believe if you find a test case where `eig(T)` happens to not return a pre-sorted list of eigenvalues, or if you use an `eig` replacement that more frequently returns unsorted eigenvalues, the bug will manifest.
Hopefully someone more familiar with the code can comment?

Hi, does this svd code run for a complex matrix ?

Qili Liu

thanks authors!

Hong Wang

I used this code to calculate singular values of large scale matrix. It is robust. More important, it is even faster than the svd of matlab built-in function.

mengyi zhao

Excellent!Help me a lot!

Liang Zhao

An excellent SVD solver. It is robust and efficient, especially for large scale problem. Really helps me a lot. Thanks to the author. Recommend!

Bin Gao

Very very robust!!!

This script was of great help to me. Thank you very much!!

Bao Haowen

Perfect!!!

Bao Haowen

Juana Jiang

An excellent file!

keke M

keke M (view profile)

a most excellent Svd solver I've ever used,thanks!

wang xi

good

wang xi

good!

Xiao

Xiao (view profile)

Very efficient !

Bo Jiang

I tested some large sparse instances, the solver performs so fast and efficient! Strongly recommend this solver.

Zaiwen Wen

The code can be even faster if the sparse matrix-dense vector products is efficient, for example using intel MKL:
http://www.bicmr.org/~wenzw/misc.html

Zhenli

Zhenli (view profile)

I have tested on large sparse matrices, this function is at least twice faster than svds and the result is the same. Fantastic work! I will incorporate it into my program. Thanks!

Zi

Zi (view profile)

Zaikun Zhang

An efficient svd solver for large problems. A very good alternative for the matlab svd function if you have large matrices.

Yin Zhang

Zaikun Zhang

An efficient SVD solver for large problems. A very good alternative for the buildin SVD function when the dimension is high.

Tao Cui

friendly, efficient and robust!

Zaiwen Wen

The code can be more efficient using a suitable implementation for sparse matrix-dense vector multiplications, for example, "mkl_dcscmm" in intel MKL:
http://www.bicmr.org/~wenzw/misc.html

Yin Zhang

Can be orders of magnitude faster than Matlab SVDS on large matrices.

XIN LIU

XIN LIU (view profile)

This code is really robust. Very good. Strongly recommend.

Updates

1.3

Two user-reported bugs, which may cause unexpected results in some extreme instances, have been corrected.

1.3

Two user-reported bugs, which may cause unexpected results in some extreme instances, have been corrected.

1.2

Modify description.

1.1

Add a typical demo.

MATLAB Release
MATLAB 8.0 (R2012b)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Win prizes and improve your MATLAB skills

Play today