Simple Atom Selection Strategy for Greedy Matrix Completion
Abstract
In this paper we focus on the greedy matrix completion problem. A simple atom selection strategy is proposed building upon an alternating minimization procedure. Based on this per-iteration strategy, we devise a greedy algorithm OAMC and establish an upper bound of the approximation error. To evaluate different weight refinement methods, several variants of OAMC are designed. We prove that OAMC and three of its variants have the property of linear convergence. Experiments of Recommendation and Image Recovery are conducted to make empirical evaluation. Results are promising. We report that our algorithm takes only 700 seconds to process Yahoo Music dataset in PC, yet achieves a root mean square error 24.5 on test set.
Cite
Text
Shen et al. "Simple Atom Selection Strategy for Greedy Matrix Completion." International Joint Conference on Artificial Intelligence, 2015.Markdown
[Shen et al. "Simple Atom Selection Strategy for Greedy Matrix Completion." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/shen2015ijcai-simple/)BibTeX
@inproceedings{shen2015ijcai-simple,
title = {{Simple Atom Selection Strategy for Greedy Matrix Completion}},
author = {Shen, Zebang and Qian, Hui and Zhou, Tengfei and Wang, Song},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2015},
pages = {1799-1805},
url = {https://mlanthology.org/ijcai/2015/shen2015ijcai-simple/}
}