File Exchange

image thumbnail

lmsvd.m

version 1.3.0.0 (5.93 KB) by XIN LIU
LMSVD ver. 1.3 is available for computing truncated SVD

9 Downloads

Updated 14 Dec 2017

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 (29)

Ke Ma

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

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

wang xi

good

wang xi

good!

Xiao

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

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

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

Yin 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

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

Updates

1.3.0.0

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

1.3.0.0

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

1.2.0.0

Modify description.

1.1.0.0

Add a typical demo.

MATLAB Release Compatibility
Created with R2012b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Discover Live Editor

Create scripts with code, output, and formatted text in a single executable document.


Learn About Live Editor