3 ms·
PCA is basically just SVD and computing an SVD of that size is not unreasonable, even of it's dense: 0.5e6^2 = 0.25e12 = 1TB of 32-bit floats. That's a lot of m
by StefanKarpinski 12y ago
PCA is basically just SVD and computing an SVD of that size is not unreasonable, even of it's dense: 0.5e6^2 = 0.25e12 = 1TB of 32-bit floats. That's a lot of memory but there are reasonably priced machines ($50k or so) with that much RAM these days. If it's sparse, this can be done on a laptop, and it might not even be necessarily to materialize the matrix at all if you use Lancosz iteration.
- srean 12y agoLets put it this way then, we disagree on what's a reasonable expenditure. 1TB Ram ? $50k ? Could you fund me please :) ok adding pretty please. Note its not just memory, its computation also. Every entry of that matrix is a solution to a dynamic program, if you dont store it you have to recompute it. The DP scales as product of the lengths of the string, those things have a fat tail. You could still get away with it if this matrix was close to a low rank matrix and with large gaps between adjacent singular values. Its not and thats a problem. Note you have to store the SVD factors too. EDIT: Interesting ! my comments seems to have annoyed someone. Did not expect downvotes on my comments here, thought they were pretty uncontroversial. If you dear reader can leave some clues it would be helpful and appreciated. I upvote those who explain what they found unpalatable about my comments, regardless of agreement.
- StefanKarpinski 12y agoIt's a lot of computation, granted, but I just wanted to point out that it wasn't completely ludicrous. The proposed algorithm doesn't work anyway since there are no non-degenerate hash functions that map all words within D edits of each other to the same hash value (as I pointed out here: https://news.ycombinator.com/item?id=8158942 https://news.ycombinator.com/item?id=8158942).