# Matrix Completion from One-Bit Dither Samples

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 78 references that are in the map.
- First posted on arXiv 5 Oct 2023.

## Builds on (most cited first, 12 of 12)

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion](https://mlsanity.com/paper/1309.6013/) (2013)
- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [Sketched Newton-Raphson](https://mlsanity.com/paper/2006.12120/) (2020)
- [UNO: Unlimited Sampling Meets One-Bit Quantization](https://mlsanity.com/paper/2301.10155/) (2022)
- [The Generalized Lasso for Sub-gaussian Measurements with Dithered Quantization](https://mlsanity.com/paper/1807.06976/) (2018)
- [1-Bit Matrix Completion under Exact Low-Rank Constraint](https://mlsanity.com/paper/1502.06689/) (2015)
- [Categorical Matrix Completion](https://mlsanity.com/paper/1507.00421/) (2015)
- [One-Bit Phase Retrieval: More Samples Means Less Complexity?](https://mlsanity.com/paper/2203.08982/) (2022)
- [Gridless Parameter Estimation for One-Bit MIMO Radar with Time-Varying Thresholds](https://mlsanity.com/paper/1908.10487/) (2019)
- [One-Bit Quadratic Compressed Sensing: From Sample Abundance to Linear Feasibility](https://mlsanity.com/paper/2303.09594/) (2023)

## Abstract (arXiv)

We explore the impact of coarse quantization on matrix completion in the extreme scenario of dithered one-bit sensing, where the matrix entries are compared with time-varying threshold levels. In particular, instead of observing a subset of high-resolution entries of a low-rank matrix, we have access to a small number of one-bit samples, generated as a result of these comparisons. In order to recover the low-rank matrix using its coarsely quantized known entries, we begin by transforming the problem of one-bit matrix completion (one-bit MC) with time-varying thresholds into a nuclear norm minimization problem. The one-bit sampled information is represented as linear inequality feasibility constraints. We then develop the popular singular value thresholding (SVT) algorithm to accommodate these inequality constraints, resulting in the creation of the One-Bit SVT (OB-SVT). Our findings demonstrate that incorporating multiple time-varying sampling threshold sequences in one-bit MC can significantly improve the performance of the matrix completion algorithm. In pursuit of achieving this objective, we utilize diverse thresholding schemes, namely uniform, Gaussian, and discrete thresholds. To accelerate the convergence of our proposed algorithm, we introduce three variants of the OB-SVT algorithm. Among these variants is the randomized sketched OB-SVT, which departs from using the entire information at each iteration, opting instead to utilize sketched data. This approach effectively reduces the dimension of the operational space and accelerates the convergence. We perform numerical evaluations comparing our proposed algorithm with the maximum likelihood estimation method previously employed for one-bit MC, and demonstrate that our approach can achieve a better recovery performance.