Git Product home page Git Product logo

redsvd's Introduction

redsvd - RandomizED Singular Value Decomposition

redsvd is a library for solving several matrix decompositions including singular value decomposition (SVD), principal component analysis (PCA), and eigen value decomposition. redsvd can handle very large matrix efficiently, and optimized for a truncated SVD of sparse matrices. For example, redsvd can compute a truncated SVD with top 20 singular values for a 100K x 100K matrix with 1M nonzero entries in less than one second.

The algorithm is based on the randomized algorithm for computing large-scale SVD. Although it uses randomized matrices, the results is very accurate with very high probability. See the experiment part for the detail.

redsvd's People

Contributors

andrewssobral avatar

Stargazers

 avatar  avatar  avatar

Watchers

 avatar  avatar

redsvd's Issues

U and V have last column all zeros

What steps will reproduce the problem?
1.
>cat densa.txt
 1.5  0.0  2.5  2.5
 0.0  2.5  2.5  0.0
 1.5  0.0  2.5  1.0
 0.0  2.5  2.5  0.0
 0.0  2.5  2.5  0.0
2.
redsvd -i densa.txt -o densa -f dense -r 10
3.
>cat densa.U
-0.401793 +0.706597 -0.582481 +0.000000 
-0.486488 -0.308495 -0.038651 +0.000000 
-0.358540 +0.463912 +0.810083 +0.000000 
-0.486488 -0.308495 -0.038651 +0.000000 
-0.486488 -0.308495 -0.038651 +0.000000 
>cat densa.V
-0.165886 +0.472878 +0.409235 +0.000000 
-0.530701 -0.623149 -0.347478 +0.000000 
-0.807177 +0.164981 +0.334580 +0.000000 
-0.198253 +0.600711 -0.774494 +0.000000 


What is the expected output? What do you see instead?
First, I expected U to be 5 by 5. 
Tried same matrix in gnu octave, and the first 3 column match exactly, but the 
last one have values not zero:
octave-3.2.4:1> A=[1.5 0 2.5 2.5;0 2.5 2.5 0; 1.5 0 2.5 1.0; 0 2.5 2.5 0;0 2.5 
2.5 0]
A =

   1.50000   0.00000   2.50000   2.50000
   0.00000   2.50000   2.50000   0.00000
   1.50000   0.00000   2.50000   1.00000
   0.00000   2.50000   2.50000   0.00000
   0.00000   2.50000   2.50000   0.00000

octave-3.2.4:2> [u,s,v]=svd(A);
octave-3.2.4:3> u
u =

  -4.0179e-01   7.0660e-01   5.8248e-01   1.9052e-16  -3.8365e-20
  -4.8649e-01  -3.0849e-01   3.8651e-02   8.1650e-01  -1.2869e-16
  -3.5854e-01   4.6391e-01  -8.1008e-01  -3.1762e-17   3.8365e-20
  -4.8649e-01  -3.0849e-01   3.8651e-02  -4.0825e-01  -7.0711e-01
  -4.8649e-01  -3.0849e-01   3.8651e-02  -4.0825e-01   7.0711e-01

octave-3.2.4:4> v
v =

  -1.6589e-01   4.7288e-01  -4.0924e-01   7.6249e-01
  -5.3070e-01  -6.2315e-01   3.4748e-01   4.5750e-01
  -8.0718e-01   1.6498e-01  -3.3458e-01  -4.5750e-01
  -1.9825e-01   6.0071e-01   7.7449e-01   1.1102e-16

What version of the product are you using? On what operating system?
Ubuntu 12.04
redsvd 0.2.0


Please provide any additional information below.
I don't sure it is an issue, I didn't find any other information to let me know 
if this behavior is expected.

Original issue reported on code.google.com by [email protected] on 27 Sep 2012 at 4:27

Wrong eigen values and vectors of a sparse symmetric matrix

What steps will reproduce the problem?
1. ./RedSVD.exe -i ip.mat -o op -r 2 -m SymEigen -f sparse

2. cat ip.mat
0:1 3:0.5
1:1
2:1
0:0.5 3:1


What is the expected output? What do you see instead?
Expected: since the matrix is sparse and there are rows with just 1 non-zero 
value, I expect to see either eigen value of 1 or eigen vector with value at 
index 1 and index 2 to be 0 (if counting indices from 0). Something like
x_0
0
0
x_3

I see this:
cat op.evec
+0.463004 -0.795740
-0.735242 -0.368169
+0.411030 -0.080414
-0.275864 -0.474113

cat op.eval
+0.872274
+1.377271

What version of the product are you using? On what operating system?
I am compiling the code in visual studio 2013. The versions are:
1. redsvd 0.2.0
2. Eigen 3

Please provide any additional information below.
If I provide identity matrix, I get the correct eigen values and vectors. 
Adding 2 elements at some {i,j} and {j,i} location does not yield the correct 
eigen vectors. 

