2018/09/13 by Takeshi Teshima, Miao Xu, Teshima, Takeshi +5
Computer Science · Engineering · Mathematics · #Algorithm #Artificial intelligence #Blind Source Separation Techniques #Clipping (morphology) #Combinatorics #Computer science #FOS: Computer and information sciences #Hinge loss #Image and Signal Denoising Methods #Low-rank approximation #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical optimization #Mathematics #Matrix (chemical analysis) #Matrix completion #Matrix norm #Mean squared error #Minification #Rank (graph theory) #Regularization (linguistics) #Sparse and Compressive Sensing Techniques #Statistics #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1809.04997
published in arXiv (Cornell University) (Cornell University) · 36 pages, 3 figures, The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)
openalex publication_date 2018/09/13 · arxiv created 2019/03/04 · arxiv updated 2019/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We consider the problem of recovering a low-rank matrix from its clipped observations. Clipping is conceivable in many scientific areas that obstructs statistical analyses. On the other hand, matrix completion (MC) methods can recover a low-rank matrix from various information deficits by using the principle of low-rank completion. However, the current theoretical guarantees for low-rank MC do not apply to clipped matrices, as the deficit depends on the underlying values. Therefore, the feasibility of clipped matrix completion (CMC) is not trivial. In this paper, we first provide a theoretical guarantee for the exact recovery of CMC by using a trace-norm minimization algorithm. Furthermore, we propose practical CMC algorithms by extending ordinary MC methods. Our extension is to use the squared hinge loss in place of the squared loss for reducing the penalty of over-estimation on clipped entries. We also propose a novel regularization term tailored for CMC. It is a combination of two trace-norm terms, and we theoretically bound the recovery error under the regularization. We demonstrate the effectiveness of the proposed methods through experiments using both synthetic and benchmark data for recommendation systems.