Thy friend is my friend: Iterative collaborative filtering for sparse matrix estimation
© 2017 Neural information processing systems foundation. All rights reserved. The sparse matrix estimation problem consists of estimating the distribution of an n x n matrix Y, from a sparsely observed single instance of this matrix where the entries of Y are independent random variables. This captu...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137935 |
| _version_ | 1826192163468214272 |
|---|---|
| author | Shah, Devavrat Lee, Christina E. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shah, Devavrat Lee, Christina E. |
| author_sort | Shah, Devavrat |
| collection | MIT |
| description | © 2017 Neural information processing systems foundation. All rights reserved. The sparse matrix estimation problem consists of estimating the distribution of an n x n matrix Y, from a sparsely observed single instance of this matrix where the entries of Y are independent random variables. This captures a wide array of problems; special instances include matrix completion in the context of recommendation systems, graphon estimation, and community detection in (mixed membership) stochastic block models. Inspired by classical collaborative filtering for recommendation systems, we propose a novel iterative, collaborative filteringstyle algorithm for matrix estimation in this generic setting. We show that the mean squared error (MSE) of our estimator converges to 0 at the rate of O(d2 (pn)-2/5) as long as ω(d5n) random entries from a total of n2 entries of Y are observed (uniformly sampled), E[Y] has rank d, and the entries of Y have bounded support. The maximum squared error across all entries converges to 0 with high probability as long as we observe a little more, Ω(d5nln (n)) entries. Our results are the best known sample complexity results in this generality. |
| first_indexed | 2024-09-23T09:07:12Z |
| format | Article |
| id | mit-1721.1/137935 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:07:12Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1379352023-02-08T21:08:41Z Thy friend is my friend: Iterative collaborative filtering for sparse matrix estimation Shah, Devavrat Lee, Christina E. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Institute for Data, Systems, and Society Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Statistics and Data Science Center (Massachusetts Institute of Technology) © 2017 Neural information processing systems foundation. All rights reserved. The sparse matrix estimation problem consists of estimating the distribution of an n x n matrix Y, from a sparsely observed single instance of this matrix where the entries of Y are independent random variables. This captures a wide array of problems; special instances include matrix completion in the context of recommendation systems, graphon estimation, and community detection in (mixed membership) stochastic block models. Inspired by classical collaborative filtering for recommendation systems, we propose a novel iterative, collaborative filteringstyle algorithm for matrix estimation in this generic setting. We show that the mean squared error (MSE) of our estimator converges to 0 at the rate of O(d2 (pn)-2/5) as long as ω(d5n) random entries from a total of n2 entries of Y are observed (uniformly sampled), E[Y] has rank d, and the entries of Y have bounded support. The maximum squared error across all entries converges to 0 with high probability as long as we observe a little more, Ω(d5nln (n)) entries. Our results are the best known sample complexity results in this generality. 2021-11-09T15:52:03Z 2021-11-09T15:52:03Z 2017 2019-07-10T16:18:09Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137935 Shah, Devavrat and Lee, Christina E. 2017. "Thy friend is my friend: Iterative collaborative filtering for sparse matrix estimation." en https://papers.nips.cc/paper/7057-thy-friend-is-my-friend-iterative-collaborative-filtering-for-sparse-matrix-estimation Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Neural Information Processing Systems (NIPS) |
| spellingShingle | Shah, Devavrat Lee, Christina E. Thy friend is my friend: Iterative collaborative filtering for sparse matrix estimation |
| title | Thy friend is my friend: Iterative collaborative filtering for sparse matrix estimation |
| title_full | Thy friend is my friend: Iterative collaborative filtering for sparse matrix estimation |
| title_fullStr | Thy friend is my friend: Iterative collaborative filtering for sparse matrix estimation |
| title_full_unstemmed | Thy friend is my friend: Iterative collaborative filtering for sparse matrix estimation |
| title_short | Thy friend is my friend: Iterative collaborative filtering for sparse matrix estimation |
| title_sort | thy friend is my friend iterative collaborative filtering for sparse matrix estimation |
| url | https://hdl.handle.net/1721.1/137935 |
| work_keys_str_mv | AT shahdevavrat thyfriendismyfrienditerativecollaborativefilteringforsparsematrixestimation AT leechristinae thyfriendismyfrienditerativecollaborativefilteringforsparsematrixestimation |