Am I missing something here ? Your help would be much appreciated. Thank you. 

Original issue reported on code.google.com by [email protected] on 27 Feb 2014 at 10:37

計算メソッドにPCAを指定した場合、結果出力時eigen3のassertionに引っかかって落ちる

What steps will reproduce the problem?
$ cat file1
 1.0  2.0  3.0  4.0  5.0
-2.0 -1.0  0.0  1.0  2.0
 1.0 -2.0  3.0 -5.0  7.0
$ redsvd -i file1 -o file1 -r 2 -f dense -m PCA && cat file1.*
compute PCA
read matrix from file1 ... -6.89179e-08 sec.
rows:   3
cols:   5
rank:   2
compute ... 3.49246e-09 sec.
write file1.pc
assertion "other.rows() == 1 || other.cols() == 1" failed: file 
"/usr/local/include/eigen3/Eigen/src/Core/DenseStorageBase.h", line 247, 
function: void Eigen::DenseStorageBase<Derived>::resizeLike(const 
Eigen::EigenBase<OtherDerived>&) [with OtherDerived = Eigen::Matrix<float, 
-0x000000001, -0x000000001, 0, -0x000000001, -0x000000001>, Derived = 
Eigen::Matrix<float, -0x000000001, 1, 0, -0x000000001, 1>]
Aborted (core dumped)


What is the expected output? What do you see instead?
計算結果が出力されてほしい

What version of the product are you using? On what operating system?
- Windows XP
- Cygwin 1.7
- redsvd 0.1.2
- eigen3 beta2

Please provide any additional information below.
writeMatrix(const string& fn, const REDSVD::RedPCA& A) 内のwriteVector_(const 
string& fn, const VectorXf& V)の呼び出しにおいて、MatrixXf 
RedPCA#scores()をVectorXfに変換しようとするところで落ちている
ようです。

Original issue reported on code.google.com by [email protected] on 16 Nov 2010 at 4:19

計算メソッドにSymEigenを指定した場合、eigen3のassertionに引っかかって落ちる

What steps will reproduce the problem?
$ cat file1
 1.0  2.0  3.0  4.0  5.0
-2.0 -1.0  0.0  1.0  2.0
 1.0 -2.0  3.0 -5.0  7.0
$ redsvd -i file1 -o file1 -r 2 -f dense -m SymEigen && cat file1.*
compute SymEigen
read matrix from file1 ... -4.07454e-09 sec.
rows:   3
cols:   5
rank:   2
compute ... assertion "lhs.cols() == rhs.rows() && "invalid matrix product" && 
"if you wanted a coeff-wise or a dot product use the respective explicit 
functions"" failed: file 
"/usr/local/include/eigen3/Eigen/src/Core/ProductBase.h", line 103, function: 
Eigen::ProductBase<Derived, Lhs, Rhs>::ProductBase(const Lhs&, const Rhs&) 
[with Derived = Eigen::GeneralProduct<Eigen::Transpose<Eigen::Matrix<float, 
-0x000000001, -0x000000001, 0, -0x000000001, -0x000000001> >, 
Eigen::Matrix<float, -0x000000001, -0x000000001, 0, -0x000000001, 
-0x000000001>, 5>, Lhs = Eigen::Transpose<Eigen::Matrix<float, -0x000000001, 
-0x000000001, 0, -0x000000001, -0x000000001> >, Rhs = Eigen::Matrix<float, 
-0x000000001, -0x000000001, 0, -0x000000001, -0x000000001>]
Aborted (core dumped)


What is the expected output? What do you see instead?
計算結果が出力されてほしい

What version of the product are you using? On what operating system?
- Windows XP
- Cygwin 1.7
- redsvd 0.1.2
- eigen3 beta2

Please provide any additional information below.


Original issue reported on code.google.com by [email protected] on 16 Nov 2010 at 4:21

rand()が0を返す場合、 sampleTwoGaussian(float&,float&)の結果が-infとなり計算結果がおかしくなる

問題
cygwin/gcc3.4.4 
環境下でビルドしたredsvd0.1.2において、計算結果がnanになる

原因
 sampleTwoGaussian(float&,float&): redsvd.cppにおいて、

  float v1 = (float)(rand()) / ((float)RAND_MAX+1);
  float v2 = (float)(rand()) / ((float)RAND_MAX+1);
  float len = sqrt(-2.f * log(v1));

というコードがある。rand()の値域は0を含むが、v1に0が設定�
��れた場合lenがinfとなり以降の値がおかしくなる。

当該環境においては、srand()されていない場合、rand()を一回�
��に呼んだ時の初期値がかならず0となるため、常時計算結��
�がおかしくなることになる。

解決方法
rand()が0を返す場合を考慮する。
知識不足でパッチは書けませんでした。



以上よろしくお願いします。

Original issue reported on code.google.com by [email protected] on 15 Nov 2010 at 6:48

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.