---
title: "Simple Atom Selection Strategy for Greedy Matrix Completion"
authors:
  - "Zebang Shen"
  - "Hui Qian"
  - "Tengfei Zhou"
  - "Song Wang"
doi: ""
url: "https://ijcai.org/proceedings/2015/256"
pdf: "https://ijcai.org/proceedings/2015/0256.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "1799-1804"
track: "Main Track"
keywords:
---

# Simple Atom Selection Strategy for Greedy Matrix Completion

Zebang Shen, Hui Qian, Tengfei Zhou, Song Wang

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 1799-1804.

## 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.