{"action":"created","issue":{"url":"https://api.github.com/repos/facebook/fbpca/issues/1","repository_url":"https://api.github.com/repos/facebook/fbpca","labels_url":"https://api.github.com/repos/facebook/fbpca/issues/1/labels{/name}","comments_url":"https://api.github.com/repos/facebook/fbpca/issues/1/comments","events_url":"https://api.github.com/repos/facebook/fbpca/issues/1/events","html_url":"https://github.com/facebook/fbpca/issues/1","id":154921848,"number":1,"title":"Complexity in Implementation","user":{"login":"shenxiul","id":10038510,"avatar_url":"https://avatars.githubusercontent.com/u/10038510?v=3","gravatar_id":"","url":"https://api.github.com/users/shenxiul","html_url":"https://github.com/shenxiul","followers_url":"https://api.github.com/users/shenxiul/followers","following_url":"https://api.github.com/users/shenxiul/following{/other_user}","gists_url":"https://api.github.com/users/shenxiul/gists{/gist_id}","starred_url":"https://api.github.com/users/shenxiul/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/shenxiul/subscriptions","organizations_url":"https://api.github.com/users/shenxiul/orgs","repos_url":"https://api.github.com/users/shenxiul/repos","events_url":"https://api.github.com/users/shenxiul/events{/privacy}","received_events_url":"https://api.github.com/users/shenxiul/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":11,"created_at":"2016-05-15T18:14:44Z","updated_at":"2016-05-15T20:06:58Z","closed_at":null,"body":"Hi @ajtulloch \r\n\r\nThanks for your nice work! I have a question about complexity in your implementation.\r\n\r\nIn your implementation computing pca, you use\r\n```python\r\nQ = mult(A, np.random.uniform(low=-1.0, high=1.0, size=(n, l)))\r\n```\r\nin line 1534 in fbpca.py, which leads to the computational complexity of calculating pca as O(mnk) if A is in shape m * n and we are computing first k singular values. However in their paper [arXiv: 0909.4061](http://arxiv.org/abs/0909.4061) and another paper by same authors [Liberty, Edo, et al., PNAS 104.51 (2007): 20167-20172.](http://www.pnas.org/content/104/51/20167.short), they improved their algorithm to O(k^2(m+n) + mn\\log(k)) by bypassing the multiplication directly instead. May I ask if my understanding of your implementation is correct? And should we work on improving it further to see how it works?"},"comment":{"url":"https://api.github.com/repos/facebook/fbpca/issues/comments/219307505","html_url":"https://github.com/facebook/fbpca/issues/1#issuecomment-219307505","issue_url":"https://api.github.com/repos/facebook/fbpca/issues/1","id":219307505,"user":{"login":"tygert","id":10134756,"avatar_url":"https://avatars.githubusercontent.com/u/10134756?v=3","gravatar_id":"","url":"https://api.github.com/users/tygert","html_url":"https://github.com/tygert","followers_url":"https://api.github.com/users/tygert/followers","following_url":"https://api.github.com/users/tygert/following{/other_user}","gists_url":"https://api.github.com/users/tygert/gists{/gist_id}","starred_url":"https://api.github.com/users/tygert/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tygert/subscriptions","organizations_url":"https://api.github.com/users/tygert/orgs","repos_url":"https://api.github.com/users/tygert/repos","events_url":"https://api.github.com/users/tygert/events{/privacy}","received_events_url":"https://api.github.com/users/tygert/received_events","type":"User","site_admin":false},"created_at":"2016-05-15T20:06:58Z","updated_at":"2016-05-15T20:06:58Z","body":"(Incidentally, you might want to continue this conversation via e-mail to mark@tygert.com rather than on GitHub.)"}}