Low-Rank Matrix Recovery from One-Bit Comparison Information

Abstract

In this paper, we study the problem of low-rank matrix recovery based on the information obtained by comparing matrix entries (where each comparison is represented by one-bit) and not the entries themselves. This is highly relevant in the context of recommendation systems, due to the fact that users (particularly those less familiar with the rating system) are more comfortable with comparing products than giving exact ratings. We investigate when and how a low-rank matrix (such as a rating matrix in the recommendation system) can be efficiently recovered using one-bit data, particularly by establishing the limitations of such a recovery. We devise a computational approach based on matrix factorization to accomplish the reconstruction task. The numerical examples exhibit the significant potential of the proposed approach in low-rank matrix recovery from one-bit comparison information.