search

aimacode / aima-pseudocode

Pseudocode descriptions of the algorithms from Russell And Norvig's "Artificial Intelligence - A Modern Approach"
Other
866 stars 420 forks source link

4th Edition Algorithm: Singular Value Decomposition #43

Open norvig opened 7 years ago

norvig commented 7 years ago

We will implement SVD, see for example http://stats.stackexchange.com/questions/159325/what-fast-algorithms-exist-for-computing-truncated-svd

kanishk1225 commented 7 years ago

Is this implemented in java?

norvig commented 7 years ago

we would want implementations in java and python, and perhaps a demo in javascript

sofmonk commented 7 years ago

Sir, so we first start work on writing the pseudocode?

Chipe1 commented 7 years ago

@norvig Are we supposed to follow the method given by amoeba (top answer on the stackexchange question)? I tried doing A = [0 B;B' 0] but instead of converging I encounter a loop. I couldn't find a proof for equivalence of truncated SVD of B and eigen decomposition of [0 B;B' 0]. I was able to prove it for [B 0; 0 B'] instead. Also, are we finding only the biggest eigen value? If not, do I generate a new X using Gram–Schmidt? I'm not sure how/where we are going to use SVD. My guess is dimensionality reduction, so we could need more eigenvalues/vectors. Is this a step in the right direction?

My bad. Just had to normalize the parts individually instead of the whole vector X.

Shashi456 commented 7 years ago

Can i work on this issue ?

Chipe1 commented 7 years ago

@Shashi456 I've already implemented it in python. You can improve it, write a pseudocode, or implement it in another language.

Shashi456 commented 7 years ago

Could i take a look at the code for writing the pseudocode then ?

Chipe1 commented 7 years ago

Link to code The code is not very clear and does some things to prevent precision problems. The pseudocode won't require doing that.

Shashi456 commented 7 years ago

Thanks @Chipe1 I'll take a look at it , have you applied just some algorithm generically or did you take a look at existing algo's and converted them into code?