Abstract
We consider the recovery of a low-rank matrix from its clipped observations.Clipping is a common prohibiting factor in many scientific areas that obstructsstatistical analyses. On the other hand, matrix completion (MC) methods canrecover a low-rank matrix from various information deficits by using theprinciple of low-rank completion. However, the current theoretical guaranteesfor low-rank MC do not apply to clipped matrices, as the deficit depends on theunderlying values. Therefore, the feasibility of clipped matrix completion(CMC) is not trivial. In this paper, we first provide a theoretical guaranteefor an exact recovery of CMC by using a trace norm minimization algorithm.Furthermore, we introduce practical CMC algorithms by extending MC methods. Thesimple idea is to use the squared hinge loss in place of the squared loss wellused in MC methods for reducing the penalty of over-estimation on clippedentries. We also propose a novel regularization term tailored for CMC. It is acombination of two trace norm terms, and we theoretically bound the recoveryerror under the regularization. We demonstrate the effectiveness of theproposed methods through experiments using both synthetic data and real-worldbenchmark data for recommendation systems.