1-Bit Matrix Completion

By Mark A. Davenport, Yaniv Plan, Ewout van den Berg, Mary Wootters. arXiv.org, 2012

375 citations recorded by the source corpus.

In this paper we develop a theory of matrix completion for the extreme case of noisy 1-bit observations. Instead of observing a subset of the real-valued entries of a matrix M, we obtain a small number of binary (1-bit) measurements generated according to a probability distribution determined by the real-valued entries of M. The central question we ask is whether or not it is possible to obtain an accurate estimate of M from this data. In general this would seem impossible, but we show that the maximum likelihood estimate under a suitable constraint returns an accurate estimate of M when ||M||_{\infty} <= \alpha, and rank(M) <= r. If the log-likelihood is a concave function (e.g., the logistic or probit observation models), then we can obtain this maximum likelihood estimate by optimizing a convex program. In addition, we also show that if instead of recovering M we simply wish to obtain an estimate of the distribution generating the 1-bit measurements, then we can eliminate the requirement that ||M||_{\infty} <= \alpha. For both cases, we provide lower bounds showing that these estimates are near-optimal. We conclude with a suite of experiments that both verify the implications of our theorems as well as illustrate some of the practical applications of 1-bit matrix completion. In particular, we compare our program to standard matrix completion methods on movie rating data in which users submit ratings from 1 to 5. In order to use our program, we quantize this data to a single bit, but we allow the standard matrix completion program to have access to the original ratings (from 1 to 5). Surprisingly, the approach based on binary data performs significantly better.

Subfields: Computational Mechanics, Statistics and Probability, Signal Processing

View Paper: https://www.semanticscholar.org/paper/03d2af05e41aac58ebae4ab37f09155e53d4b35b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

In Signal Processing

Citations in the corpus

Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, methodology): “One body of past work [24, 16] has studied the recovery of approximately low-rank matrices with bounded nuclear norm—that is, matrices whose vectors of singular values are in the `q ball with q = 1.”
Matrix estimation by Universal Singular Value Thresholding (2012, methodology): “Section 3.1 of [38] gives a matrix estimation algorithm based on nuclear norm penalization that achieves this minimax rate up to a logarithmic factor.”
The non-convex geometry of low-rank matrix optimization (2016, background): “We remark that such a constraint on ‖X‖∞ is also required in the seminal work [17], while by using the BurerMonteiro parameterization, our result removes the time-consuming nuclear norm constraint.”
Generalized Low Rank Models (2014, background): “1) (under a few mild technical conditions) with an appropriate loss function [34].”
Item Response Theory—A Statistical Framework for Educational and Psychological Measurement (2021, neutral): “More precisely, for the completion of a binary or categorical matrix, it is often assumed that the data matrix follows a probabilistic model parameterized by a low-rank matrix (Bhaskar, 2016; Bhaskar and Javanmard, 2015; Cai and Zhou, 2013; Davenport et al., 2014; Zhu et al., 2016).”
Structured Latent Factor Analysis for Large-scale Data: Identifiability, Estimability, and Their Implications (2017, methodology): “Results similar to (14) have also been derived in the literature of matrix completion (e.g. Candès and Plan, 2010; Davenport et al., 2014) under specific statistical models with an underlying low rank structure.”
Matrix recovery from quantized and corrupted measurements (2014, background): “The recent popularity of MC and RPCA is mainly due to the fact that they find use in a large number of practical applications and fields, including (but not limited to) collaborative filtering [4, 5], foreground-background separation [2], financial data analysis [6], and compressive sensing [7].”
A Field Guide to Forward-Backward Splitting with a FASTA Implementation (2014, methodology): “Another loss function arises in 1-bit matrix completion, which can be viewed as an instance of low-rank logistic regression [21].”
An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, methodology): “The recovery algorithm in [101] is a simple modification of (7), but where the fidelity constraint ‖A(X)− y‖(2)F is replaced by the negative log-likelihood of X given observations from the model in (23).”
Matrix Completion has No Spurious Local Minimum (2016, background): “Can we replace the objective function with a different distance measure rather than Frobenius norm (which is related to works on 1-bit matrix sensing [DPvdBW14])?”
No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (2017, background): “, 2016) and 1-bit matrix sensing(Davenport et al., 2014) where the Hessian operator may behave differently as the settings we can analyze.”