Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2017
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1712.00710 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909706940841984 |
|---|---|
| author | Borgs, Christian Chayes, Jennifer Shah, Devavrat Yu, Christina Lee |
| author_facet | Borgs, Christian Chayes, Jennifer Shah, Devavrat Yu, Christina Lee |
| contents | We consider sparse matrix estimation where the goal is to estimate an $n\times n$ matrix from noisy observations of a small subset of its entries. We analyze the estimation error of the popularly utilized collaborative filtering algorithm for the sparse regime. Specifically, we propose a novel iterative variant of the algorithm, adapted to handle the setting of sparse observations. We establish that as long as the fraction of entries observed at random scale as $\frac{\log^{1+κ}(n)}{n}$ for any fixed $κ> 0$, the estimation error with respect to the $\max$-norm decays to $0$ as $n\to\infty$ assuming the underlying matrix of interest has constant rank $r$. Our result is robust to model mis-specification in that if the underlying matrix is approximately rank $r$, then the estimation error decays to the approximate error with respect to the $\max$-norm. In the process, we establish algorithm's ability to handle arbitrary bounded noise in the observations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1712_00710 |
| institution | arXiv |
| publishDate | 2017 |
| record_format | arxiv |
| spellingShingle | Iterative Collaborative Filtering for Sparse Matrix Estimation Borgs, Christian Chayes, Jennifer Shah, Devavrat Yu, Christina Lee Statistics Theory We consider sparse matrix estimation where the goal is to estimate an $n\times n$ matrix from noisy observations of a small subset of its entries. We analyze the estimation error of the popularly utilized collaborative filtering algorithm for the sparse regime. Specifically, we propose a novel iterative variant of the algorithm, adapted to handle the setting of sparse observations. We establish that as long as the fraction of entries observed at random scale as $\frac{\log^{1+κ}(n)}{n}$ for any fixed $κ> 0$, the estimation error with respect to the $\max$-norm decays to $0$ as $n\to\infty$ assuming the underlying matrix of interest has constant rank $r$. Our result is robust to model mis-specification in that if the underlying matrix is approximately rank $r$, then the estimation error decays to the approximate error with respect to the $\max$-norm. In the process, we establish algorithm's ability to handle arbitrary bounded noise in the observations. |
| title | Iterative Collaborative Filtering for Sparse Matrix Estimation |
| topic | Statistics Theory |
| url | https://arxiv.org/abs/1712.00710 |