1-bit matrix completion
From MaRDI portal
Abstract: 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.
Recommendations
- A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
- Probabilistic low-rank matrix completion from quantized measurements
- 1-bit matrix completion: PAC-Bayesian analysis of a variational approximation
- Exact matrix completion via convex optimization
- Adaptive multinomial matrix completion
Cited in
(58)- Adaptive multinomial matrix completion
- scientific article; zbMATH DE number 7370536 (Why is no real title available?)
- Item response theory -- a statistical framework for educational and psychological measurement
- Misclassification excess risk bounds for 1-bit matrix completion
- Maximum a posteriori inference of random dot product graphs via conic programming
- 1-bit matrix completion: PAC-Bayesian analysis of a variational approximation
- Population-Level Balance in Signed Networks
- Flexible low-rank statistical modeling with missing data and side information
- Matrix Completion under Low-Rank Missing Mechanism
- A network model that combines latent factors and sparse graphs
- Concentration properties of fractional posterior in 1-bit matrix completion
- Matrix estimation by universal singular value thresholding
- Universal latent space model fitting for large networks with edge covariates
- Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
- High-dimensional large-scale mixed-type data imputation under missing at random
- One-bit tensor completion via transformed tensor singular value decomposition
- Matrix completion under complex survey sampling
- Collective matrix completion
- Generalized Low-Rank Plus Sparse Tensor Estimation by Fast Riemannian Optimization
- A nonlinear matrix decomposition for mining the zeros of sparse data
- Dynamic assortment personalization in high dimensions
- Dueling optimization with a monotone adversary
- Joint maximum likelihood estimation for high-dimensional exploratory item factor analysis
- Low-rank matrix completion with Poisson observations via nuclear norm and total variation constraints
- Matrix completion via max-norm constrained optimization
- Matrix completion from a computational statistics perspective
- Robust tensor completion from uniformly dithered one-bit observations
- scientific article; zbMATH DE number 7306859 (Why is no real title available?)
- Maximum likelihood estimation of sparse networks with missing observations
- Provable accelerated gradient method for nonconvex low rank optimization
- A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
- Latent Space Model for Higher-Order Networks and Generalized Tensor Decomposition
- Link Prediction for Egocentrically Sampled Networks
- Projective, sparse and learnable latent position network models
- A Zero-imputation Approach in Recommendation Systems with Data Missing Heterogeneously
- Statistical inference for covariate-adjusted and interpretable generalized latent factor model with application to testing fairness
- Learning from comparisons and choices
- Matrix estimation, latent variable model and collaborative filtering
- High-dimensional index volatility models via Stein's identity
- Active matrix factorization for surveys
- Uniform recovery guarantees for quantized corrupted sensing using structured or generative priors
- Variational Inference for Stochastic Block Models From Sampled Data
- Generalized high-dimensional trace regression via nuclear norm regularization
- Theoretical guarantees for low-rank compression of deep neural networks
- 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
- scientific article; zbMATH DE number 7370528 (Why is no real title available?)
- A latent factor model for high-dimensional binary data
- Structured latent factor analysis for large-scale data: identifiability, estimability, and their implications
- Iterative Collaborative Filtering for Sparse Matrix Estimation
- Discussion of the paper ``On concentration for (regularized) empirical risk minimization
- A Majorization-Minimization Gauss-Newton Method for 1-Bit Matrix Completion
- Conformalized Tensor Completion with Riemannian Optimization
- A two-step item bank calibration strategy based on 1-bit matrix completion for small-scale computerized adaptive testing
- Semiparametric modeling and analysis for longitudinal network data
- Exponential family tensor completion with auxiliary information
- High-dimensional estimation with geometric constraints
- Online optimization for max-norm regularization
- Probabilistic low-rank matrix completion from quantized measurements
This page was built for publication: 1-bit matrix completion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5177868)
