{"action":"created","comment":{"url":"https://api.github.com/repos/scicubator/scikit-learn/pulls/comments/29556538","id":29556538,"diff_hunk":"@@ -0,0 +1,172 @@\n+\"\"\" Sparse Nonnegative matrix factorization\n+\"\"\"\n+# Author: Vamsi Krishna Potluru\n+# License: BSD 3 clause\n+\n+from __future__ import division\n+import numpy as np\n+import scipy.io\n+\n+\n+def sparse_nmf(X, r, maxiter, spar, W=None, H=None):\n+    \"\"\"Learns a sparse NMF model given data X.\n+\n+    Parameters\n+    ----------\n+\n+    X : {array}, shape = [n_features, n_samples]\n+    r : rank of factorization\n+    maxiter : number of updates of the factor matrices\n+    spar : sparsity of the features given by measure\n+           sp(x) = (sqrt(n)-|x|_1/|x|_2 )/(sqrt(n)-1)\n+\n+    Returns\n+    -------\n+\n+    W : {array}\n+        Feature matrix to the sparse NMF problem.\n+\n+    Reference\n+    ---------\n+\n+    Block Coordinate Descent for Sparse NMF\n+    Vamsi K. Potluru, Sergey M. Plis, Jonathan Le Roux,\n+    Barak A. Pearlmutter, Vince D. Calhoun, Thomas P. Hayes\n+    ICLR 2013.\n+    http://arxiv.org/abs/1301.3527\n+    \"\"\"\n+    m, n = np.shape(X)\n+    if not W and not H:\n+        W, H = init_nmf(X, r, spar)\n+    Obj = np.zeros(maxiter)\n+    for i in range(maxiter):\n+        Obj[i] = np.linalg.norm(X - np.dot(W, H), 'fro')\n+        print 'iter:', i + 1, 'Obj: ', Obj[i]\n+        W = update_W(X, W, H, spar)\n+        H = update_H(X, W, H)\n+\n+    return W\n+\n+\n+def init_nmf(X, r, spar):\n+    \"\"\" Initialize the matrix factors for NMF.\n+\n+    Parameters\n+    ----------\n+\n+    X: {array}, shape = [n_features, n_samples]\n+    r: rank of factorization\n+\n+    Returns\n+    -------\n+\n+    W : {array}\n+        Feature matrix of the factorization\n+    H : {array}\n+        Weight matrix of the factorization\n+\n+    where X ~ WH\n+    \"\"\"\n+    m, n = np.shape(X)\n+    W = np.zeros((m, r))\n+    k = np.sqrt(m) - spar * (np.sqrt(m) - 1)\n+    for i in range(r):\n+        W[:, i] = sparse_opt(np.sort(np.random.rand(m))[::-1], k)\n+\n+    W = np.random.rand(m, r)\n+    H = np.random.rand(r, n)\n+    return (W, H)\n+\n+\n+def update_W(X, W, H, spar):\n+    \"\"\"Update the feature matrix based on user-defined sparsity\"\"\"\n+    m, n = np.shape(X)\n+    m, r = np.shape(W)\n+    cach = np.zeros((m, r))\n+    HHt = np.dot(H, H.T)\n+    cach = -np.dot(X, H.T) + np.dot(W, np.dot(H, H.T))\n+    for i in range(r):\n+        W, cach = W_sparse_ith(W, HHt, cach, spar, i)\n+\n+    return W\n+\n+\n+def update_H(X, W, H):\n+    \"\"\"Update the weight matrix using the regular multiplicative updates\"\"\"\n+    m, n = np.shape(X)\n+    WtX = np.dot(W.T, X)\n+    WtW = np.dot(W.T, W)\n+    for j in range(10):\n+        H = H * WtX / (np.dot(WtW, H) + np.spacing(1))\n+\n+    return H\n+\n+\n+def W_sparse_ith(W, HHt, cach, spar, i):\n+    \"\"\" Update the columns sequentially\"\"\"\n+    m, r = np.shape(W)\n+    C = cach[:, i] - W[:, i] * HHt[i, i]\n+    V = np.zeros(m)\n+    k = np.sqrt(m) - spar * (np.sqrt(m) - 1)\n+    a = sparse_opt(np.sort(-C)[::-1], k)\n+    ind = np.argsort(-C)[::-1]\n+    V[ind] = a\n+    cach = cach + np.outer(V - W[:, i], HHt[i, :])\n+    W[:, i] = V\n+    return (W, cach)\n+\n+\n+def sparse_opt(b, k):\n+    \"\"\" Project a vector onto a sparsity constraint\n+\n+    Solves the projection problem by taking into account the\n+    symmetry of l1 and l2 constraints.\n+\n+    Parameters\n+    ---------\n+    b : sorted vector in decreasing value\n+    k : Ratio of l1/l2 norms of a vector\n+\n+    Returns\n+    -------\n+    z : closest vector satisfying the required sparsity constraint.\n+\n+    \"\"\"\n+    n = len(b)\n+    sumb = np.cumsum(b)\n+    normb = np.cumsum(b * b)\n+    pnormb = np.arange(1, n + 1) * normb\n+    y = (pnormb - sumb * sumb) / (np.arange(1, n + 1) - k * k)\n+    bot = np.ceil(k * k)\n+    z = np.zeros(n)\n+    if bot > n:\n+        print 'Looks like the sparsity measure is not between 0 and 1\\n'\n+        return\n+    obj = (-np.sqrt(y) * (np.arange(1, n + 1) + k) + sumb) / \\\n+        np.arange(1, n + 1)\n+    indx = np.argmax(obj[bot:n])\n+    p = indx + bot - 1\n+    p = min(p, n - 1)\n+    p = max(p, bot)\n+    lam = np.sqrt(y[p])\n+    mue = -sumb[p] / (p + 1) + k / (p + 1) * lam\n+    z[:p + 1] = (b[:p + 1] + mue) / lam\n+    return z\n+\n+\n+if __name__ == '__main__':\n+    r = 25\n+    spar = 0.5\n+    maxiter = 200\n+    X = scipy.io.loadmat('../data/orlfaces.mat')\n+    W = sparse_nmf(X['V'], r, maxiter, spar)","path":"nmf/sparse_nmf.py","position":162,"original_position":162,"commit_id":"13e901239576411123e14368f42cb7bceca08d0d","original_commit_id":"13e901239576411123e14368f42cb7bceca08d0d","user":{"login":"ismav","id":5237913,"avatar_url":"https://avatars.githubusercontent.com/u/5237913?v=3","gravatar_id":"","url":"https://api.github.com/users/ismav","html_url":"https://github.com/ismav","followers_url":"https://api.github.com/users/ismav/followers","following_url":"https://api.github.com/users/ismav/following{/other_user}","gists_url":"https://api.github.com/users/ismav/gists{/gist_id}","starred_url":"https://api.github.com/users/ismav/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ismav/subscriptions","organizations_url":"https://api.github.com/users/ismav/orgs","repos_url":"https://api.github.com/users/ismav/repos","events_url":"https://api.github.com/users/ismav/events{/privacy}","received_events_url":"https://api.github.com/users/ismav/received_events","type":"User","site_admin":false},"body":"Ah I see.\nYes, I have been reading about test driven development in Python and it is\nstarting to make sense.\n\nBtw, I am not sure if we want to make it necessarily part of scikit-learn.\nWe should discuss that.\nThere are couple of important high-level questions which we should hammer\nout.\n\n\nOn Sun, May 3, 2015 at 10:24 AM, Yaroslav Halchenko <\nnotifications@github.com> wrote:\n\n> In nmf/sparse_nmf.py\n> <https://github.com/scicubator/scikit-learn/pull/2#discussion_r29556519>:\n>\n> > +    indx = np.argmax(obj[bot:n])\n> > +    p = indx + bot - 1\n> > +    p = min(p, n - 1)\n> > +    p = max(p, bot)\n> > +    lam = np.sqrt(y[p])\n> > +    mue = -sumb[p] / (p + 1) + k / (p + 1) * lam\n> > +    z[:p + 1] = (b[:p + 1] + mue) / lam\n> > +    return z\n> > +\n> > +\n> > +if __name__ == '__main__':\n> > +    r = 25\n> > +    spar = 0.5\n> > +    maxiter = 200\n> > +    X = scipy.io.loadmat('../data/orlfaces.mat')\n> > +    W = sparse_nmf(X['V'], r, maxiter, spar)\n>\n> and that is the point of \"unit-tests\": to verify/guarantee that things\n> work as they should. Next step would be to create\n> sklearn/nmf/tests/test_sparse_nmf.py and write some basic tests: that\n> functions work as they should and produce correct or at least sensible\n> results.\n>\n> —\n> Reply to this email directly or view it on GitHub\n> <https://github.com/scicubator/scikit-learn/pull/2/files#r29556519>.\n>\n","created_at":"2015-05-03T14:26:26Z","updated_at":"2015-05-03T14:26:26Z","html_url":"https://github.com/scicubator/scikit-learn/pull/2#discussion_r29556538","pull_request_url":"https://api.github.com/repos/scicubator/scikit-learn/pulls/2","_links":{"self":{"href":"https://api.github.com/repos/scicubator/scikit-learn/pulls/comments/29556538"},"html":{"href":"https://github.com/scicubator/scikit-learn/pull/2#discussion_r29556538"},"pull_request":{"href":"https://api.github.com/repos/scicubator/scikit-learn/pulls/2"}}},"pull_request":{"url":"https://api.github.com/repos/scicubator/scikit-learn/pulls/2","id":30704048,"html_url":"https://github.com/scicubator/scikit-learn/pull/2","diff_url":"https://github.com/scicubator/scikit-learn/pull/2.diff","patch_url":"https://github.com/scicubator/scikit-learn/pull/2.patch","issue_url":"https://api.github.com/repos/scicubator/scikit-learn/issues/2","number":2,"state":"open","locked":false,"title":"First NMF function","user":{"login":"ismav","id":5237913,"avatar_url":"https://avatars.githubusercontent.com/u/5237913?v=3","gravatar_id":"","url":"https://api.github.com/users/ismav","html_url":"https://github.com/ismav","followers_url":"https://api.github.com/users/ismav/followers","following_url":"https://api.github.com/users/ismav/following{/other_user}","gists_url":"https://api.github.com/users/ismav/gists{/gist_id}","starred_url":"https://api.github.com/users/ismav/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ismav/subscriptions","organizations_url":"https://api.github.com/users/ismav/orgs","repos_url":"https://api.github.com/users/ismav/repos","events_url":"https://api.github.com/users/ismav/events{/privacy}","received_events_url":"https://api.github.com/users/ismav/received_events","type":"User","site_admin":false},"body":"This should hopefully be the right pull request!","created_at":"2015-03-07T15:16:26Z","updated_at":"2015-05-03T14:26:26Z","closed_at":null,"merged_at":null,"merge_commit_sha":"6d6e8f428b30f64225a972aece04226f997a8a54","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/scicubator/scikit-learn/pulls/2/commits","review_comments_url":"https://api.github.com/repos/scicubator/scikit-learn/pulls/2/comments","review_comment_url":"https://api.github.com/repos/scicubator/scikit-learn/pulls/comments{/number}","comments_url":"https://api.github.com/repos/scicubator/scikit-learn/issues/2/comments","statuses_url":"https://api.github.com/repos/scicubator/scikit-learn/statuses/13e901239576411123e14368f42cb7bceca08d0d","head":{"label":"ismav:NMF","ref":"NMF","sha":"13e901239576411123e14368f42cb7bceca08d0d","user":{"login":"ismav","id":5237913,"avatar_url":"https://avatars.githubusercontent.com/u/5237913?v=3","gravatar_id":"","url":"https://api.github.com/users/ismav","html_url":"https://github.com/ismav","followers_url":"https://api.github.com/users/ismav/followers","following_url":"https://api.github.com/users/ismav/following{/other_user}","gists_url":"https://api.github.com/users/ismav/gists{/gist_id}","starred_url":"https://api.github.com/users/ismav/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ismav/subscriptions","organizations_url":"https://api.github.com/users/ismav/orgs","repos_url":"https://api.github.com/users/ismav/repos","events_url":"https://api.github.com/users/ismav/events{/privacy}","received_events_url":"https://api.github.com/users/ismav/received_events","type":"User","site_admin":false},"repo":{"id":31763699,"name":"scikit-learn","full_name":"ismav/scikit-learn","owner":{"login":"ismav","id":5237913,"avatar_url":"https://avatars.githubusercontent.com/u/5237913?v=3","gravatar_id":"","url":"https://api.github.com/users/ismav","html_url":"https://github.com/ismav","followers_url":"https://api.github.com/users/ismav/followers","following_url":"https://api.github.com/users/ismav/following{/other_user}","gists_url":"https://api.github.com/users/ismav/gists{/gist_id}","starred_url":"https://api.github.com/users/ismav/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ismav/subscriptions","organizations_url":"https://api.github.com/users/ismav/orgs","repos_url":"https://api.github.com/users/ismav/repos","events_url":"https://api.github.com/users/ismav/events{/privacy}","received_events_url":"https://api.github.com/users/ismav/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/ismav/scikit-learn","description":"scikit-learn: machine learning in Python","fork":true,"url":"https://api.github.com/repos/ismav/scikit-learn","forks_url":"https://api.github.com/repos/ismav/scikit-learn/forks","keys_url":"https://api.github.com/repos/ismav/scikit-learn/keys{/key_id}","collaborators_url":"https://api.github.com/repos/ismav/scikit-learn/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/ismav/scikit-learn/teams","hooks_url":"https://api.github.com/repos/ismav/scikit-learn/hooks","issue_events_url":"https://api.github.com/repos/ismav/scikit-learn/issues/events{/number}","events_url":"https://api.github.com/repos/ismav/scikit-learn/events","assignees_url":"https://api.github.com/repos/ismav/scikit-learn/assignees{/user}","branches_url":"https://api.github.com/repos/ismav/scikit-learn/branches{/branch}","tags_url":"https://api.github.com/repos/ismav/scikit-learn/tags","blobs_url":"https://api.github.com/repos/ismav/scikit-learn/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/ismav/scikit-learn/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/ismav/scikit-learn/git/refs{/sha}","trees_url":"https://api.github.com/repos/ismav/scikit-learn/git/trees{/sha}","statuses_url":"https://api.github.com/repos/ismav/scikit-learn/statuses/{sha}","languages_url":"https://api.github.com/repos/ismav/scikit-learn/languages","stargazers_url":"https://api.github.com/repos/ismav/scikit-learn/stargazers","contributors_url":"https://api.github.com/repos/ismav/scikit-learn/contributors","subscribers_url":"https://api.github.com/repos/ismav/scikit-learn/subscribers","subscription_url":"https://api.github.com/repos/ismav/scikit-learn/subscription","commits_url":"https://api.github.com/repos/ismav/scikit-learn/commits{/sha}","git_commits_url":"https://api.github.com/repos/ismav/scikit-learn/git/commits{/sha}","comments_url":"https://api.github.com/repos/ismav/scikit-learn/comments{/number}","issue_comment_url":"https://api.github.com/repos/ismav/scikit-learn/issues/comments{/number}","contents_url":"https://api.github.com/repos/ismav/scikit-learn/contents/{+path}","compare_url":"https://api.github.com/repos/ismav/scikit-learn/compare/{base}...{head}","merges_url":"https://api.github.com/repos/ismav/scikit-learn/merges","archive_url":"https://api.github.com/repos/ismav/scikit-learn/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/ismav/scikit-learn/downloads","issues_url":"https://api.github.com/repos/ismav/scikit-learn/issues{/number}","pulls_url":"https://api.github.com/repos/ismav/scikit-learn/pulls{/number}","milestones_url":"https://api.github.com/repos/ismav/scikit-learn/milestones{/number}","notifications_url":"https://api.github.com/repos/ismav/scikit-learn/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/ismav/scikit-learn/labels{/name}","releases_url":"https://api.github.com/repos/ismav/scikit-learn/releases{/id}","created_at":"2015-03-06T10:06:38Z","updated_at":"2015-03-06T10:06:44Z","pushed_at":"2015-03-06T10:00:02Z","git_url":"git://github.com/ismav/scikit-learn.git","ssh_url":"git@github.com:ismav/scikit-learn.git","clone_url":"https://github.com/ismav/scikit-learn.git","svn_url":"https://github.com/ismav/scikit-learn","homepage":"http://scikit-learn.org","size":55559,"stargazers_count":0,"watchers_count":0,"language":"C","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"scicubator:NMF","ref":"NMF","sha":"c1a429e46db05954f92ab74f62716579bd357cb4","user":{"login":"scicubator","id":9728993,"avatar_url":"https://avatars.githubusercontent.com/u/9728993?v=3","gravatar_id":"","url":"https://api.github.com/users/scicubator","html_url":"https://github.com/scicubator","followers_url":"https://api.github.com/users/scicubator/followers","following_url":"https://api.github.com/users/scicubator/following{/other_user}","gists_url":"https://api.github.com/users/scicubator/gists{/gist_id}","starred_url":"https://api.github.com/users/scicubator/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/scicubator/subscriptions","organizations_url":"https://api.github.com/users/scicubator/orgs","repos_url":"https://api.github.com/users/scicubator/repos","events_url":"https://api.github.com/users/scicubator/events{/privacy}","received_events_url":"https://api.github.com/users/scicubator/received_events","type":"Organization","site_admin":false},"repo":{"id":26609407,"name":"scikit-learn","full_name":"scicubator/scikit-learn","owner":{"login":"scicubator","id":9728993,"avatar_url":"https://avatars.githubusercontent.com/u/9728993?v=3","gravatar_id":"","url":"https://api.github.com/users/scicubator","html_url":"https://github.com/scicubator","followers_url":"https://api.github.com/users/scicubator/followers","following_url":"https://api.github.com/users/scicubator/following{/other_user}","gists_url":"https://api.github.com/users/scicubator/gists{/gist_id}","starred_url":"https://api.github.com/users/scicubator/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/scicubator/subscriptions","organizations_url":"https://api.github.com/users/scicubator/orgs","repos_url":"https://api.github.com/users/scicubator/repos","events_url":"https://api.github.com/users/scicubator/events{/privacy}","received_events_url":"https://api.github.com/users/scicubator/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/scicubator/scikit-learn","description":"scikit-learn: machine learning in Python","fork":true,"url":"https://api.github.com/repos/scicubator/scikit-learn","forks_url":"https://api.github.com/repos/scicubator/scikit-learn/forks","keys_url":"https://api.github.com/repos/scicubator/scikit-learn/keys{/key_id}","collaborators_url":"https://api.github.com/repos/scicubator/scikit-learn/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/scicubator/scikit-learn/teams","hooks_url":"https://api.github.com/repos/scicubator/scikit-learn/hooks","issue_events_url":"https://api.github.com/repos/scicubator/scikit-learn/issues/events{/number}","events_url":"https://api.github.com/repos/scicubator/scikit-learn/events","assignees_url":"https://api.github.com/repos/scicubator/scikit-learn/assignees{/user}","branches_url":"https://api.github.com/repos/scicubator/scikit-learn/branches{/branch}","tags_url":"https://api.github.com/repos/scicubator/scikit-learn/tags","blobs_url":"https://api.github.com/repos/scicubator/scikit-learn/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/scicubator/scikit-learn/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/scicubator/scikit-learn/git/refs{/sha}","trees_url":"https://api.github.com/repos/scicubator/scikit-learn/git/trees{/sha}","statuses_url":"https://api.github.com/repos/scicubator/scikit-learn/statuses/{sha}","languages_url":"https://api.github.com/repos/scicubator/scikit-learn/languages","stargazers_url":"https://api.github.com/repos/scicubator/scikit-learn/stargazers","contributors_url":"https://api.github.com/repos/scicubator/scikit-learn/contributors","subscribers_url":"https://api.github.com/repos/scicubator/scikit-learn/subscribers","subscription_url":"https://api.github.com/repos/scicubator/scikit-learn/subscription","commits_url":"https://api.github.com/repos/scicubator/scikit-learn/commits{/sha}","git_commits_url":"https://api.github.com/repos/scicubator/scikit-learn/git/commits{/sha}","comments_url":"https://api.github.com/repos/scicubator/scikit-learn/comments{/number}","issue_comment_url":"https://api.github.com/repos/scicubator/scikit-learn/issues/comments{/number}","contents_url":"https://api.github.com/repos/scicubator/scikit-learn/contents/{+path}","compare_url":"https://api.github.com/repos/scicubator/scikit-learn/compare/{base}...{head}","merges_url":"https://api.github.com/repos/scicubator/scikit-learn/merges","archive_url":"https://api.github.com/repos/scicubator/scikit-learn/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/scicubator/scikit-learn/downloads","issues_url":"https://api.github.com/repos/scicubator/scikit-learn/issues{/number}","pulls_url":"https://api.github.com/repos/scicubator/scikit-learn/pulls{/number}","milestones_url":"https://api.github.com/repos/scicubator/scikit-learn/milestones{/number}","notifications_url":"https://api.github.com/repos/scicubator/scikit-learn/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/scicubator/scikit-learn/labels{/name}","releases_url":"https://api.github.com/repos/scicubator/scikit-learn/releases{/id}","created_at":"2014-11-13T21:41:52Z","updated_at":"2014-11-13T21:41:58Z","pushed_at":"2015-03-07T14:35:31Z","git_url":"git://github.com/scicubator/scikit-learn.git","ssh_url":"git@github.com:scicubator/scikit-learn.git","clone_url":"https://github.com/scicubator/scikit-learn.git","svn_url":"https://github.com/scicubator/scikit-learn","homepage":"http://scikit-learn.org","size":55753,"stargazers_count":0,"watchers_count":0,"language":"C","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1,"mirror_url":null,"open_issues_count":1,"forks":1,"open_issues":1,"watchers":0,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/scicubator/scikit-learn/pulls/2"},"html":{"href":"https://github.com/scicubator/scikit-learn/pull/2"},"issue":{"href":"https://api.github.com/repos/scicubator/scikit-learn/issues/2"},"comments":{"href":"https://api.github.com/repos/scicubator/scikit-learn/issues/2/comments"},"review_comments":{"href":"https://api.github.com/repos/scicubator/scikit-learn/pulls/2/comments"},"review_comment":{"href":"https://api.github.com/repos/scicubator/scikit-learn/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/scicubator/scikit-learn/pulls/2/commits"},"statuses":{"href":"https://api.github.com/repos/scicubator/scikit-learn/statuses/13e901239576411123e14368f42cb7bceca08d0d"}}}}