j2kun/svd

Python code implementing the power method for Singular Value Decomposition

SVD

An implementation of the greedy algorithm for SVD, using the power method for the 1-dimensional case.

For the post Singular Value Decomposition Part 2: Theorem, Proof, Algorithm

And the first (motivational) post in the series: Singular Value Decomposition Part 1: Perspectives on Linear Algebra

Setup

Run the following to set up all the requirements needed to run the code in this repository.

$ virtualenv venv
$ source venv/bin/activate
$ pip install -r requirements.txt
$ bash setup.sh   # downloads relevant NLP corpora from nltk

Then run python3 topicmodel.py for the main topic-model routine, svd.py for the core svd algorithm, and demo.py for the numpy examples from the post.

When finished, run $ deactivate to exit the virtual environment.

svd's Issues

Fails on singularity.

If the matrix is not full-ranked (one at least one of the dimensions, the SVD gives wrong results for the eigenvalues and eigenvectors that corresponds to the eigenvalues should be 0.

License

Please kindly add license, Sir. Thank you.

Wrong A matrix?

    if n > m:
        v = svd_1d(matrixFor1D, epsilon=epsilon)  # next singular vector
        u_unnormalized = np.dot(A, v)
        sigma = norm(u_unnormalized)  # next singular value
        u = u_unnormalized / sigma
    else:
        u = svd_1d(matrixFor1D, epsilon=epsilon)  # next singular vector
        v_unnormalized = np.dot(A.T, u)
        sigma = norm(v_unnormalized)  # next singular value
        v = v_unnormalized / 

In the above code you multiply by A or A.T. Shouldn't you be using the updated matrix: matrixFor1D or matrixFor1D.T?

Fails on square matrices

It seems that this method fails on square matrices (all of the time). Is there anything theoretical that I'm missing about this method?

How to compute non-reduced SVD?

Hi!

First of all, thanks a lot for this implementation! 😊 I couldn't find any other better implementation in Python.

Your implementation looks like it's computing reduced SVD. But I'm trying to implement SVD for the case when full_matrices=True as in torch.svd. Is there anyway I can modify your implementation for full SVD calculation?

Looking towards your help.

Regards,
Rahul Bhalley