# PU Learning for Matrix Completion

arXiv: https://arxiv.org/abs/1411.6081 · HTML: https://mlsanity.com/paper/1411.6081/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2014.

## Built on by (most cited first, 30 of 30)

- [Multi-Label Learning from Single Positive Labels](https://mlsanity.com/paper/2106.09708/) (2021)
- [Multiscale Positive-Unlabeled Detection of AI-Generated Texts](https://mlsanity.com/paper/2305.18149/) (2023)
- [Feed Two Birds with One Scone: Exploiting Wild Data for Both Out-of-Distribution Generalization and Detection](https://mlsanity.com/paper/2306.09158/) (2023)
- [How Does Unlabeled Data Provably Help Out-of-Distribution Detection?](https://mlsanity.com/paper/2402.03502/) (2024)
- [Double Correction Framework for Denoising Recommendation](https://mlsanity.com/paper/2405.11272/) (2024)
- [Knowledge Learning with Crowdsourcing: A Brief Review and Systematic Perspective](https://mlsanity.com/paper/2206.09315/) (2022)
- [Fairness-aware Model-agnostic Positive and Unlabeled Learning](https://mlsanity.com/paper/2206.09346/) (2022)
- [Beyond Myopia: Learning from Positive and Unlabeled Data through Holistic Predictive Trends](https://mlsanity.com/paper/2310.04078/) (2023)
- [Positive Unlabeled Contrastive Learning](https://mlsanity.com/paper/2206.01206/) (2022)
- [When Less is Enough: Positive and Unlabeled Learning Model for Vulnerability Detection](https://mlsanity.com/paper/2308.10523/) (2023)
- [Class Prior-Free Positive-Unlabeled Learning with Taylor Variational Loss for Hyperspectral Remote Sensing Imagery](https://mlsanity.com/paper/2308.15081/) (2023)
- [Positive-Unlabeled Classification under Class-Prior Shift: A Prior-invariant Approach Based on Density Ratio Estimation](https://mlsanity.com/paper/2107.05045/) (2021)
- [Concentration properties of fractional posterior in 1-bit matrix completion](https://mlsanity.com/paper/2404.08969/) (2024)
- [Rethinking Missing Data: Aleatoric Uncertainty-Aware Recommendation](https://mlsanity.com/paper/2209.11679/) (2022)
- [Out-of-Distribution Detection using Synthetic Data Generation](https://mlsanity.com/paper/2502.03323/) (2025)
- [Learning From Positive and Unlabeled Data Using Observer-GAN](https://mlsanity.com/paper/2208.12477/) (2022)
- [Meta-learning for Positive-unlabeled Classification](https://mlsanity.com/paper/2406.03680/) (2024)
- [Medix: Out-of-Distribution Detection from Unlabeled Wild Data via Robust Gradient Statistics](https://mlsanity.com/paper/2510.06505/) (2025)
- [Scalable Unidirectional Pareto Optimality for Multi-Task Learning with Constraints](https://mlsanity.com/paper/2110.15442/) (2021)
- [Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization](https://mlsanity.com/paper/2205.03059/) (2022)
- [Robust Learning under Hybrid Noise](https://mlsanity.com/paper/2407.04029/) (2024)
- [Accessible, Realistic, and Fair Evaluation of Positive-Unlabeled Learning Algorithms](https://mlsanity.com/paper/2509.24228/) (2025)
- [Noisy-Pair Robust Representation Alignment for Positive-Unlabeled Learning](https://mlsanity.com/paper/2510.01278/) (2025)
- [Learning from Interval Targets](https://mlsanity.com/paper/2510.20925/) (2025)
- [Heterogeneous network-based drug repurposing for COVID-19](https://mlsanity.com/paper/2107.09217/) (2021)
- [One-Bit Matrix Completion with Differential Privacy](https://mlsanity.com/paper/2110.00719/) (2021)
- [Learning A Disentangling Representation For PU Learning](https://mlsanity.com/paper/2310.03833/) (2023)
- [Misclassification excess risk bounds for 1-bit matrix completion](https://mlsanity.com/paper/2312.12945/) (2023)
- [Detecting Scarce and Sparse Anomalous: Solving Dual Imbalance in Multi-Instance Learning](https://mlsanity.com/paper/2503.13562/) (2025)
- [Correct and Weight: A Simple Yet Effective Loss for Implicit Feedback Recommendation](https://mlsanity.com/paper/2601.04291/) (2026)

## Abstract (arXiv)

In this paper, we consider the matrix completion problem when the observations are one-bit measurements of some underlying matrix M, and in particular the observed samples consist only of ones and no zeros. This problem is motivated by modern applications such as recommender systems and social networks where only "likes" or "friendships" are observed. The problem of learning from only positive and unlabeled examples, called PU (positive-unlabeled) learning, has been studied in the context of binary classification. We consider the PU matrix completion problem, where an underlying real-valued matrix M is first quantized to generate one-bit observations and then a subset of positive entries is revealed. Under the assumption that M has bounded nuclear norm, we provide recovery guarantees for two different observation models: 1) M parameterizes a distribution that generates a binary matrix, 2) M is thresholded to obtain a binary matrix. For the first case, we propose a "shifted matrix completion" method that recovers M using only a subset of indices corresponding to ones, while for the second case, we propose a "biased matrix completion" method that recovers the (thresholded) binary matrix. Both methods yield strong error bounds --- if M is n by n, the Frobenius error is bounded as O(1/((1-rho)n), where 1-rho denotes the fraction of ones observed. This implies a sample complexity of O(nlog n) ones to achieve a small error, when M is dense and n is large. We extend our methods and guarantees to the inductive matrix completion problem, where rows and columns of M have associated features. We provide efficient and scalable optimization procedures for both the methods and demonstrate the effectiveness of the proposed methods for link prediction (on real-world networks consisting of over 2 million nodes and 90 million links) and semi-supervised clustering tasks.