Abstract: One of the main goals of recommendation systems is to predict unobserved ratings. The majority of existing methods implicitly assume that all entries are missing at random and homogeneous, that is, the ratings are revealed with the same probability. However, studies have shown that this assumption is often too strong in real-data applications. We propose a zero-imputation method for solving prediction problems under heterogeneous missing situations. Our algorithm has a closed-form solution, is scalable to large data sets, and can be extended to include the cold-start prediction problems, where one needs a prediction for a new user or item with no prior ratings. We provide theoretical guarantees for the proposed method and demonstrate its good performance in a data analysis and in simulations.

Key words and phrases: Bipartite graph, cold start, missing values.