# Matrix Completion from One-Bit Dither Samples

Arian Eamaz, , Farhang Yeganegi, and Mojtaba Soltanalian, This work was
supported in part by the National Science Foundation Grant CCF-1704401. The
conference precursor to this work was presented at the 2023 IEEE International
Conference on Sampling Theory and Applications (SampTA). (_Corresponding
author: Arian Eamaz_)The authors are with the Department of Electrical and
Computer Engineering, University of Illinois Chicago, Chicago, IL 60607, USA
(e-mail: _{aeamaz2, fyegan2, msol}@uic.edu_).

###### Abstract

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 _O_ ne-_B_ it _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.

###### Index Terms:

Coarse quantization, matrix completion, one-bit sensing, singular value
thresholding, time-varying thresholds.

##  I Introduction

Matrix completion, which involves recovering an unknown low-rank matrix based
on partial information, is a ubiquitous challenge in numerous practical fields
such as collaborative filtering [1], system identification [2], and sensor
localization [3]. As a distinctive form of low-rank matrix sensing, matrix
completion presents unique difficulties, particularly because the sampling
matrices may not necessarily adhere to the conditions of the matrix restricted
isometry property (RIP) [4, 5]. A notable revelation has surfaced: when
dealing with a matrix $\mathbf{X}$ of rank $r$, and barring excessive
_structure_ , a compact, randomly chosen subset of its entries can facilitate
an exact reconstruction. This pivotal finding was initially substantiated by
[6] through a meticulous analysis of a convex relaxation technique introduced
by [7]. One parameter that plays a crucial role in determining the feasibility
of matrix completion is a certain incoherence measure, proposed in [6].

Numerous algorithms have been suggested to address the matrix completion
problem. These range from solvers for the nuclear norm minimization problem
[6, 8, 9] to algorithms based on low-rank matrix factorization [10, 11, 12,
13].

A prime example for matrix completion applications is the Netflix challenge,
where the user rating matrix is presumed to be approximately low rank owing to
the widely accepted notion that only a handful of factors influence a person’s
taste or preference[6, 5]. Another emerging application of matrix completion
is in waveform design for multiple-input and multiple-output (MIMO) radars[14,
15]. In a comprehensive manner, the authors of [14, 16, 15] conducted an
extensive exploration of MIMO radars employing sparse sensing and matrix
completion techniques. These approaches prove highly advantageous in
significantly reducing the data volume required by MIMO radars for accurate
target detection and estimation. In MIMO-MC radars, the receive antennas
transmit subsampled target returns to a fusion center, which fills a data
matrix partially. Subsequently, MC techniques are employed to complete the
data matrix, enabling the estimation of target parameters using standard array
processing methods. MIMO radars equipped with sparse sensing and matrix
completion techniques have the potential to drastically decrease the amount of
data necessary for precise target detection and estimation. This reduction in
data volume can lead to a more efficient and accurate MIMO radar system. In
their work [17], the authors introduced a widely separated MIMO (WS-MIMO)
radar system that utilizes sub-Nyquist sampling and reduced rates at each of
its multiple receivers. Consequently, the received data matrix contains
missing information. To address this challenge, the authors employed matrix
completion techniques to recover the missing samples of each receiver’s signal
matrix.

Quantization is a crucial step in digital signal processing that converts
continuous signals into discrete representations. However, to achieve high-
resolution quantization, a large number of quantization levels are required,
which can result in increased power consumption, manufacturing cost, and a
reduced sampling rate in analog-to-digital converters (ADCs). To mitigate
these issues, researchers have explored the use of fewer quantization bits,
including the extreme case of one-bit quantization where the signals are
compared with a fixed threshold at the ADCs, resulting in sign outputs[18,
19]. This approach enables high-rate sampling while reducing implementation
cost and energy consumption compared to multi-bit ADCs. One-bit ADCs have
proven to be immensely valuable across a range of applications, including MIMO
[20, 21], channel estimation [22], and array signal processing [23].

Extensive research has been conducted to investigate the impact of
thresholding (dithering) on the quantization process and its effect on
quantization error [24, 25, 26, 27, 28]. The mean squared error (MSE) is a
relevant parameter used to evaluate the performance of a quantizing system,
particularly in digital signal processing applications. By employing
dithering, the system’s performance can be flexibly controlled, as it enables
a trade-off between accuracy and resolution. Dithering has the remarkable
property of reducing the overall average quantization error [27]. Multiple
dithering schemes have been studied, including uniform dither, discrete
dither, and Gaussian dither. Research findings indicate that a carefully
chosen dither signal can significantly enhance the resolution and performance
of digital instrumentation. While discrete dithering has also been analyzed,
it generally does not perform as well as uniform or Gaussian dithering in
terms of quantization error reduction [27].

After thorough analysis in [29, 30, 27], it is evident that when considering
both resolution and accuracy in quantizers, the performance of the quantizing
scheme remains nearly unchanged whether Gaussian or uniformly distributed
dither signals are employed. It is important to acknowledge that while
discrete dithering may not match the performance of uniform or Gaussian
dithering, it offers notable advantages in terms of practical implementation.
Specifically, in the context of Cramér-Rao bound (CRB) analysis, Gaussian
dithering exhibits better performance for input signals with bell-shaped
distributions [31].

The time-varying thresholds are realized through a randomly (usually,
Gaussian) dithered generator within the ADC [32]. The source of this Gaussian
dither is a low-cost thermal noise diode, which may require additional
circuitry and amplifiers to enhance the noise levels; see, for instance, [33]
for the implementation of multiple dithering in 12-bit, 18 gigasamples per
second (GS/s) ADC.

In recent works, researchers have proposed using time-varying thresholds to
improve the estimation of signal characteristics, addressing this challenge
[34, 35, 31, 36]. For instance, [37, 38, 39] considered Gaussian dithering for
recovering covariance from one-bit measurements. In [40], the authors provide
a comprehensive investigation of estimating the covariance matrix from one-bit
measurements using Uniform dithering. Moreover, dithered one-bit quantization
has found applications in various problems discussed in contemporary
literature, including sparse parameter estimation [41, 42], compressed sensing
[36, 43, 44], phase retrieval [45], and sampling theory [46].

The recovery of low-rank matrices from highly-quantized measurements, where
the number of measurements is expected to be much smaller than that of
unknowns, is an emerging research area in statistical signal processing and
machine learning. This field of study has the potential to facilitate the
development of cost-effective and efficient systems [47, 48, 49, 50, 44].

The theory behind matrix completion typically assumes that observations
consist of continuous values within the matrix. However, the Netflix problem
involves ”quantized” observations that are restricted to integers between 1
and 5. This presents a challenge for high-resolution matrix completion
techniques, as the impact of coarse quantization becomes more apparent. This
issue is particularly prominent in recommender systems, where ratings are
reduced to a single bit indicating a positive or negative rating (e.g., rating
music on Pandora, determining the relevance of advertisements on Hulu, or
evaluating posts on sites like MathOverflow). In such cases, the assumptions
made in existing matrix completion theory do not hold true[47]. MIMO radar
systems with one-bit ADC receivers provide another example where traditional
matrix completion techniques may not be used for waveform design due to coarse
quantization applied to the received measurements [14].

Randomized sketching is a widely used technique for dimension reduction that
encompasses various iterative methods for solving linear systems and their
variations, as well as extensions to non-linear optimization problems [51]. It
encompasses well-known methods such as randomized Kaczmarz [52], coordinate
descent [53], and variants of the Newton method in convex optimization [54],
among others. In this approach, instead of utilizing all available information
at each iteration, only a sketched subset of the information is used, which is
selected through a sketching process. This paper introduces a novel approach
where, for the first time in the literature, the first algorithmic paradigm is
employed to sketch the one-bit data matrix. The proposed method utilizes
sketched information exclusively at each iteration, resulting in a more
efficient structure.

###  I-A Prior Arts

One-bit low-rank matrix sensing has emerged as a relatively unexplored area,
with a handful of papers, including [55, 50], shedding light on this
intriguing subject. In [55], the authors delved into the theoretical
guarantees of one-bit sensing from low-rank matrices using two distinct
algorithms: one employing hard singular value thresholding and the other
relying on semidefinite programming. Both of these notable papers focused
exclusively on scenarios involving Gaussian sampling matrices. However, it is
important to note that they did not delve into the exploration of matrix
completion with coarse quantization.

In [47, 56], the initial attempt to address one-bit matrix completion (one-bit
MC) involved developing theoretical guarantees under the generalized linear
model. The authors derived a regularized maximum likelihood estimate (MLE)
based on a probability distribution determined by the real-valued noisy
entries of the low-rank matrix. To constrain the MLE problem, the authors
employed the nuclear and Frobenius norms, drawing inspiration from previous
work on one-bit compressed sensing[47]. They utilized projected gradient
descent to solve the regularized MLE obtained. In [47] and [56], the authors
present various theoretical guarantees and necessary conditions for achieving
perfect recovery performance in the context of the MLE problem. They establish
these guarantees by considering the rank and number of measurements required,
ensuring optimal solutions when the density function is concave. A max-norm
constrained MLE for the one-bit MC problem was comprehensively investigated in
[48]. In their work [57], the authors developed a greedy algorithm that
extends the concept of conditional gradient descent to efficiently solve the
regularized MLE for the one-bit MC problem. The concept of regularized MLE for
the one-bit MC problem was further extended to the quantized MC problem in
[58]. For quantized MC problem, the authors of [59] considered a Trace norm
regularized MLE with a likelihood function for categorical distribution. In
[49], a regularized MLE for MC from quantized and erroneous measurements was
proposed which considers the sparse additive error in the model.

Furthermore, [47] includes a set of experiments that not only validate the
implications of their theorems but also demonstrate practical applications of
one-bit MC. Notably, the authors compare one-bit MC to standard matrix
completion methods using movie rating data, where users submit ratings ranging
from 1 to 5. To utilize one-bit MC, they quantize the data to a single bit,
while the standard matrix completion algorithm has access to the original
ratings. _Surprisingly, the approach based on binary data outperforms the
standard matrix completion approach significantly_[47].

###  I-B Motivation and Contributions of the Paper

To derive the MLE and take advantage of time-varying thresholds (random
dithering), authors of [47] considered noisy measurements, where the noise can
be seen as time-varying thresholds. However, as demonstrated in [60, 46, 45,
38, 36], the design of time-varying thresholds is a critical aspect of one-bit
sensing that can significantly improve signal reconstruction performance.
However, by utilizing noise as our dithering, as was demonstrated in [47], we
constrain our thresholds to follow the behavior of the noise, which is not
under our control. Moreover, in scenarios involving non-convex distributions,
the uniqueness of the solution in the MLE problem is not guaranteed. In order
for the recovery of the matrix to be feasible, certain assumptions must be
made on the noise distribution, as discussed in [47, 48, 56, 49, 57]. In
practical scenarios, however, we cannot assume that the noise follows a
distribution with properties that ensure good recovery performance for the
regularized MLE problem.

Dithering is particularly relevant in matrix completion scenarios like
recommendation systems, where users may prefer to compare products rather than
provide exact ratings. This approach can improve the user interface’s
usability and, in some cases, enhance the accuracy of ratings [61, 47]. For
example, a user may evaluate an anime’s quality by comparing it to their
favorite show, such as Jujutsu Kaisen, and rate it on IMDb accordingly, or
simply give it a thumbs-up or thumbs-down as one-bit data.

_The concept of dithered one-bit MC can be applied in digital signal
processing applications where ADCs benefit from the advantages of efficient
sampling in matrix completion, treating low-rate samples as partially observed
data matrices, and the cost-effectiveness of coarse quantization_. This
approach holds great potential for applications such as MIMO-MC [14] and WS-
MIMO [17]. Our main contributions in this paper are:
1) Combined matrix completion with dithered one-bit quantization framework. In
the proposed dithered one-bit MC framework, we leverage upon the benefits of
both one-bit sensing with time-varying sampling thresholds and efficient
sampling in the matrix completion. We frame this as a nuclear norm
minimization problem, constrained by a _linear inequality_ system obtained
from the one-bit sensing with multiple dithering scheme. _Our formulation
allows for the freedom to design or select appropriate thresholds to enhance
the recovery performance._
2) SVT-based recovery. We propose the _O_ ne-_B_ it _SVT_ (OB-SVT) algorithm,
which utilizes an SVT specifically developed to address nuclear norm
minimization problems with linear inequality constraints. To enhance the
convergence rate and recovery performance, we propose additional variants of
OB-SVT. Specifically, we incorporate the concept of sketch-and-project into
SVT. This involves utilizing sketched one-bit measurements obtained by
multiplying the sparse Gaussian sketch matrix with the one-bit data matrix for
each inequality constraint. Our approach reduces computational load by using
sketched measurements instead of processing full one-bit data from multiple
comparisons, and we show its superior performance compared to the MLE method
proposed by [47] in both noiseless and noisy scenarios.
3) Performance guarantees. Our theoretical analyses provide an upper bound on
the error recovery of the one-bit MC problem that is applicable to any chosen
algorithm. This upper bound depends on the number of measurements as well as
the maximum distances between the thresholds and the matrix entries. To
achieve better error recovery, we determine the probability and the required
number of time-varying sampling threshold sequences, which allows us to
surpass the upper bound and approach a desired error recovery value.
Additionally, we prove the convergence of the proposed algorithms and provide
various theoretical guarantees to ensure their convergence.
4) Recovery in the presence of additive noise. The proposed OB-SVT algorithm
has been slightly modified to handle the noisy one-bit MC problem. We conduct
a comprehensive investigation into the performance of the proposed OB-SVT
algorithms in the presence of noise. We experimentally evaluate the
algorithm’s performance under Gaussian and Poisson noise scenarios and observe
its robustness against these types of noise.
5) Comparing different dithering scenarios performance. This paper presents a
comprehensive comparison of Gaussian, uniform, and discrete dithering
techniques in the context of one-bit sensing for matrix completion. Notably,
we introduce the use of discrete dithering. While discrete dithering may not
offer the same level of performance as other schemes, its simplicity and ease
of implementation enable us to generate a larger number of dithering
sequences, resulting in improved recovery performance. Our study shows that
using Uniform dithering improves signal reconstruction performance when the
input matrix comes from a Uniform distribution. However, when measurements are
corrupted by bell-shaped noise or the input follows a Gaussian distribution,
Gaussian dithering performs better than Uniform dithering.
6) Dithering design with adaptive scheme. We introduce an adaptive threshold
design inspired by the Bregman iterative method [62, 63]. This adaptive
framework for one-bit MC, utilizes the concept of Bregman projection iterative
method to iteratively design a threshold that improves recovery performance.

###  I-C Organization and Notation

In the following section, we present an overview of one-bit quantization with
time-varying sampling thresholds. We introduce the one-bit MC problem, where
the task is to reconstruct a signal from one-bit sampled measurements. We
formulate this problem as a system of linear inequalities and describe the
one-bit MC solver, which utilizes nuclear norm minimization for both noisy and
noiseless scenarios. Section III introduces the OB-SVT algorithms, which are
specifically designed for one-bit MC. In Section IV, we provide various
theoretical guarantees for matrix recovery from the one-bit MC problem and
analyze the convergence rates of the proposed algorithms in both noisy and
noiseless cases. Section V focuses on the adaptive thresholding process by
combining the Bregman iterative method with the OB-SVT algorithms. We discuss
how this approach improves the recovery performance. In Section VI, we present
several numerical experiments to demonstrate the effectiveness of the proposed
algorithms. We compare them with state-of-the-art algorithms and evaluate
their performance in both noisy and noiseless scenarios using different
dithering schemes. Finally, in Section VII, we conclude our findings and
highlight the open discussion of this research.

_Notation:_ Throughout this paper, we use bold lowercase and bold uppercase
letters for vectors and matrices, respectively. We represent a vector
$\mathbf{x}$ and a matrix $\mathbf{B}$ in terms of their elements as
$\mathbf{x}=[x_{i}]$ and $\mathbf{x}=[B_{i,j}]$, respectively. The generalized
inverse operator is presented by $(\cdot)^{-}$. The sets of complex and real
numbers are $\mathbb{C}$ and $\mathbb{R}$, respectively; $(\cdot)^{\top}$,
$(\cdot)^{\ast}$and $(\cdot)^{\mathrm{H}}$ are the vector/matrix transpose,
conjugate and the Hermitian transpose, respectively. We define
$\mathbf{x}\succeq\mathbf{y}$ as a component-wise inequality between vectors
$\mathbf{x}$ and $\mathbf{y}$, i.e., $x_{i}\geq y_{i}$ for every index $i$.
The function $\textrm{diag}(.)$ returns the diagonal elements of the input
matrix. The nuclear norm of a matrix $\mathbf{B}\in\mathbb{C}^{M\times N}$ is
denoted $\left\|\mathbf{B}\right\|_{\star}=\sum^{r}_{i=1}\sigma_{i}$ where $r$
and $\left\\{\sigma_{i}\right\\}$ are the rank and singular values of
$\mathbf{B}$, respectively. The minimum and maximum singular values of
$\mathbf{B}$ are $\sigma_{\mathrm{max}}\left(\mathbf{B}\right)$ and
$\sigma_{\mathrm{min}}\left(\mathbf{B}\right)$, respectively. The Frobenius
norm of a matrix $\mathbf{B}\in\mathbb{C}^{M\times N}$ is defined as
$\|\mathbf{B}\|_{\mathrm{F}}=\sqrt{\sum^{M}_{r=1}\sum^{N}_{s=1}\left|b_{rs}\right|^{2}}$,
where $b_{rs}$ is the $(r,s)$-th entry of $\mathbf{B}$. The $\ell_{p}$-norm of
a vector $\mathbf{b}$ is
$\|\mathbf{b}\|_{p}=\left(\sum_{i}b^{p}_{i}\right)^{1/p}$. The Hadamard
(element-wise) products is $\odot$. The vectorized form of a matrix
$\mathbf{B}$ is written as $\mathrm{vec}\left(\mathbf{B}\right)$. Given a
scalar $x$, we define the operator $(x)^{+}$ as $\max\left\\{x,0\right\\}$.
For an event $\mathcal{E}$, $\mathbb{1}_{(\mathcal{E})}$ is the indicator
function for that event meaning that $\mathbb{1}_{(\mathcal{E})}$ is $1$ if
$\mathcal{E}$ occurs; otherwise, it is zero. The set $[n]$ is defined as
$[n]=\left\\{1,\cdots,n\right\\}$. The function $\operatorname{sgn}(\cdot)$
yields the sign of its argument. The function $\log(\cdot)$ denotes the
natural logarithm, unless its base is otherwise stated. The notation
$x\sim\mathcal{U}(a,b)$ means a random variable drawn from the uniform
distribution over the interval $[a,b]$ and $x\sim\mathcal{N}(\mu,\sigma^{2})$
represents the normal distribution with mean $\mu$ and variance $\sigma^{2}$.
The sub-Gaussian norm of a random variable $X$ is characterized by
$\|X\|_{\psi_{2}}=\inf\left\\{t>0:\mathbb{E}\left\\{e^{X^{2}/t^{2}}\right\\}\leq
2\right\\}$.

##  II One-Bit Matrix Completion

In this section, we first present the one-bit quantization using multiple
time-varying thresholds as a linear inequality feasibility problem. We then
formulate the one-bit MC problem as a nuclear norm minimization problem with
linear inequality constraints for both noisy and noiseless scenarios. Finally,
we develop the SVT algorithm in such a way to handle the linear inequality
constraints and recover the low-rank matrix. We call our proposed algorithm,
OB-SVT.

###  II-A One-Bit Sensing With Time-Varying Thresholds

In practice, the discrete-time samples occupy pre-determined quantized values.
We denote the quantization operation on $x_{k}$ by the function $Q(\cdot)$.
This yields the quantized signal as $r_{k}=Q(x_{k})$. In one-bit quantization,
compared to zero or constant thresholds, time-varying sampling thresholds
yield a better reconstruction performance [38]. These thresholds may be chosen
from any distribution. In this paper we examine the performance of one-bit
quantization under the discrete, uniform and Gaussian dithering scenarios. A
Gaussian non-zero time-varying threshold vector
$\bm{\uptau}_{\mathcal{N}}=\left[\tau_{k}\right]$ follows the distribution
$\bm{\uptau}_{\mathcal{N}}\sim\mathcal{N}\left(\mathbf{d}=\mathbf{1}d,\bm{\Sigma}\right)$
with mean $d$ and the covariance matrix $\bm{\Sigma}$. We also employ
uniformly distributed thresholds in the sequel as
$\bm{\uptau}_{\mathcal{U}}\sim\mathcal{U}_{\left[a,b\right]}$. We define the
discrete dithering as $\bm{\uptau}_{\mathcal{D}}$, which contains values as
$\tau_{k}\in\left[\frac{k}{M}D\right]$, where $D$ represents the peak-to-peak
dither amplitude, and $k\in\\{-M/2,\cdots,-1,1,\cdots,M/2\\}$ with an even
number $M$. It is important to note that when the number $M$ of equiprobable
impulses in the discrete dithering tends to infinity, it behaves similarly to
a uniform distribution. The distribution of discrete dither is given by [29]

$f(\tau)=\frac{1}{M}\sum_{k}\delta\left(\tau-\frac{k}{M}D\right).$ (1)

For one-bit quantization with such time-varying sampling thresholds,
$r_{k}=\operatorname{sgn}\left(x_{k}-\tau_{k}\right)$. For notational
simplicity, hereafter, we denote the time-varying sampling thresholds by
dropping the subscripts, i.e. $\bm{\uptau}=\left[\tau_{k}\right]$.

The information gathered through the one-bit sampling with time-varying
thresholds may be formulated in terms of an overdetermined linear system of
inequalities. We have $r_{k}=+1$ when $x_{k}>\tau_{k}$ and $r_{k}=-1$ when
$x_{k}<\tau_{k}$. Collecting all the elements in the vectors as
$\mathbf{x}=[x_{k}]\in\mathbb{R}^{n}$ and
$\mathbf{r}=[r_{k}]\in\mathbb{R}^{n}$, therefore, one can formulate the
geometric location of the signal as

$r_{k}\left(x_{k}-\tau_{k}\right)\geq 0.$ (2)

Then, the vectorized representation of (2) is
$\mathbf{r}\odot\left(\mathbf{x}-\bm{\uptau}\right)\succeq\mathbf{0}$ or
equivalently

$\displaystyle\bm{\Omega}\mathbf{x}$
$\displaystyle\succeq\mathbf{r}\odot\bm{\uptau},$ (3)

where $\bm{\Omega}\triangleq\operatorname{diag}\left(\mathbf{r}\right)$.
Suppose $\mathbf{x},\bm{\uptau}\in\mathbb{R}^{n}$, and that
$\bm{\uptau}^{(\ell)}$ denotes the time-varying sampling threshold in
$\ell$-th signal sequence, where $\ell\in[m]$.

For the $\ell$-th signal sequence, (3) becomes

$\displaystyle\bm{\Omega}^{(\ell)}\mathbf{x}$
$\displaystyle\succeq\mathbf{r}^{(\ell)}\odot\bm{\uptau}^{(\ell)},\quad\ell\in[m],$
(4)

where
$\bm{\Omega}^{(\ell)}=\operatorname{diag}\left(\mathbf{r}^{(\ell)}\right)$.
Denote the concatenation of all $m$ sign matrices as

$\tilde{\bm{\Omega}}=\left[\begin{array}[]{c|c|c}\bm{\Omega}^{(1)}&\cdots&\bm{\Omega}^{(m)}\end{array}\right]^{\top},\quad\in\mathbb{R}^{mn\times
n}.$ (5)

Rewrite the $m$ linear system of inequalities in (4) as

$\tilde{\bm{\Omega}}\mathbf{x}\succeq\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}\right),$
(6)

where $\mathbf{R}$ and $\bm{\Gamma}$ are matrices, whose columns are the
sequences $\left\\{\mathbf{r}^{(\ell)}\right\\}_{\ell=1}^{m}$ and
$\left\\{\bm{\uptau}^{(\ell)}\right\\}_{\ell=1}^{m}$, respectively.

The linear system of inequalities in (6) associated with the one-bit sampling
scheme is overdetermined. We recast (6) into a one-bit polyhedron as

$\displaystyle\mathcal{P}=\left\\{\mathbf{x}\mid\tilde{\bm{\Omega}}\mathbf{x}\succeq\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}\right)\right\\}.$
(7)

Instead of complex high-dimensional optimization with techniques such as MLE,
our objective is to employ the polyhedron (7) that encapsulates the desired
signal $\mathbf{x}$ and leads to solving linear inequalities with linear
convergence in expectation.

###  II-B One-Bit MC as Nuclear Norm Minimization Problem

Assume we apply the coarse quantization to the observed partial entries of a
low-rank matrix $\mathbf{X}\in\mathbb{R}^{n_{1}\times n_{2}}$ of rank $r$.
Define
$\mathcal{P}_{\Omega}\left(\mathbf{X}\right)=\left[\widehat{X}_{i,j}\right]$
be the orthogonal projector onto the span of matrices vanishing outside of
$\Omega$. These partial entries of $\mathbf{X}$ are obtained in subset
$\Omega$ as below:

$\displaystyle\widehat{X}_{i,j}$
$\displaystyle=\begin{cases}X_{i,j}&(i,j)\in\Omega,\\\
0&\text{otherwise}.\end{cases}$ (8)

In one-bit MC, we solely observe the partial matrix through the $\ell$-th one-
bit data matrix
$\bm{\mathcal{R}}^{(\ell)}=\left[r_{i,j}^{(\ell)}\right]\in\mathbb{R}^{m_{1}\times
m_{2}}$, where $m_{1}m_{2}\ll n_{1}n_{2}$. The entries in
$\bm{\mathcal{R}}^{(\ell)}$ are dependent on the comparison between
corresponding entries in $\mathcal{P}_{\Omega}\left(\mathbf{X}\right)$ and
$\ell$-th dithering matrix
$\bm{\mathcal{T}}^{(\ell)}=\left[\tau_{i,j}^{(\ell)}\right]\in\mathbb{R}^{n_{1}\times
n_{2}}$ according to the following relationship:

$\displaystyle r_{i,j}^{(\ell)}$
$\displaystyle=\begin{cases}+1&X_{i,j}>\tau_{i,j}^{(\ell)},\\\
-1&X_{i,j}<\tau_{i,j}^{(\ell)},\end{cases}\quad(i,j)\in\Omega,\quad\ell\in[m].$
(9)

Assume that the partial entries of $\mathbf{X}$ in the subset $\Omega$
correspond to the partial entries of the vectorized form
$\operatorname{vec}\left(\mathbf{X}\right)$ in the subset $\Omega^{\prime}$.
Define $\mathbf{P}\in\mathbb{R}^{m_{1}m_{2}\times n_{1}n_{2}}$ as a
permutation matrix that only selects the subset $\Omega^{\prime}$. For
$\ell$-th threshold matrix, we formulate the obtained one-bit scheme as the
following linear inequality feasibility problem:

$\displaystyle\bm{\Omega}^{(\ell)}\mathbf{P}\operatorname{vec}\left(\mathbf{X}\right)$
$\displaystyle\succeq\operatorname{vec}\left(\bm{\mathcal{R}}^{(\ell)}\right)\odot\left(\mathbf{P}\operatorname{vec}\left(\bm{\mathcal{T}}^{(\ell)}\right)\right),\quad\ell\in[m],$
(10)

where
$\bm{\Omega}^{(\ell)}=\operatorname{diag}\left(\operatorname{vec}\left(\bm{\mathcal{R}}^{(\ell)}\right)\right)$,
$\mathbf{P}\operatorname{vec}\left(\mathbf{X}\right)$ and
$\mathbf{P}\operatorname{vec}\left(\bm{\mathcal{T}}^{(\ell)}\right)$ only
return the subset $\Omega^{\prime}$ from
$\operatorname{vec}\left(\mathbf{X}\right)$ and
$\operatorname{vec}\left(\bm{\mathcal{T}}^{(\ell)}\right)$, respectively. As
demonstrated earlier, we rewrite (10) as

$\displaystyle\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)$
$\displaystyle\succeq\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}\right),$
(11)

where $\mathbf{R}$ and $\bm{\Gamma}$ are matrices, whose columns are the
sequences
$\left\\{\operatorname{vec}\left(\bm{\mathcal{R}}^{(\ell)}\right)\right\\}_{\ell=1}^{m}$
and
$\left\\{\mathbf{P}\operatorname{vec}\left(\bm{\mathcal{T}}^{(\ell)}\right)\right\\}_{\ell=1}^{m}$,
respectively, and

$\bm{\mathcal{B}}=\left[\begin{array}[]{c|c|c}\mathbf{P}^{\top}\bm{\Omega}^{(1)}&\cdots&\mathbf{P}^{\top}\bm{\Omega}^{(m)}\end{array}\right]^{\top}.$
(12)

Therefore, to recover the low-rank matrix $\mathbf{X}$ from highly-quantized
observed measurements, we must find the optimal solution from the following
feasible set:

$\displaystyle\mathcal{F}=\left\\{\mathbf{X}\mid\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)\succeq\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}\right),\leavevmode\nobreak\
\left\|\mathbf{X}\right\|_{\star}\leq\epsilon\right\\},$ (13)

where $\epsilon$ is the predefined threshold. The feasible set of one-bit MC
is written as a _nuclear norm minimization_ problem as below

$\displaystyle\mathcal{F}^{(1)}:\quad\underset{\mathbf{X}}{\textrm{minimize}}$
$\displaystyle\tau\left\|\mathbf{X}\right\|_{\star}+\frac{1}{2}\left\|\mathbf{X}\right\|^{2}_{\mathrm{F}}$
(14) subject to
$\displaystyle\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)\succeq\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}\right),$

for some fixed $\tau\geq 0$. More than nuclear norm, the Frobenius norm is
also considered to control the amplitudes of the unknown data [8]. In Section
III, we will propose various algorithms to tackle this problem.

###  II-C One-Bit MC With Noisy Entries

Herein, we formulate the noisy version of one-bit MC with time-varying
thresholds. Denote $\mathbf{Z}\in\mathbb{R}^{n_{1}\times n_{2}}$ as the noise
matrix. The noisy one-bit samples are generated as

$\displaystyle r_{i,j}^{(\ell)}$
$\displaystyle=\begin{cases}+1&X_{i,j}+Z_{i,j}>\tau_{i,j}^{(\ell)},\\\
-1&X_{i,j}+Z_{i,j}<\tau_{i,j}^{(\ell)},\end{cases}\quad(i,j)\in\Omega.$ (15)

Consequently, the noisy linear system of inequalities associated with (15) is
written as

$\bm{\mathcal{B}}\left(\operatorname{vec}\left(\mathbf{X}\right)+\operatorname{vec}\left(\mathbf{Z}\right)\right)\succeq\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}\right),$
(16)

or equivalently,

$\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)+\bm{\upnu}\succeq\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}\right),$
(17)

where $\bm{\upnu}=\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{Z}\right)$
is the noise of our system. For instance, if we consider
$\operatorname{vec}\left(\mathbf{Z}\right)\sim\mathcal{N}\left(\bm{\upmu},\bm{\Sigma}_{z}\right)$
with mean vector $\bm{\upmu}$ and covariance matrix $\bm{\Sigma}_{z}$, the
distribution of $\bm{\upnu}$ will be
$\mathcal{N}\left(\bm{\mathcal{B}}\bm{\upmu},\bm{\mathcal{B}}\bm{\Sigma}_{z}\bm{\mathcal{B}}^{\mathrm{H}}\right)$.

To find the feasible solution from a linear inequality feasibility problem
such as $\mathbf{C}\mathbf{x}\succeq\mathbf{b}$, we can rewrite the problem
as[53]

$\left(\mathbf{b}-\mathbf{C}\mathbf{x}\right)^{+}=0.$ (18)

If our system encounters a noise vector $\mathbf{n}$, we can slightly adjust
(18) to minimize the impact of noise using the following formula:

$\left|\left(\mathbf{b}-\mathbf{C}\mathbf{x}\right)^{+}\right|\preceq\bm{\upsigma}_{n},$
(19)

where $\bm{\upsigma}_{n}$ is the effect of noise. Thus, if $\mathbf{x}$ is
contained within $\mathbf{C}\mathbf{x}\succeq\mathbf{b}$, there is no need to
take (19) into account. However, if it is not, i.e.
$\mathbf{C}\mathbf{x}\preceq\mathbf{b}$, we must consider the following:

$\left|\mathbf{b}-\mathbf{C}\mathbf{x}\right|\preceq\bm{\upsigma}_{n}.$ (20)

Since $\mathbf{C}\mathbf{x}\preceq\mathbf{b}$, (20) is equivalent to

$\mathbf{b}-\bm{\upsigma}_{n}\preceq\mathbf{C}\mathbf{x}\preceq\mathbf{b}.$
(21)

By applying the same process to (16), the modified linear inequality
feasibility constraint is given by

$\displaystyle\mathcal{Y}=\left\\{\left\\{\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)\succeq\mathbf{t}\right\\}\cup\left\\{\mathbf{t}-\bm{\upsigma}_{z}\preceq\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)\preceq\mathbf{t}\right\\}\right\\},$
(22)

where
$\mathbf{t}=\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}\right)$,
and $\bm{\upsigma}_{z}$ is the effect of
$\operatorname{vec}\left(\mathbf{Z}\right)$. Therefore, the nuclear norm
minimization problem $\mathcal{F}^{(1)}$ is reformulated as

$\displaystyle\mathcal{F}^{(2)}:\quad\underset{\mathbf{X}}{\textrm{minimize}}$
$\displaystyle\tau\left\|\mathbf{X}\right\|_{\star}+\frac{1}{2}\left\|\mathbf{X}\right\|^{2}_{\mathrm{F}}$
(23) subject to
$\displaystyle\left(\mathbf{t}-\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)\right)^{+}\preceq\bm{\upsigma}_{z}.$

##  III Proposed Algorithms

The main contribution in the literature on the one-bit MC problem is the
introduction of the regularized MLE approach [47, 8, 56, 58, 57]. In this
section, we present a novel perspective by considering one-bit MC as a nuclear
norm minimization problem. To solve this problem, we adapt the popular
algorithm SVT to its one-bit versions which we will call them _O_ ne-_B_ it
_SVT_ (OB-SVT) algorithms.

###  III-A OB-SVT-I

To tackle $\mathcal{F}^{(1)}$, we employ the SVT algorithm generalized for
linear inequality constraints inspired by [8] as follows: Denote a linear
transformation $\mathcal{A}:\mathbb{R}^{n_{1}\times
n_{2}}\rightarrow\mathbb{R}^{mm_{1}m_{2}}$ and
$\mathcal{A}^{\star}:\mathbb{R}^{mm_{1}m_{2}}\rightarrow\mathbb{R}^{n_{1}\times
n_{2}}$ as its adjoint operator. In $\mathcal{F}^{(1)}$, we have
$\mathcal{A}\left(\mathbf{X}\right)=\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)$.
Then the Lagrangian for this problem is of the form

$\mathcal{L}(\mathbf{X},\bm{y})=\tau\left\|\mathbf{X}\right\|_{\star}+\frac{1}{2}\left\|\mathbf{X}\right\|^{2}_{\mathrm{F}}+\bm{y}^{\top}\left(\mathbf{t}-\mathcal{A}(\mathbf{X})\right),$
(24)

where $\bm{y}$ is the Lagrangian multiplier and
$\mathbf{t}=\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}\right)$.
The Karush-Kuhn-Tucker (KKT) conditions dictate that when dealing with
inequality constraints, the Lagrange multiplier must be nonnegative, i.e.,
$\bm{y}\succeq 0$. Drawing inspiration from Uzawa’s method [8, Section 3.2],
we introduce slight modifications to the SVT algorithm to accommodate the
inequality constraints and ensure satisfaction of $\bm{y}\succeq 0$ at every
iteration $k$. The resulting expression is

$\left\\{\begin{array}[]{l}\mathbf{X}^{(k)}=\arg\min\mathcal{L}\left(\mathbf{X},\bm{y}^{(k-1)}\right),\\\
\bm{y}^{(k)}=\left(\bm{y}^{(k-1)}+\delta_{k}\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)\right)^{+},\end{array}\right.$
(25)

where $\\{\delta_{k}\\}$ are positive step sizes. If we consider the singular
value decomposition (SVD) of $\mathbf{X}$ as
$\mathbf{X}=\mathbf{U}\bm{\Sigma}\mathbf{V}^{\top}$ and $\\{\sigma_{i}\\}$ as
its singular values, the first step in (25) can be easily solved by using the
singular value shrinkage operator comprehensively investigated in [8, 62]
which applies the partial SVD to achieve the low-rank matrix structure as
$\mathcal{D}_{\tau}(\mathbf{X})=\mathbf{U}\mathcal{D}_{\tau}(\bm{\Sigma})\mathbf{V}^{\top},\leavevmode\nobreak\
\mathcal{D}_{\tau}(\bm{\Sigma})=\operatorname{diag}\left(\left(\sigma_{i}-\tau\right)^{+}\right)$,
where $\tau\geq 0$ is the predefined threshold. The SVT algorithm is a popular
approach for matrix sensing (here matrix completion), where the partial SVD
can be numerically calculated using Krylov subspace methods (e.g. Lanczos
algorithm) [64]. Consequently, the update process (25) is rewritten as

$\left\\{\begin{array}[]{l}\mathbf{X}^{(k)}=\mathcal{D}_{\tau}\left(\mathcal{A}^{\star}\left(\bm{y}^{(k-1)}\right)\right),\\\
\bm{y}^{(k)}=\left(\bm{y}^{(k-1)}+\delta_{k}\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)\right)^{+}.\end{array}\right.$
(26)

For the noisy scenario (23), the Lagrangian formulation for
$\mathcal{F}^{(2)}$ is given by

$\displaystyle\mathcal{L}^{n}(\mathbf{X},\bm{y}_{1})=\tau\left\|\mathbf{X}\right\|_{\star}+\frac{1}{2}\left\|\mathbf{X}\right\|^{2}_{\mathrm{F}}+\bm{y}^{\top}_{1}\left(\left(\mathbf{t}-\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)\right)^{+}-\bm{\upsigma}_{z}\right),$
(27)

where $\bm{y}_{1}$ is the Lagrangian multiplier parameter. We call this
algorithm _OB-SVT-I_.

As outlined in Subsection II-C, incorporating the noisy inequality constraint
(19) can be achieved by only considering
$\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\preceq\mathbf{t}$
at each iteration $k$. Otherwise, i.e.,
$\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)\succeq\mathbf{t}$,
there is no need to update the Lagrangian multiplier $\bm{y}_{1}$. As a
result, the operator $(\cdot)^{+}$ can be easily removed from (27):

$\displaystyle\mathcal{L}^{n}(\mathbf{X},\bm{y})=\tau\left\|\mathbf{X}\right\|_{\star}+\frac{1}{2}\left\|\mathbf{X}\right\|^{2}_{\mathrm{F}}+\bm{y}^{\top}_{1}\left(\mathbf{t}-\bm{\upsigma}_{z}-\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)\right).$
(28)

Denote $\mathbf{t}_{1}=\mathbf{t}-\bm{\upsigma}_{z}$. According to Uzawa’s
method, the following update process is proposed to address
$\mathcal{F}^{(2)}$:

$\left\\{\begin{array}[]{l}\mathbf{X}^{(k)}=\mathcal{D}_{\tau}\left(\mathcal{A}^{\star}\left(\bm{y}_{1}^{(k-1)}\right)\right),\\\
\bm{g}^{(k)}=\left(\mathbf{t}_{1}-\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}\mathbb{1}_{\left(\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\preceq\mathbf{t}\right)},\\\
\bm{y}^{(k)}_{1}=\left(\bm{y}^{(k-1)}_{1}+\delta_{k}\bm{g}^{(k)}\right)^{+}.\end{array}\right.$
(29)

###  III-B OB-SVT-II

By drawing inspiration from the Kaczmarz algorithm [53], where inequality
constraints are represented by

$\left(\mathbf{t}-\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)\right)^{+}=0,$
(30)

we can reframe the Lagrangian formulation associated with $\mathcal{F}^{(1)}$
as follows:

$\mathcal{L}^{(1)}(\mathbf{X},\bm{y})=\tau\left\|\mathbf{X}\right\|_{\star}+\frac{1}{2}\left\|\mathbf{X}\right\|^{2}_{\mathrm{F}}+\bm{y}^{\top}\left(\mathbf{t}-\mathcal{A}(\mathbf{X})\right)^{+}.$
(31)

The intriguing aspect of this new formulation is that the inequality
constraint behaves akin to an equality constraint, removing the necessity for
a nonnegative $\mathbf{y}$. As a result, the algorithm designed to address
this Lagrangian problem may be expressed as follows:

$\left\\{\begin{array}[]{l}\mathbf{X}^{(k)}=\mathcal{D}_{\tau}\left(\mathcal{A}^{\star}\left(\bm{y}^{(k-1)}\right)\right),\\\
\bm{y}^{(k)}=\bm{y}^{(k-1)}+\delta_{k}\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+}.\end{array}\right.$
(32)

This algorithm is named _OB-SVT-II_ , bears resemblance to both the least
squares and Kaczmarz algorithms (with an identity sketch matrix) [65, 53],
with the additional inclusion of a nuclear norm constraint in each iteration.

###  III-C Randomized OB-SVT

The key advantage of randomized algorithms over regular algorithms lies in
their ability to operate on batches or even single measurements per iteration,
rather than requiring the entire set of measurements. This characteristic
makes them highly efficient for practical applications. In particular,
considering the RKA as an example, it only requires information from one
measurement per iteration. By employing the RKA instead of the full matrix
version, we significantly reduce the computational complexity from matrix-
vector multiplication to vector-vector multiplication in each algorithmic
iteration. This reduction in complexity greatly enhances the efficiency of
this algorithm in large-scale problems such as MC.

The new formulation of one-bit MC in (32) opens up avenues for exploring the
feasibility of solving the following Lagrangian problem when only partial
measurements per iteration are utilized:

$\mathcal{L}^{(2)}(\mathbf{X},\bm{y})=\tau\left\|\mathbf{X}\right\|_{\star}+\frac{1}{2}\left\|\mathbf{X}\right\|^{2}_{\mathrm{F}}+\bm{y}^{\top}_{s}\left(\mathbf{S}\mathbf{t}-\mathbf{S}\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)\right)^{+},$
(33)

where $\mathbf{S}\in\mathbb{R}^{s\times mm_{1}m_{2}}$ is a sketch matrix with
$s<m_{1}m_{2}$ as the sketch length, which randomly selects a row or a block
of matrix $\bm{\mathcal{B}}\in\mathbb{R}^{mm_{1}m_{2}\times n_{1}n_{2}}$. One
well-known example of a sketch matrix is the sparse Gaussian matrix, which
selects a block of the matrix using the following definition [66]:

$\mathbf{S}^{\top}=\left[\begin{array}[]{c|c|c}\mathbf{0}_{s\times
p}&\mathbf{G}&\mathbf{0}_{s\times((m-1)m_{1}m_{2}-p)}\end{array}\right]^{\top},$
(34)

where $\mathbf{G}$ is a $s\times m_{1}m_{2}$ Gaussian matrix, whose entries
are i.i.d. following the distribution $\mathcal{N}\left(0,1\right)$, and
$p=m_{1}m_{2}\alpha,\leavevmode\nobreak\
\alpha\in\left\\{1,\cdots,m-1\right\\}$. Assume $\bm{y}_{s}\in\mathbb{R}^{s}$
and
$\mathcal{M}\left(\mathbf{X}\right)=\mathbf{S}\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)$.
Then the _randomized OB-SVT_ is written as

$\left\\{\begin{array}[]{l}\mathbf{X}^{(k)}=\mathcal{D}_{\tau}\left(\mathcal{M}^{\star}\left(\bm{y}^{(k-1)}_{s}\right)\right),\\\
\bm{y}^{(k)}_{s}=\bm{y}^{(k-1)}_{s}+\delta_{k}\left(\mathbf{S}\mathbf{t}-\mathcal{M}\left(\mathbf{X}^{(k)}\right)\right)^{+}.\end{array}\right.$
(35)

##  IV Adaptive Time-Varying Threshold Design With Bregman Iterative Method

In this section, we will employ the concept of _Bregman iterative method_ to
devise a time-varying threshold that enhances the performance of one-bit low-
rank matrix sensing. We will begin by presenting an overview of the Bregman
iterative method.

Define a convex function $g(\cdot)$, the Bregman distance of the vector
$\mathbf{u}$ from the vector $\mathbf{v}$ is defined as

$D_{g}^{\mathbf{p}}(\mathbf{u},\mathbf{v})\triangleq
g(\mathbf{u})-g(\mathbf{v})-\mathbf{p}^{\top}(\mathbf{u}-\mathbf{v}),$ (36)

where $\mathbf{p}\in\partial g(\mathbf{v})$ is some subgradient in the
subdifferential of $g$ at the point $\mathbf{v}$. Authors of [63] proposed
solving the $\ell_{1}$ minimization problem for
$\mathbf{A}\mathbf{x}=\mathbf{b}$, by replacing
$g(\mathbf{x})=\|\mathbf{x}\|_{1}$ with its Bregman distance at each iteration
as follows:

$\left\\{\begin{array}[]{l}\mathbf{x}^{(k+1)}=\arg\min
D_{g}^{\mathbf{p}^{(k)}}\left(\mathbf{x},\mathbf{x}^{(k)}\right)+\frac{1}{2}\left\|\mathbf{A}\mathbf{x}-\mathbf{b}\right\|_{2}^{2},\\\
\mathbf{p}^{(k+1)}=\mathbf{p}^{(k)}+\mathbf{A}^{\top}\left(\mathbf{b}-\mathbf{A}\mathbf{x}^{(k+1)}\right),\end{array}\right.$
(37)

which is interestingly equivalent to

$\left\\{\begin{array}[]{l}\mathbf{b}^{(k+1)}=\mathbf{b}+\left(\mathbf{b}^{(k)}-\mathbf{A}\mathbf{x}^{(k)}\right),\\\
\mathbf{x}^{(k+1)}=\arg\min\leavevmode\nobreak\
\|\mathbf{x}\|_{1}+\frac{1}{2}\left\|\mathbf{A}\mathbf{x}-\mathbf{b}^{(k+1)}\right\|_{2}^{2}.\end{array}\right.$
(38)

This approach has been extended to the low-rank matrix sensing and matrix
completion in [62] as

$\left\\{\begin{array}[]{l}\mathbf{b}^{(k+1)}=\mathbf{b}+\left(\mathbf{b}^{(k)}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right),\\\
\mathbf{X}^{(k+1)}=\arg\min\tau\|\mathbf{X}\|_{\star}+\frac{1}{2}\left\|\mathcal{A}(\mathbf{X})-\mathbf{b}^{(k+1)}\right\|_{2}^{2}.\end{array}\right.$
(39)

The study conducted in [62] demonstrated that by utilizing the Bregman
iterative method in conjunction with the nuclear norm minimization problem,
both the convergence rate and accuracy of the algorithm can be improved.

To tailor the Bregman iterative method to the one-bit MC problem, it appears
sufficient to incorporate the impact of inequality constraints, i.e.,
$\mathcal{A}\left(\mathbf{X}\right)\succeq\mathbf{b}$, in the following
manner:

$\left\\{\begin{array}[]{l}\mathbf{b}^{(k+1)}=\mathbf{b}+\left(\mathbf{b}^{(k)}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+},\\\
\mathbf{X}^{(k+1)}=\arg\min\tau\|\mathbf{X}\|_{\star}+\frac{1}{2}\left\|\left(\mathbf{b}^{(k+1)}-\mathcal{A}\left(\mathbf{X}\right)\right)^{+}\right\|_{2}^{2}.\end{array}\right.$
(40)

Also as discussed in [62], the second step of (40) can be tackled by the SVT
algorithm. Consequently, the Bregman iterative method for the one-bit MC
problem is formulated as

$\left\\{\begin{array}[]{l}\mathbf{t}^{(k+1)}=\mathbf{t}+\left(\mathbf{t}^{(k)}-\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+},\\\
\mathbf{X}^{(k+1)}=\arg\min\tau\|\mathbf{X}\|_{\star}+\frac{1}{2}\left\|\left(\mathbf{t}^{(k+1)}-\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)\right)^{+}\right\|_{2}^{2}.\end{array}\right.$
(41)

where $\tau$ is a predefined threshold and
$\mathbf{t}^{(k)}=\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}^{(k)}\right)$.
After setting the current time-varying threshold as fixed, we can obtain
$\mathbf{t}=\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}\right)$
and subsequently update the threshold at each iteration $k$ using the first
step of (41). This process is repeated until
$\left\|\mathbf{t}^{(k+1)}-\mathbf{t}^{(t)}\right\|_{2}\leq\varepsilon$, where
$\varepsilon$ is a positive constant value. Note that the second step of (41)
is tackled by the SVT with inequality constraints proposed in Section III.

##  V Theoretical Discussion

Our focus is on the possibility of performing one-bit sensing for matrix
completion while establishing an upper bound on the recovery error, regardless
of the specific algorithm employed. Previous works, such as [47, 48], have
provided theoretical guarantees by considering the distribution of noise and
the KL-divergence for the regularized MLE problem. However, in this paper, we
aim to derive a more general approach that can be applied to one-bit MC,
irrespective of the noise distribution. We will employ the _general
Hoeffding’s inequality_ [67, Theorem 2.6.2] to determine the required number
of dithering sequences that ensure a successful recovery performance.
Subsequently, we delve into the convergence analysis of the proposed OB-SVT
algorithms in both noisy and noiseless scenarios.

###  V-A One-Bit MC Theoretical Guarantees

Sensing and reconstructing matrices from a limited number of noisy entries is
a captivating and ongoing area of research that has garnered significant
attention. In the work presented by the authors in [68], noisy matrix
completion is formulated as a nuclear norm minimization problem. This approach
has led to the derivation of rigorous theoretical guarantees, further
advancing the understanding and development of this intriguing field. Consider
the noisy measurements as follows:

$X^{(n)}_{i,j}=X_{i,j}+Z_{i,j},\quad(i,j)\in\Omega,$ (42)

where $Z_{i,j}$ is the additive noise with variance $\sigma^{2}_{z}$.

Extensive investigations conducted in [68, 8] have demonstrated that matrix
completion with noise can be formulated as a nuclear norm minimization problem
as follows:

$\displaystyle\underset{\mathbf{X}}{\textrm{minimize}}\quad\left\|\mathbf{X}\right\|_{\star}$
(43) $\displaystyle\text{subject
to}\quad\left\|\mathcal{P}_{\Omega}(\mathbf{X}-\mathbf{X}^{(n)})\right\|_{F}\leq\delta,$

where $\mathbf{X}^{(n)}$ is the noisy matrix and $\delta$ presents the effect
of noise. Drawing inspiration from the theoretical guarantees of noisy MC, we
examine the problem of quantized MC, specifically focusing on the case of one-
bit MC. Let us assume that
$\mathcal{P}_{\Omega}\left(\mathbf{Y}\right)=Q\left(\mathcal{P}_{\Omega}\left(\mathbf{X}\right)\right)$
represents a scalar quantization of known entries of low-rank matrix
$\mathbf{X}$. Consequently, the quantized measurements can be expressed as
follows:

$\mathcal{P}_{\Omega}\left(\mathbf{Y}\right)=\mathcal{P}_{\Omega}\left(\mathbf{X}\right)+\mathbf{N},$
(44)

where the matrix $\mathbf{N}\in\mathbb{R}^{m_{1}\times m_{2}}$ presents the
effect of quantization as the additive noise matrix. Therefore, the nuclear
norm minimization problem associated with the quantized MC is given by

$\displaystyle\underset{\mathbf{X}}{\textrm{minimize}}\quad\left\|\mathbf{X}\right\|_{\star}$
(45) $\displaystyle\text{subject
to}\quad\left\|\mathcal{P}_{\Omega}(\mathbf{X}-\mathbf{Y})\right\|_{F}\leq q,$

where the parameter $q$ denotes the impact of the quantization process.

Drawing inspiration from [68, Theorem 7] in the context of noisy MC problem,
we can derive an upper bound for the Frobenius norm error in one-bit MC
through the nuclear norm minimization problem. This result is stated in the
following theorem:

######  Theorem 1.

Assume $\left\\{\delta_{\ell}\right\\}^{m}_{\ell=1}$ to be the upper bounds on
the differences between the entries of low-rank matrix
$\mathbf{X}\in\mathbb{R}^{n_{1}\times n_{2}}$ and thresholds in the one-bit
sensing, for the uniform set $\Omega$ and $q$ to be a parameter presenting the
effect of quantization. Define $m$ as the number of time-varying threshold
sequences, and $m^{\prime}=m_{1}m_{2}$ as the cardinality of the set $\Omega$.
The error norm $\left\|\mathbf{X}-\bar{\mathbf{X}}\right\|_{\mathrm{F}}$
between the unknown matrix $\mathbf{X}\in\mathcal{F}$ and the reconstructed
matrix $\bar{\mathbf{X}}\in\mathcal{F}$ by one-bit MC is bounded with
probability at least $1-\left(\max\left(n_{1},n_{2}\right)\right)^{-3}$ as

$\left\|\mathbf{X}-\bar{\mathbf{X}}\right\|_{\mathrm{F}}\leq
4\sqrt{\frac{\left(2n_{1}n_{2}+m^{\prime}\right)\min\left(n_{1},n_{2}\right)}{m^{\prime}}}q+2q,$
(46)

where $q=\frac{\sum^{m}_{\ell=1}\delta_{\ell}}{m}$.

###### Proof:

The linear feasibility of one-bit MC is given by

$\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}\right)\succeq\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}\right),$
(47)

which may be rewritten for each threshold sequence as

$\bm{\Omega}^{(\ell)}\operatorname{vec}\left(\mathcal{P}_{\Omega}\left(\mathbf{X}\right)\right)\succeq\bm{\Omega}^{(\ell)}\operatorname{vec}\left(\mathcal{P}_{\Omega}\left(\bm{\mathcal{T}}^{(\ell)}\right)\right),\quad\ell\in[m].$
(48)

The set of inequalities in (48) can be expressed as the following system of
equations, taking into account the slack parameters
$\left\\{\bm{\mathcal{E}}_{\ell}\right\\}^{m}_{\ell=1}$:

$\bm{\Omega}^{(\ell)}\operatorname{vec}\left(\mathcal{P}_{\Omega}\left(\mathbf{X}\right)\right)=\bm{\Omega}^{(\ell)}\operatorname{vec}\left(\mathcal{P}_{\Omega}\left(\bm{\mathcal{T}}^{(\ell)}\right)\right)+\bm{\mathcal{E}}_{\ell},\quad\ell\in[m],$
(49)

or equivalently,
$\operatorname{vec}\left(\mathcal{P}_{\Omega}\left(\mathbf{X}\right)\right)=\operatorname{vec}\left(\mathcal{P}_{\Omega}\left(\bm{\mathcal{T}}^{(\ell)}\right)\right)+\mathbf{n}^{(\ell)},\leavevmode\nobreak\
\ell\in[m]$, where
$\left\\{\mathbf{n}^{(\ell)}=\bm{\Omega}^{(\ell)}\bm{\mathcal{E}}_{\ell}\right\\}^{m}_{\ell=1}$
show the differences between the measurements and the dithering sequences.
Hence, it is sufficient to impose the following norm constraints on the
nuclear norm minimization problem in order to represent the one-bit MC:

$\left\|\bm{\Omega}^{(\ell)}\operatorname{vec}\left(\mathcal{P}_{\Omega}\left(\mathbf{X}\right)\right)-\bm{\Omega}^{(\ell)}\operatorname{vec}\left(\mathcal{P}_{\Omega}\left(\bm{\mathcal{T}}^{(\ell)}\right)\right)\right\|_{2}\leq\delta_{\ell},\quad\ell\in[m].$
(50)

As the matrices $\left\\{\bm{\Omega}^{(\ell)}\right\\}^{m}_{\ell=1}$ consist
of sign data, they can be readily eliminated in (50). Therefore, the
parameters $\left\\{\delta_{\ell}\right\\}^{m}_{\ell=1}$ simply represent the
upper bounds on the differences between the measurements and thresholds in the
one-bit sensing, i.e.,
$\left\|\operatorname{vec}\left(\mathcal{P}_{\Omega}\left(\mathbf{X}\right)\right)-\operatorname{vec}\left(\mathcal{P}_{\Omega}\left(\bm{\mathcal{T}}^{(\ell)}\right)\right)\right\|_{2}\leq\delta_{\ell}$
for all $\ell\in[m]$. To observe all these constraints collectively, we can
simply sum over the threshold sequences, and according to the inequality
$\left\|\sum^{m}_{i}\mathbf{x}_{i}\right\|_{2}\leq\sum^{m}_{i=1}\left\|\mathbf{x}_{i}\right\|_{2}$
for $\left\\{\mathbf{x}_{i}\right\\}^{m}_{i=1}$ in the Hilbert space, which
straightforwardly verifies that it results in the following constraint:

$\displaystyle\left\|m\mathcal{P}_{\Omega}\left(\mathbf{X}\right)-\mathcal{P}_{\Omega}\left(\sum^{m}_{\ell=1}\bm{\mathcal{T}}^{(\ell)}\right)\right\|_{\mathrm{F}}$
$\displaystyle\leq\sum^{m}_{\ell=1}\delta_{\ell},$ (51)
$\displaystyle\left\|\mathcal{P}_{\Omega}\left(\mathbf{X}\right)-\mathcal{P}_{\Omega}\left(\frac{\sum^{m}_{\ell=1}\bm{\mathcal{T}}^{(\ell)}}{m}\right)\right\|_{\mathrm{F}}$
$\displaystyle\leq\frac{\sum^{m}_{\ell=1}\delta_{\ell}}{m}=q.$

The resulting constraint in (51) demonstrates that the dithered one-bit MC is
equivalent to the noisy matrix completion problem, with the distinction that
instead of noisy measurements, we utilize the average value of the thresholds
as our available information. Therefore, it suffices to apply the noisy matrix
completion theorem [68, Theorem 7] to our problem, which substantiates the
Theorem 1. ∎

It is worth emphasizing that, as per Theorem 1, the crucial information that
enables us to utilize the noisy matrix completion theorem for our theoretical
guarantees is the information derived from the dithering process. This
underscores the significance of employing dithering in our approach. In [6,
Theorem 2.3] and more generally in [69, Theorem 1.2] (without any assumption
on the singular values of $\mathbf{X}$), a comprehensive analysis was
conducted to determine the necessary number of measurements in matrix
completion (denoted as $m^{\prime}=m_{1}m_{2}$) to ensure that an unknown low-
rank matrix satisfies the incoherence properties. These incoherence properties
play a crucial role in guaranteeing the recovery of the low-rank matrix in
matrix completion through the solution of nuclear norm minimization.

Note that the sign preservation in our work is equivalent to the solution
provided by a linear feasibility solver, denoted as $\bar{\mathbf{X}}$,
satisfying all the given inequalities, meaning
$\bar{\mathbf{X}}\in\mathcal{F}$.

If each inequality constraint of one-bit MC incorporates a perturbation or
noise effect, denoted as
$\left\\{\mathbf{E}_{{}_{\ell}}\right\\}_{\ell=1}^{m}$, the inequality
constraint in (51) can be reformulated as follows:

$\displaystyle\left\|\mathcal{P}_{\Omega}\left(\mathbf{X}\right)-\mathcal{P}_{\Omega}\left(\frac{\sum^{m}_{\ell=1}\bm{\mathcal{T}}^{(\ell)}}{m}\right)-\frac{\sum^{m}_{\ell=1}\mathbf{E}_{{}_{\ell}}}{m}\right\|_{\mathrm{F}}$
(52)
$\displaystyle\leq\left\|\mathcal{P}_{\Omega}\left(\mathbf{X}\right)-\mathcal{P}_{\Omega}\left(\frac{\sum^{m}_{\ell=1}\bm{\mathcal{T}}^{(\ell)}}{m}\right)\right\|_{\mathrm{F}}+\left\|\frac{\sum^{m}_{\ell=1}\mathbf{E}_{{}_{\ell}}}{m}\right\|_{\mathrm{F}}\leq
q+\epsilon,$

where $\epsilon\geq 0$ is the noise effect which leads to an increase in the
upper bound of error recovery defined in Theorem 1.

In certain systems, when the dynamic range (DR) of the input signal is known,
it is possible to design threshold values that closely align with the
measurements, resulting in smaller values of
$\left\\{\delta_{\ell}\right\\}^{m}_{\ell=1}$. A notable example of such a
scheme is UNO sampling, proposed in [46], where the knowledge of input
signal’s DR allows for the design of thresholds with reduced
$\left\\{\delta_{\ell}\right\\}^{m}_{\ell=1}$. However, in many practical
scenarios, where information about the DR is unavailable, selecting an
appropriate value for $\left\\{\delta_{\ell}\right\\}^{m}_{\ell=1}$ becomes
challenging.

In order to offer a more profound understanding of the upper bound elucidated
within (51), we define the distance between the threshold and the signal as
follows:

$\displaystyle
d^{(\ell)}_{i,j}=\left|X_{i,j}-\tau^{(\ell)}_{i,j}\right|,\quad(i,j)\in\Omega,\leavevmode\nobreak\
\ell\in[m].$ (53)

It is easy to observe that by reducing the distances between the measurements
and the constraint-associated hyperplanes in (7) presented by thresholds, the
possibility of _capturing_ the optimal point is increased. For a specific
number of one-bit samples, when
$\operatorname{vol}\left(\mathcal{P}_{\mathbf{X}}\right)$ is reduced, the
average of distances is diminished as well [44]. This average of distances can
be written as:

$\displaystyle
T_{\mathrm{ave}}=\frac{1}{mm^{\prime}}\sum^{mm^{\prime}}_{i,j,\ell=1}d^{(\ell)}_{i,j},\quad(i,j)\in\Omega,\leavevmode\nobreak\
\ell\in[m],$ (54)

where $m$ is the number of time-varying threshold sequences and
$m^{\prime}=m_{1}m_{2}$. It is straightforward to verify that
$T_{\mathrm{ave}}$ can be rewritten as

$T_{\mathrm{ave}}=\frac{1}{mm^{\prime}}\sum^{m}_{\ell=1}\left\|\operatorname{vec}\left(\mathcal{P}_{\Omega}\left(\mathbf{X}\right)\right)-\operatorname{vec}\left(\mathcal{P}_{\Omega}\left(\bm{\mathcal{T}}^{(\ell)}\right)\right)\right\|_{1}.$
(55)

Given that the $\ell_{1}$-norm is consistently greater than the
$\ell_{2}$-norm (or Frobenius norm in the matrix version), we can write

$\displaystyle\left\|\mathcal{P}_{\Omega}\left(\mathbf{X}\right)-\mathcal{P}_{\Omega}\left(\frac{\sum^{m}_{\ell=1}\bm{\mathcal{T}}^{(\ell)}}{m}\right)\right\|_{\mathrm{F}}$
$\displaystyle=$ (56)
$\displaystyle\frac{1}{m}\left\|m\mathcal{P}_{\Omega}\left(\mathbf{X}\right)-\mathcal{P}_{\Omega}\left(\sum^{m}_{\ell=1}\bm{\mathcal{T}}^{(\ell)}\right)\right\|_{\mathrm{F}}$
$\displaystyle\leq m^{\prime}T_{\mathrm{ave}}.$

Therefore, based on the upper bounds in (51) and (56), one can set
$q=m^{\prime}T_{\mathrm{ave}}$ which equivalently informs that by establishing
a bound on $T_{\mathrm{ave}}$, the left-hand side of (51) can be bounded, as
well. The following theorem provides the required number of time-varying
sampling threshold sequences $m$ in order to achieve
$T_{\mathrm{ave}}\leq\alpha$ with high probability:

######  Theorem 2.

Denote $\mathcal{F}\subseteq\mathbb{R}^{n_{1}\times n_{2}}$ as the one-bit MC
polyhedron defined in (13). Let $m^{\prime}=m_{1}m_{2}$ denote the cardinality
of the set $\Omega$ and $m$ be the number of time-varying sampling threshold
sequences. Assume the distances
$\left\\{d^{(\ell)}_{i,j}\right\\}_{i,j,\ell=1}^{mm^{\prime}}$ defined in
(53), between the desired matrix $\mathbf{X}\in\mathcal{F}$ and the
hyperplanes of the one-bit MC polyhedron (13) are independent sub-gaussian
random variables with $\mathbb{E}\left\\{T_{\mathrm{ave}}\right\\}=\mu$.
Consider a fixed $0<\eta<1$ and a positive constant $C$. For a positive
constant $\delta=\alpha-\mu$, we have $T_{\mathrm{ave}}\leq\alpha$ with a
probability exceeding $1-\eta$ when the number of time-varying sampling
threshold sequences $m$ satisfies

$m\geq
C\delta^{-2}\log\left(\frac{en_{1}n_{2}}{m^{\prime}\eta^{\frac{1}{m^{\prime}}}}\right).$
(57)

The complete proof of Theorem 2 can be found in Appendix A. Based on Theorem
2, when the number of dithering sequences satisfies (57), the hyperplanes of
the one-bit MC polyhedron (13) create a solution space such that
$\left\|\mathbf{X}-\bar{\mathbf{X}}\right\|_{\mathrm{F}}\leq\rho$ for a
positive constant $\rho$ with high probability. As the number of dithering
sequences $m$ grows large, the likelihood of capturing the optimal solution in
one-bit MC increases. This can be confirmed by referring to Theorem 1, where a
smaller value of $q$ (which can be bounded using Theorem 2) leads to a
decreased upper bound on error recovery.

As per Theorem 2, we explore the implications when the statistical
characteristics of the input measurements align closely with those of the
dithering sequences. This investigation will provide insights into making more
informed choices for the dithering scenario, ultimately enhancing the
performance of signal reconstruction. In the subsequent claim, we present our
discovered insights concerning this subject:

######  Claim 1.

Within the one-bit MC problem, when the inputs provided to the one-bit ADCs
stem from a Gaussian distribution, the utilization of Gaussian dithering
results in enhanced signal reconstruction performance with high probability.
This principle remains consistent when the input measurements are derived from
a Uniform distribution, coupled with the selection of Uniform dithering.

The substantiation of Claim 1 is detailed in Appendix B. Claim 1 serves as a
bridge between Theorems 1 and 2, facilitating the selection of an optimal
sampling dithering strategy for one-bit sensing. This choice leads to improved
signal reconstruction performance and a reduced upper bound for the one-bit MC
problem.

###  V-B Convergence Analysis of Proposed Algorithms

The OB-SVT-I algorithm is proven to converge according to the following
theorem:

######  Theorem 3.

Assume $m$ to be the number of time-varying threshold sequences and
$\delta_{k}$ be the step size. The OB-SVT-I algorithm, employed to solve the
nuclear norm minimization problem $\mathcal{F}^{(1)}$, exhibits convergence as
follows:

$\left\|\bm{y}^{(k)}-\bm{y}^{\star}\right\|^{2}_{2}\leq\left\|\bm{y}^{(k-1)}-\bm{y}^{\star}\right\|^{2}_{2}-\left(2\delta_{k}-\delta^{2}_{k}m\right)\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}},$
(58)

where $\left(2\delta_{k}-\delta^{2}_{k}m\right)$ is positive.

We thoroughly study the proof of Theorem 3 in Appendix C. Based on the
aforementioned theorem, the step size $\delta_{k}$ should satisfy
$0\leq\delta_{k}<2/m$. This condition implies that the error between the
variable and its desired value is a non-increasing function with respect to
the iteration, providing evidence of the convergence of OB-SVT-I.

The convergence of the OB-SVT-II algorithm is examined through the following
theorem. By establishing a convergence rate based on this theorem, we can make
a meaningful comparison of its performance relative to that of the OB-SVT-I
algorithm.

######  Theorem 4.

Let $m$ denote the number of time-varying threshold sequences, and
$\delta_{k}$ represent the step size. The OB-SVT-II algorithm, utilized for
solving the nuclear norm minimization problem $\mathcal{F}^{(1)}$,
demonstrates convergence as follows:

$\left\|\bm{y}^{(k)}-\bm{y}^{\star}\right\|^{2}_{2}\leq\left\|\bm{y}^{(k-1)}-\bm{y}^{\star}\right\|^{2}_{2}-m\delta^{2}_{k}\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}.$
(59)

The detailed proof of Theorem 4 is available in Appendix D. As mentioned in
Theorem 3, to ensure that OB-SVT-I converges, the term
$2\delta_{k}-m\delta_{k}^{2}$ should be positive which implies that the step
size $\delta_{k}$ must be lower than $2/m$. However, Theorem 4 for OB-SVT-II
demonstrates that the choice of step size has more flexibility since the term
$m\delta_{k}^{2}$ is always a positive value. Moreover, it is evident from
(59) that by increasing the number of time-varying thresholds $m$ with a fixed
step size $\delta_{k}$, the convergence of OB-SVT-II will be accelerated,
which aligns with our goal. We will empirically examine and analyze the
performance of both algorithms, demonstrating that this simple difference in
step size enhances the convergence and performance of OB-SVT-II compared to
OB-SVT-I.

In the OB-SVT-II algorithm, when we employ the randomized sketch matrix to
select a subset of one-bit data, the resulting variant is known as randomized
OB-SVT. We can derive the convergence rate of the randomized OB-SVT algorithm
as follows:

######  Theorem 5.

Assume $m$ to be the number of time-varying threshold sequences and
$\delta_{k}$ be the step size. Let $\mathbf{S}\in\mathbb{R}^{s\times
mm_{1}m_{2}}$ defined in (34) be the sparse Gaussian sketch matrix and
$\alpha=c\sqrt{\log s}$ for a positive constant $c$. The randomized OB-SVT
algorithm with the sketch matrix $\mathbf{S}$, employed to solve the nuclear
norm minimization problem $\mathcal{F}^{(1)}$, exhibits convergence as
follows:

$\mathbb{E}_{\mathbf{S}}\left\\{\left\|\bm{y}^{(k)}-\bm{y}^{\star}\right\|^{2}_{2}\right\\}\leq\left\|\bm{y}^{(k-1)}-\bm{y}^{\star}\right\|^{2}_{2}-\alpha^{2}\delta^{2}_{k}\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}.$
(60)

The complete proof of Theorem 5 is presented in Appendix E. The connection
between the convergence of the Lagrangian multiplier $\bm{y}^{(k)}$ and the
convergence of the solution $\mathbf{X}^{(k)}$ remains consistent across all
suggested algorithms, as expressed in the following lemma:

######  Lemma 1.

Given that $m$ represents the number of time-varying threshold sequences, the
solution attained by OB-SVT algorithms converges towards the optimum, as
described by the following relationship:

$\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}\leq\frac{1}{m}\left\|\bm{y}^{(k-1)}-\bm{y}^{\star}\right\|^{2}_{2},$
(61)

where the Lagrangian multipliers converge according to Theorems 3-5.

We extensively provide the proof of Lemma 1 in Appendix F. The mentioned lemma
reaffirms that increasing the quantity of time-varying threshold sequences
accelerates the convergence rate of OB-SVT algorithms.

###  V-C Robustness of Proposed Algorithms in the Presence of Noise

In this study, we examine the impact of noise or perturbations on the
performance of the proposed OB-SVT algorithms. We apply these algorithms to
the problem of noisy one-bit MC and explore the conditions under which they
still converge and provide satisfactory recovery performance. This
investigation aims to demonstrate the effectiveness of the proposed
algorithms, even in the presence of noise at specific levels. By analyzing the
performance of our proposed algorithms in the presence of noise, we gain
insights into the robustness and reliability of them in practical scenarios.

We account for noise by introducing an additive noise matrix applied to the
solution $\mathbf{X}^{\star}$. Since $\mathbf{X}^{\star}$ is not a solution in
the noiseless case, incorporating a noise as an additive matrix allows us to
establish a connection to the noiseless scenario.

In the following proposition, we establish the sufficient conditions on the
_pre-quantization error_ $\mathbf{N}\in\mathbb{R}^{n_{1}\times n_{2}}$ to
ensure the convergence of the proposed algorithms:

(a)  (b)

(c)

(d)  (e)

(f)

Figure 1: (a) Comparison between OB-SVT-I, OB-SVT-II and the MLE [47] for
measurements corrupted by Gaussian noise in terms of the relative error when
reconstructing a $500\times 500$ matrix $\mathbf{X}$ with the rank $r=10$. (b)
Comparison between OB-SVT-I, OB-SVT-II and the MLE for measurements corrupted
by Poisson noise in terms of the relative error. (c) Comparison different
dithering schemes, Gaussian, Uniform and discrete with quantization levels
$M=10$ and $M=100$, for the one-bit MC with Gaussian measurements corrupted by
Gaussian noise. (d) Comparison between Uniform dithering and Gaussian
dithering schemes for the input measurements generated based on Uniform
distribution. (e) The performance of randomized OB-SVT algorithm for the
different values of $\beta=s/m^{\prime}$ and $\alpha=m^{\prime}/n_{1}n_{2}$.
(f) Enhancement of the reconstruction accuracy via the OB-SVT method as the
number of dithering sequences grows large and comparison between the
performance of Gaussian dithering and the proposed adaptive dithering scheme.

######  Proposition 1.

Let $m$ denote the number of time-varying threshold sequences, and
$\delta_{k}$ represent the step size. For the noisy one-bit MC problem with
$\mathbf{N}\in\mathbb{R}^{n_{1}\times n_{2}}$ representing the pre-
quantization error and $I$ signifying the total count of iterations at which
the algorithm achieves complete convergence, the convergence of proposed
algorithms is contingent upon the noise satisfying the following condition:

$\left\|\mathbf{N}\right\|^{2}_{\mathrm{F}}\leq\frac{1}{2}\left\|\mathbf{X}^{(I)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}.$
(62)

A comprehensive demonstration of the proof for Proposition 1 can be found in
Appendix G. Irrespective of whether $\mathbf{N}$ is deterministic or random,
it is imperative for their second norm to adhere to the previously stated
upper bounds to ensure reliable convergence. Moreover, drawing insights from
the aforementioned propositions, it becomes evident that in contrast to noise-
free situations, the recovery error of OB-SVT algorithms in noisy scenarios is
constrained by a lower bound contingent upon the impact of noise.

##  VI Numerical Investigations

In this section, we numerically scrutinize the efficacy of our proposed OB-SVT
methods by comparing its recovery results with the state-of-the-art method
(MLE approach) proposed in [47]. Note that in all experiments the number of
time-varying threshold sequences is considered to be $m=1$ except in Fig. 1f.
In particular, we constructed a random $500\times 500$ matrix
$\mathbf{X}=[X_{i,j}]$ with rank $r=10$ by forming
$\mathbf{X}=\mathbf{X}_{1}\mathbf{X}_{2}^{\top}$, where $\mathbf{X}_{1}$ and
$\mathbf{X}_{2}$ are $500\times 10$ matrices with entries drawn i.i.d. from
the Gaussian distribution $\mathcal{N}\left(0,1\right)$. In the results
reported in Fig. 1a, the high-resolution measurements
$\mathcal{P}_{\Omega}\left(\mathbf{X}\right)$ are corrupted by an additive
noise $\mathbf{N}=[n_{i,j}]$ following the distribution
$n_{i,j}\sim\mathcal{N}(0,1)$ resulting in
$\mathcal{P}_{\Omega}\left(\mathbf{Y}\right)=\mathcal{P}_{\Omega}\left(\mathbf{X}+\mathbf{N}\right)$.
We then obtained one-bit observations by comparing the corrupted high-
resolution values with the generated time-varying sampling thresholds
$\bm{\uptau}$ and recording the sign of the resulting value. Herein, we have
utilized the Gaussian distributed random thresholds. Accordingly, inspired by
[70], we have generated the Gaussian time-varying thresholds as
$\left\\{\bm{\uptau}^{(\ell)}\sim\mathcal{N}\left(\mathbf{0},\frac{\beta_{\mathbf{Y}}^{2}}{9}\mathbf{I}\right)\right\\}_{\ell=1}^{m}$,
where $\beta_{\mathbf{Y}}$ denotes the DR of the
$\mathcal{P}_{\Omega}\left(\mathbf{Y}\right)$. For simplicity in OB-SVT
methods, we have utilized step sizes that are independent of the iteration
count; i.e. $\delta_{k}=\delta$ for all $k$. Inspired from [8], we have set
the value of $\delta$ to $\delta=1.2\frac{n_{1}n_{2}}{m_{1}m_{2}}$. The reason
behind this selection has been heuristically justified in [8]. The parameter
$\tau$ is chosen empirically and set to $\tau=\alpha\sqrt{n_{1}n_{2}}$, where
the value of $\alpha$ varies for different values of $m_{1}m_{2}$. Define the
relative error of the reconstruction as $\text{relative
error}\triangleq\frac{\left\|\bar{\mathbf{X}}-\mathbf{X}\right\|_{\mathrm{F}}}{\left\|\mathbf{X}\right\|_{\mathrm{F}}}$,
where $\mathbf{X}$ is the real unknown matrix and $\bar{\mathbf{X}}$ denotes
the reconstructed version of $\mathbf{X}$ by either OB-SVT or MLE methods. In
Fig. 1a, the accuracy of input matrix reconstruction using OB-SVT-I, OB-SVT-II
and MLE methods is compared in terms of relative error. It can be seen that
OB-SVT-I and OB-SVT-II outperform MLE in reconstructing the input matrix. The
reason behind the better performance of OB-SVT-II compared to that of OB-SVT-I
has been discussed in Section V-B.

In Fig. 1b, we have considered the same settings as in Fig. 1a with the
exception that the noise matrix $\mathbf{N}=[n_{i,j}]$ adheres to the Poisson
distribution with the parameter $\lambda=0.5$. Similar to our previous
observation, OB-SVT-I and OB-SVT-II show a better reconstruction results in
terms of relative error compared to the of MLE approach. With the same
settings as in Fig. 1a, Fig. 1c compares the reconstruction performance of OB-
SVT-II in terms of relative error, when Gaussian, Uniform, and discrete
dithers with $M=10$ and $M=100$ are utilized. We have generated the Uniform
random thresholds as
$\left\\{\bm{\uptau}^{(\ell)}\sim\mathcal{U}_{[-a,a]}\right\\}_{\ell=1}^{m}$,
where $a$ denotes the DR of $\mathcal{P}_{\Omega}\left(\mathbf{Y}\right)$. The
discrete dithers can be generated as explained in Section II-A. As can be
observed in Fig. 1c, in the case of Gaussian input matrix, OB-SVT-II with
Gaussian dither shows a better reconstruction performance compared to that of
OB-SVT-II with Uniform and discrete dithers. The reason behind this has been
covered in Claim 1. Also, it can be observed that by increasing the value of
$M$ in the discrete dither, the reconstruction performance of OB-SVT-II tends
to the case of Uniform dithering. The reason behind this is simply followed by
the distribution of discrete dither as described in (1). In the next
experiment, we constructed a random $500\times 500$ matrix
$\mathbf{X}=[X_{i,j}]$ with rank $r=10$ by forming
$\mathbf{X}=\mathbf{X}_{1}\mathbf{X}_{2}^{\top}$, where $\mathbf{X}_{1}$ and
$\mathbf{X}_{2}$ are $500\times 10$ matrices with entries drawn i.i.d. from
the Uniform distribution $\mathcal{U}_{[0,1]}$. Fig. 1d compares the
reconstruction performance of OB-SVT-II in terms of relative error, when
Gaussian and Uniform dithering are utilized. Following Claim 1 in this case,
it is expected that the reconstruction performance of OB-SVT-II with Uniform
dither outperforms the performance of OB-SVT-II with Gaussian dither. As can
be seen, Fig. 1d numerically validates Claim 1. Note that the results reported
in Fig. 1d are related to the noiseless scenario. Define the parameters
$\alpha=\frac{m_{1}m_{2}}{n_{1}n_{2}}$ and $\beta=\frac{s}{m_{1}m_{2}}$, where
$s$ denotes the sketch length in randomized OB-SVT algorithm. By considering
the same settings as in Fig. 1a (with no noise), Fig. 1e illustrates the
reconstruction performance of randomized OB-SVT in terms of relative error
respect to $\beta\in\\{0.005,0.01,0.02,0.1,0.5\\}$ while
$\alpha\in\\{0.3,0.5,0.7\\}$. Based on Theorem 5, increasing the sketch length
$s$ (or increasing the value of $\beta$ here) results in an accelerated
convergence rate which is also numerically validated in Fig. 1e. With the same
settings as in Fig. 1a, Fig. 1f compares the reconstruction performance of OB-
SVT-II in terms of relative error respect to the number of time-varying
threshold sequences $m$ when Gaussian and adaptive dithering scheme are
utilized. As shown, increasing the number of time-varying thresholds leads to
a better reconstruction accuracy. The reason behind this has been
theoretically discussed in Theorems 1 and 2.

##  VII Discussion

This study explores the impact of dithered one-bit sensing on matrix
completion, framing the challenge as a nuclear norm minimization problem
incorporating linear inequality feasibility constraints from one-bit samples.
The adaptation of the SVT algorithm to accommodate these constraints, both in
scenarios with and without noise, outperformed the regularized MLE method in
terms of recovery performance. Incorporating the concept of dithered one-bit
MC, we examined noise characteristics within the problem context, relating the
distance between entries and dithering sequences to a form of noise.
Furthermore, we established a relationship between the number of required
dithering sequences and the suppression of upper bounds on distances between
thresholds and measurements, ultimately leading to improved signal
reconstruction performance. Theoretical results underscored the advantage of
employing Gaussian dithering for input measurements generated through Gaussian
distributions, highlighting its superior recovery performance compared to
Uniform dithering. Numerical discussions extended to discrete dithering and
comparisons with Uniform and Gaussian scenarios. This paper mainly addressed
one-bit MC using nuclear norm minimization. Low-rank matrix factorization
could offer an alternative avenue for further research. The convergence rate
of algorithms based on low-rank matrix factorization remains an active
research area [5]. Our study showed promising outcomes with the sketch-and-
project method using randomized sketching matrices and partial measurements.
Further potential lies in investigating randomized SVD [66, 9].

##  Appendix A Proof of Theorem 2

Assume $\Omega$ is a fixed set with
$\operatorname{card}\left(\Omega\right)=m^{\prime}$. Let
$\left\|d^{(\ell)}_{i,j}\right\|_{\psi_{2}}^{2}\leq K$ for all
$(i,j)\in\Omega,\ell\in[m]$. According to the general Hoeffding’s inequality
[67, Theorem 2.6.2], the event $T_{\mathrm{ave}}\leq\alpha$ holds with a
failure probability at most

$\operatorname{Pr}\left(T_{\mathrm{ave}}\geq\alpha\right)\leq
e^{\frac{-c_{1}\left(\alpha-\mu\right)^{2}}{K}mm^{\prime}},$ (63)

where $c_{1}$ is a positive constant. Define
$\rho=\left(4\sqrt{\frac{\left(2n_{1}n_{2}+m^{\prime}\right)\min\left(n_{1},n_{2}\right)}{m^{\prime}}}+2\right)m^{\prime}\alpha$.
Then, based on the Theorem 1, with high probability the event
$T_{\mathrm{ave}}\leq\alpha$ implies the event
$\left\|\mathbf{X}-\bar{\mathbf{X}}\right\|_{\mathrm{F}}\leq\rho$ for
$\mathbf{X},\bar{\mathbf{X}}\in\mathcal{F}$. The probability derived in (63)
is true for a fixed set $\Omega$. However, to account for all possible uniform
sampling scenarios in matrix completion, we employ the union bound and express
the general case of (63) as follows:

$\displaystyle\operatorname{Pr}\left(T_{\mathrm{ave}}\geq\alpha\quad\text{for
some}\leavevmode\nobreak\ \Omega\subseteq[1:n_{1}n_{2}]\leavevmode\nobreak\
\text{with}\leavevmode\nobreak\
\operatorname{card}\left(\Omega\right)=m^{\prime}\right)$ (64)
$\displaystyle\leq\binom{n_{1}n_{2}}{m^{\prime}}e^{\frac{-c_{1}\left(\alpha-\mu\right)^{2}}{K}mm^{\prime}}.$

Based on
$\binom{n_{1}n_{2}}{m^{\prime}}\leq(en_{1}n_{2}/m^{\prime})^{m^{\prime}}$, we
can rewrite (64) as:

$\displaystyle\operatorname{Pr}\left(T_{\mathrm{ave}}\geq\alpha\quad\text{for
some}\leavevmode\nobreak\ \Omega\subseteq[1:n_{1}n_{2}]\leavevmode\nobreak\
\text{with}\leavevmode\nobreak\
\operatorname{card}\left(\Omega\right)=m^{\prime}\right)$ (65)
$\displaystyle\leq\left(\frac{en_{1}n_{2}}{m^{\prime}}\right)^{m^{\prime}}e^{\frac{-c_{1}\left(\alpha-\mu\right)^{2}}{K}m^{\prime}}\leq
e^{m^{\prime}\log\left(\frac{en_{1}n_{2}}{m^{\prime}}\right)-\frac{c_{1}\left(\alpha-\mu\right)^{2}}{K}mm^{\prime}}.$

In order to achieve a minimum probability of $1-\eta$, it is sufficient to
ensure that the upper bound in (65) is smaller than $\eta$. This establishes
the validity of Theorem 2.

##  Appendix B Proof of Claim 1

Without loss of generality, consider the low-rank matrix
$\mathbf{X}=[X_{i,j}]$, where each $X_{i,j}$ is independently sampled from the
standard Gaussian distribution, $\mathcal{N}(0,1)$. Referring to insights
presented in existing literature, achieving a successful reconstruction
performance in the context of dithered one-bit sensing necessitates that the
time-varying sampling thresholds cover the DR of the input signal [46, 71,
38]. Based on this result, to cover the DR of the generated Gaussian data, we
consider the Gaussian time-varying thresholds as
$\tau_{i,j}^{(\ell)}(g)\sim\mathcal{N}(0,1)$ and the Uniform time-varying
thresholds as $\tau_{i,j}^{(\ell)}(u)\sim\mathcal{U}_{[-4,4]}$. Note that this
selection of time-varying sampling thresholds ensures that the DR of the
Gaussian data is covered with high probability. Let $T_{\mathrm{ave}}^{g}$
denote the average of distances defined in (54) for the Gaussian threshold,
and $T_{\mathrm{ave}}^{u}$ for the Uniform threshold. Assume that
$\mathbb{E}\left\\{T_{\mathrm{ave}}^{g}\right\\}=\mu_{g}$ and
$\mathbb{E}\left\\{T_{\mathrm{ave}}^{u}\right\\}=\mu_{u}$. Then, based on the
Theorems 1 and 2, to prove Claim 1 it suffices to demonstrate that
$\mu_{g}<\mu_{u}$. We can compute $\mu_{g}$ as
$\mu_{g}=\mathbb{E}\left\\{T_{\mathrm{ave}}^{g}\right\\}=\mathbb{E}\left\\{\left|X-T_{g}\right|\right\\}$,
where $X$ and $T_{g}$ are standard normal random variables. Similarly, we can
write
$\mu_{u}=\mathbb{E}\left\\{T_{\mathrm{ave}}^{u}\right\\}=\mathbb{E}\left\\{\left|X-T_{u}\right|\right\\}$,where
$T_{u}$ denotes the Uniform random variable with the distribution
$T_{u}\sim\mathcal{U}_{[-4,4]}$. Since $X$ and $T_{g}$ are independent random
variables, we have $X-T_{g}\sim\mathcal{N}(0,2)$. Then, based on the fact that
$\left|X-T_{g}\right|$ is the folded normal random variable with the scale
parameter $2$, we can obtain $\mu_{g}$ as
$\mu_{g}=2\sqrt{\frac{2}{\pi}}\approx 1.5958$. Since $X$ and $T_{u}$ are
independent random variables, we can calculate $\mu_{u}$ as

$\displaystyle\mu_{u}=\frac{1}{8\sqrt{2\pi}}\int_{-\infty}^{\infty}\int_{-4}^{4}\left|x-t\right|e^{-\frac{x^{2}}{2}}\,dt\,dx,$
(66)

which is obtained as $\mu_{u}\approx 2.1250$. Comparing the values of
$\mu_{g}$ and $\mu_{u}$ completes the proof.

##  Appendix C Convergence Analysis of OB-SVT-I

Define $\mathbf{e}_{k}=\bm{y}^{(k)}-\bm{y}^{\star}$, and

$\displaystyle P\left(\mathbf{X}^{(k)}\right)$
$\displaystyle=\bm{y}^{(k-1)}+\delta_{k}\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right),$
(67) $\displaystyle P\left(\mathbf{X}^{\star}\right)$
$\displaystyle=\bm{y}^{\star}+\delta_{k}\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{\star}\right)\right).$

Since $\bm{y}^{\star}=\left(P\left(\mathbf{X}^{\star}\right)\right)^{+}$ [72],
the error norm is written as

$\displaystyle\left\|\mathbf{e}_{k}\right\|^{2}_{2}$
$\displaystyle=\left\|\left(P\left(\mathbf{X}^{(k)}\right)\right)^{+}-\left(P\left(\mathbf{X}^{\star}\right)\right)^{+}\right\|^{2}_{2}$
(68)
$\displaystyle\leq\left\|\bm{y}^{(k-1)}-\bm{y}^{\star}+\delta_{k}\left(\mathcal{A}\left(\mathbf{X}^{\star}\right)-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)\right\|^{2}_{2}$
$\displaystyle=\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}+2\delta_{k}\mathbf{e}^{\top}_{k-1}\left(\mathcal{A}\left(\mathbf{X}^{\star}\right)-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)$
$\displaystyle\quad\quad\quad\quad\quad+\delta^{2}_{k}\left\|\mathcal{A}\left(\mathbf{X}^{\star}\right)-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right\|^{2}_{2}.$

As shown in [8], we have

$\mathbf{e}^{\top}_{k-1}\left(\mathcal{A}\left(\mathbf{X}^{\star}\right)-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)\leq-\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}},$
(69)

and

$\displaystyle\left\|\mathcal{A}\left(\mathbf{X}^{\star}\right)-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right\|^{2}_{2}$
$\displaystyle=\left\|\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}^{\star}\right)-\bm{\mathcal{B}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right\|^{2}_{2}$
(70)
$\displaystyle\leq\sigma^{2}_{\mathrm{max}}\left(\bm{\mathcal{B}}\right)\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}.$

Combining (69) and (70) with (68) results in

$\displaystyle\left\|\mathbf{e}_{k}\right\|^{2}_{2}\leq\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}-\left(2\delta_{k}-\delta^{2}_{k}\sigma^{2}_{\mathrm{max}}\left(\bm{\mathcal{B}}\right)\right)\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}.$
(71)

Herein, we obtain the maximum singular value of one-bit MC matrix
$\bm{\mathcal{B}}$ as follows:

$\displaystyle\mathbf{W}$
$\displaystyle=\bm{\mathcal{B}}^{\top}\bm{\mathcal{B}}$ (72)
$\displaystyle=\left[\begin{array}[]{c|c|c}\mathbf{P}^{\top}\bm{\Omega}^{(1)}&\cdots&\mathbf{P}^{\top}\bm{\Omega}^{(m)}\end{array}\right]\left[\begin{array}[]{c|c|c}\mathbf{P}^{\top}\bm{\Omega}^{(1)}&\cdots&\mathbf{P}^{\top}\bm{\Omega}^{(m)}\end{array}\right]^{\top}$
$\displaystyle=\mathbf{P}^{\top}\bm{\Omega}^{(1)}\bm{\Omega}^{(1)}\mathbf{P}+\cdots+\mathbf{P}^{\top}\bm{\Omega}^{(m)}\bm{\Omega}^{(m)}\mathbf{P}=m\mathbf{P}^{\top}\mathbf{I}\mathbf{P}=m\mathbf{P}^{\top}\mathbf{P},$

which means that the singular values of $\bm{\mathcal{B}}$ are
$\left\\{\sigma_{\bm{\mathcal{B}}}\right\\}=\sqrt{m}\left\\{\sigma_{i\mathbf{P}}\right\\}$.
Also, the singular values of the permutation matrix $\mathbf{P}$ are all equal
to one. Therefore, the maximum (or minimum) singular value of one-bit MC
matrix $\bm{\mathcal{B}}$ is given by
$\sigma^{2}_{\mathrm{max}}\left(\bm{\mathcal{B}}\right)=m$, which proves the
theorem.

##  Appendix D Convergence Analysis of OB-SVT-II

Define $\mathbf{e}_{k}=\bm{y}^{(k)}-\bm{y}^{\star}$. Then, the error norm is
written as

$\displaystyle\left\|\mathbf{e}_{k}\right\|^{2}_{2}$
$\displaystyle=\left\|\bm{y}^{(k-1)}-\bm{y}^{\star}+\delta_{k}\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{2}$
(73)
$\displaystyle=\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}+2\delta_{k}\mathbf{e}^{\top}_{k-1}\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+}$
$\displaystyle+\delta^{2}_{k}\left\|\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{2}.$

Since a nonnegative value,
$\delta_{k}\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+}$,
is added to $\bm{y}^{(k-1)}$ at each iteration, we can write

$\displaystyle\bm{y}^{(k-1)}+\delta_{k}\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+}\preceq\bm{y}^{\star},$
(74)

or equivalently,

$\displaystyle\bm{y}^{(k-1)}-\bm{y}^{\star}$
$\displaystyle\preceq-\delta_{k}\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+},$
(75)
$\displaystyle\delta_{k}\mathbf{e}^{\top}_{k-1}\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+}$
$\displaystyle\leq-\delta^{2}_{k}\left\|\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{2}.$

Combining (75) with (73) leads to

$\left\|\mathbf{e}_{k}\right\|^{2}_{2}\leq\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}-\delta^{2}_{k}\left\|\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{2}.$
(76)

According to the Hoffman inequality [73], [53, Theorem 4.2], we have

$\displaystyle\sigma^{2}_{\mathrm{min}}\left(\bm{\mathcal{B}}\right)\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}\leq\left\|\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{2}.$
(77)

Combining (77) with (76) results in

$\displaystyle\left\|\mathbf{e}_{k}\right\|^{2}_{2}\leq\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}-\delta^{2}_{k}\sigma^{2}_{\mathrm{min}}\left(\bm{\mathcal{B}}\right)\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}},$
(78)

where according to the proof presented in Appendix C, the minimum singular
value of one-bit MC matrix $\bm{\mathcal{B}}$ is given by
$\sigma^{2}_{\mathrm{min}}\left(\bm{\mathcal{B}}\right)=m$ which proves the
theorem.

##  Appendix E Convergence Analysis of Randomized OB-SVT

Define $\mathbf{e}_{k}=\bm{y}^{(k)}-\bm{y}^{\star}$,
$\widehat{t}=\mathbf{S}\mathbf{t}$, and
$\widehat{\bm{\mathcal{B}}}=\mathbf{S}\bm{\mathcal{B}}$. Then, the error norm
is written as

$\displaystyle\left\|\mathbf{e}_{k}\right\|^{2}_{2}$
$\displaystyle=\left\|\bm{y}^{(k-1)}-\bm{y}^{\star}+\delta_{k}\left(\widehat{\mathbf{t}}-\widehat{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{2}$
(79)
$\displaystyle=\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}+2\delta_{k}\mathbf{e}^{\top}_{k-1}\left(\widehat{\mathbf{t}}-\widehat{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}$
$\displaystyle+\delta^{2}_{k}\left\|\left(\widehat{\mathbf{t}}-\widehat{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{2}.$

Since a nonnegative value,
$\delta_{k}\left(\widehat{\mathbf{t}}-\widehat{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}$,
is added to $\bm{y}^{(k-1)}$ at each iteration, we can write

$\displaystyle\bm{y}^{(k-1)}+\delta_{k}\left(\widehat{\mathbf{t}}-\widehat{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}\leq\bm{y}^{\star},$
(80)

or equivalently,

$\displaystyle\bm{y}^{(k-1)}-\bm{y}^{\star}$
$\displaystyle\preceq-\delta_{k}\left(\widehat{\mathbf{t}}-\widehat{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+},$
(81)
$\displaystyle\delta_{k}\mathbf{e}^{\top}_{k-1}\left(\widehat{\mathbf{t}}-\widehat{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}$
$\displaystyle\leq-\delta^{2}_{k}\left\|\left(\widehat{\mathbf{t}}-\widehat{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{2}.$

Combining (81) with (79) leads to

$\displaystyle\left\|\mathbf{e}_{k}\right\|^{2}_{2}\leq\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}-\delta^{2}_{k}\left\|\left(\widehat{\mathbf{t}}-\widehat{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{2}.$
(82)

Since the infinite norm is lower than norm-2, (82) is rewritten as

$\displaystyle\left\|\mathbf{e}_{k}\right\|^{2}_{2}\leq\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}-\delta^{2}_{k}\left\|\left(\widehat{\mathbf{t}}-\widehat{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{\infty}.$
(83)

By taking the expectation over the error, we have

$\displaystyle\mathbb{E}_{\mathbf{S}}\left\\{\left\|\mathbf{e}_{k}\right\|^{2}_{2}\right\\}\leq\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}-\delta^{2}_{k}\mathbb{E}_{\mathbf{S}}\left\\{\left\|\left(\widehat{\mathbf{t}}-\widehat{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{\infty}\right\\}.$
(84)

We can apply the Jensen’s inequality as follows:

$\displaystyle\mathbb{E}_{\mathbf{S}}$
$\displaystyle\left\\{\left\|\left(\widehat{\mathbf{t}}-\widehat{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{\infty}\right\\}\geq$
(85)
$\displaystyle\left(\mathbb{E}_{\mathbf{S}}\left\\{\left\|\left(\widehat{\mathbf{t}}-\widehat{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|_{\infty}\right\\}\right)^{2}.$

By taking advantage from the estimate for the maximum of independent normal
random variables [67, Section 2.5.2], the following bound is obtained:

$\displaystyle\mathbb{E}_{\mathbf{S}}\left\\{\left\|\left(\widehat{\mathbf{t}}-\widehat{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|_{\infty}\right\\}$
(86) $\displaystyle\geq
c\left\|\left(\tilde{\mathbf{t}}-\tilde{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|_{2}\sqrt{\log
s},$

where $c$ is a positive value, $\mathbf{s}_{t}$ and $\mathbf{g}_{t}$
correspond to the $t$-th rows of $\mathbf{S}$ and $\mathbf{G}$, while
$\tilde{\mathbf{t}}\in\mathbb{R}^{m_{1}m_{2}}$ and
$\tilde{\bm{\mathcal{B}}}\in\mathbb{R}^{m_{1}m_{2}\times n_{1}n_{2}}$ denote
the blocks of $\mathbf{t}$ and $\bm{\mathcal{B}}$, respectively. Combining
(85) and (86) with (84) results in

$\displaystyle\mathbb{E}_{\mathbf{S}}\left\\{\left\|\mathbf{e}_{k}\right\|^{2}_{2}\right\\}\leq\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}-\delta^{2}_{k}c^{2}\log
s\left\|\left(\tilde{\mathbf{t}}-\tilde{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|_{2}^{2}.$
(87)

According to the Hoffman inequality [73], [53, Theorem 4.2], we have

$\displaystyle\sigma^{2}_{\mathrm{min}}\left(\tilde{\bm{\mathcal{B}}}\right)\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}\leq\left\|\left(\tilde{\mathbf{t}}-\tilde{\bm{\mathcal{B}}}\operatorname{vec}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{2}.$
(88)

Based on this result, (87) can be rewritten as

$\displaystyle\mathbb{E}\left\\{\left\|\mathbf{e}_{k}\right\|^{2}_{2}\right\\}\leq\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}-\delta^{2}_{k}c^{2}\sigma^{2}_{\mathrm{min}}\left(\tilde{\bm{\mathcal{B}}}\right)\log
s\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}.$ (89)

Similar to the proof provided in Appendix C, one can simply show that
$\sigma^{2}_{\mathrm{min}}(\tilde{\bm{\mathcal{B}}})=1$ which proves the
theorem.

##  Appendix F Proof of Lemma 1

According to the first step of OB-SVT algorithms, we write

$\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}=\left\|\mathcal{D}_{\tau}\left(\mathcal{A}^{\star}\left(\bm{y}^{(k-1)}\right)\right)-\mathcal{D}_{\tau}\left(\mathcal{A}^{\star}\left(\bm{y}^{\star}\right)\right)\right\|^{2}_{\mathrm{F}}.$
(90)

Consider an operator function $\mathcal{G}_{f}$ applied to a matrix
$\mathbf{X}$ with rank $r$ as follows:
$\mathcal{G}_{f}\left(\mathbf{X}\right)=\sum^{r}_{k=1}f\left(\sigma_{k}\right)\mathbf{u}_{k}\mathbf{v}^{\mathrm{H}}_{k}$,
where $\left\\{\sigma_{k},\mathbf{u}_{k},\mathbf{v}_{k}\right\\}^{r}_{k=1}$
are singular values of $\mathbf{X}$ and its corresponding singular vectors,
and $f$ is a $L$-Lipschitz continuous projector function. As comprehensively
discussed in [74] and [75, Theorem 4.2], the following relation holds for two
matrices $\mathbf{X}_{1}$ and $\mathbf{X}_{2}$ belonging to the Hilbert space
$\mathcal{H}$:

$\left\|\mathcal{G}_{f}\left(\mathbf{X}_{1}\right)-\mathcal{G}_{f}\left(\mathbf{X}_{2}\right)\right\|_{\mathrm{F}}\leq
L\left\|\mathbf{X}_{1}-\mathbf{X}_{2}\right\|_{\mathrm{F}}.$ (91)

In the OB-SVT algorithm, the function $f$ is an operator which compares the
singular values of $\mathbf{X}$ with a fixed threshold $\tau$ and then
eliminate the smaller ones, which is straightforward that it satisfies (91)
with $L=1$. Therefore, one can conclude

$\left\|\mathcal{D}_{\tau}\left(\mathbf{X}_{1}\right)-\mathcal{D}_{\tau}\left(\mathbf{X}_{2}\right)\right\|^{2}_{\mathrm{F}}\leq\left\|\mathbf{X}_{1}-\mathbf{X}_{2}\right\|^{2}_{\mathrm{F}},\leavevmode\nobreak\
\forall\mathbf{X}_{1},\mathbf{X}_{2}\in\mathcal{H}.$ (92)

Combining this result with (90) results in

$\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}\leq\left\|\mathcal{A}^{\star}\left(\bm{y}^{(k-1)}\right)-\mathcal{A}^{\star}\left(\bm{y}^{\star}\right)\right\|^{2}_{\mathrm{F}}.$
(93)

Also, we have

$\left\|\mathcal{A}^{\star}\left(\bm{y}^{(k-1)}\right)-\mathcal{A}^{\star}\left(\bm{y}^{\star}\right)\right\|^{2}_{\mathrm{F}}\leq\sigma^{2}_{\mathrm{max}}\left(\mathcal{A}^{\star}\right)\left\|\bm{y}^{(k-1)}-\bm{y}^{\star}\right\|^{2}_{2},$
(94)

which leads to

$\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}\leq\sigma^{2}_{\mathrm{max}}\left(\mathcal{A}^{\star}\right)\left\|\bm{y}^{(k-1)}-\bm{y}^{\star}\right\|^{2}_{2}.$
(95)

It is straightforward to verify that
$\sigma^{2}_{\mathrm{max}}\left(\mathcal{A}^{\star}\right)=\sigma^{2}_{\mathrm{max}}\left(\bm{\mathcal{B}}^{\dagger}\right)$.
Note that

$\displaystyle\bm{\mathcal{B}}^{\dagger}=\left(\mathbf{P}^{\top}\tilde{\bm{\Omega}}^{\top}\tilde{\bm{\Omega}}\mathbf{P}\right)^{-}\bm{\mathcal{B}}^{\top}=\left(m\mathbf{P}^{\top}\mathbf{P}\right)^{-}\bm{\mathcal{B}}^{\top}=\frac{1}{m}\bm{\mathcal{B}}^{\top},$
(96)

where $\tilde{\bm{\Omega}}$ is defined in (5). Therefore, the maximum singular
value of $\bm{\mathcal{B}}^{\dagger}$ is given by

$\displaystyle\sigma^{2}_{\mathrm{max}}\left(\bm{\mathcal{B}}^{\dagger}\right)=\frac{1}{m^{2}}\sigma^{2}_{\mathrm{max}}\left(\bm{\mathcal{B}}^{\top}\right)=\frac{1}{m^{2}}\sigma^{2}_{\mathrm{max}}\left(\bm{\mathcal{B}}\right)=\frac{1}{m},$
(97)

which proves the lemma.

##  Appendix G Proof of Proposition 1

Using the same notations as introduced in Appendix C, the error norm is
written as

$\displaystyle\left\|\mathbf{e}_{k}\right\|^{2}_{2}$
$\displaystyle\leq\left\|\bm{y}^{(k-1)}-\bm{y}^{\star}+\delta_{k}\left(\mathcal{A}\left(\mathbf{X}^{\star}+\mathbf{N}\right)-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)\right\|^{2}_{2}$
(98)
$\displaystyle\leq\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}+2\delta_{k}\mathbf{e}^{\top}_{k-1}\left(\mathcal{A}\left(\mathbf{X}^{\star}+\mathbf{N}\right)-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)$
$\displaystyle+\delta^{2}_{k}\left\|\mathcal{A}\left(\mathbf{X}^{\star}+\mathbf{N}\right)-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right\|^{2}_{2}.$

According to Theorem 3, since
$\sigma^{2}_{\textrm{max}}\left(\bm{\mathcal{B}}\right)=m$, we have

$\displaystyle\left\|\mathbf{e}_{k}\right\|^{2}_{2}\leq\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}-\left(2\delta_{k}-m\delta^{2}_{k}\right)\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}-\mathbf{N}\right\|^{2}_{\mathrm{F}},$
(99)

where based on the triangle inequality, we can write

$\displaystyle\left\|\mathbf{e}_{k}\right\|^{2}_{2}\leq\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}-\left(2\delta_{k}-m\delta^{2}_{k}\right)\left(\frac{1}{2}\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}-\left\|\mathbf{N}\right\|^{2}_{\mathrm{F}}\right).$
(100)

To guarantee the convergence of OB-SVT-I in the presence of noise, the error
norm must be a nonincreasing function with respect to the iteration.
Therefore, the noise level must satisfy
$\left\|\mathbf{N}\right\|^{2}_{\mathrm{F}}\leq\frac{1}{2}\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}$.
For the OB-SVT-II algorithm, we use the same notations as introduced in
Appendix D, the error norm is written as

$\displaystyle\left\|\mathbf{e}_{k}\right\|^{2}_{2}$
$\displaystyle=\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}+2\delta_{k}\mathbf{e}^{\top}_{k-1}\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+}$
(101)
$\displaystyle+\delta^{2}_{k}\left\|\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{2},$

or simply

$\left\|\mathbf{e}_{k}\right\|^{2}_{2}\leq\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}-\delta^{2}_{k}\left\|\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{2}.$
(102)

According to the Hoffman inequality [73], [53, Theorem 4.2], we have

$\displaystyle\sigma^{2}_{\mathrm{min}}\left(\bm{\mathcal{B}}\right)\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}-\mathbf{N}\right\|^{2}_{\mathrm{F}}\leq\left\|\left(\mathbf{t}-\mathcal{A}\left(\mathbf{X}^{(k)}\right)\right)^{+}\right\|^{2}_{2}.$
(103)

Combining (103) with (102) leads to

$\left\|\mathbf{e}_{k}\right\|^{2}_{2}\leq\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}-m\delta^{2}_{k}\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}-\mathbf{N}\right\|^{2}_{\mathrm{F}}.$
(104)

Since
$\frac{1}{2}\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}-\left\|\mathbf{N}\right\|^{2}_{\mathrm{F}}\leq\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}-\mathbf{N}\right\|^{2}_{\mathrm{F}}$,
we can rewrite (104) as

$\left\|\mathbf{e}_{k}\right\|^{2}_{2}\leq\left\|\mathbf{e}_{k-1}\right\|^{2}_{2}-\frac{1}{2}m\delta^{2}_{k}\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}+m\delta_{k}^{2}\left\|\mathbf{N}\right\|^{2}_{\mathrm{F}}.$
(105)

To guarantee the convergence of OB-SVT-II in the presence of noise, the error
norm must be a nonincreasing function with respect to the iteration.
Therefore, the noise level must satisfy
$\left\|\mathbf{N}\right\|^{2}_{\mathrm{F}}\leq\frac{1}{2}\left\|\mathbf{X}^{(k)}-\mathbf{X}^{\star}\right\|^{2}_{\mathrm{F}}$,
which proves the proposition. Verifying the proof of the similar proposition
for the randomized OB-SVT is as straightforward as the proofs of other
propositions. To establish the convergence of the randomized OB-SVT algorithm
in the presence of noise, it suffices to demonstrate that the _expectation_ of
the error is non-increasing. This can be straightforwardly proven in a similar
manner to the preceding proofs.

## References

  * [1] D. Goldberg, D. Nichols, B. Oki, and D. Terry, “Using collaborative filtering to weave an information tapestry,” _Communications of the ACM_ , vol. 35, no. 12, pp. 61–70, 1992.
  * [2] Z. Liu and L. Vandenberghe, “Interior-point method for nuclear norm approximation with application to system identification,” _SIAM Journal on Matrix Analysis and Applications_ , vol. 31, no. 3, pp. 1235–1256, 2010.
  * [3] A. Singer, “A remark on global positioning from local distances,” _Proceedings of the National Academy of Sciences_ , vol. 105, no. 28, pp. 9507–9511, 2008.
  * [4] P. Jain, P. Netrapalli, and S. Sanghavi, “Low-rank matrix completion using alternating minimization,” in _Proceedings of the forty-fifth annual ACM symposium on Theory of computing_ , 2013, pp. 665–674.
  * [5] Y. Chi, Y. Lu, and Y. Chen, “Nonconvex optimization meets low-rank matrix factorization: An overview,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 20, pp. 5239–5269, 2019.
  * [6] E. Candès and B. Recht, “Exact matrix completion via convex optimization,” _Foundations of Computational mathematics_ , vol. 9, no. 6, pp. 717–772, 2009.
  * [7] M. Fazel, “Matrix rank minimization with applications,” Ph.D. dissertation, PhD thesis, Stanford University, 2002.
  * [8] J. Cai, E. Candès, and Z. Shen, “A singular value thresholding algorithm for matrix completion,” _SIAM Journal on optimization_ , vol. 20, no. 4, pp. 1956–1982, 2010.
  * [9] T. Oh, Y. Matsushita, Y. Tai, and I. Kweon, “Fast randomized singular value thresholding for low-rank optimization,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 40, no. 2, pp. 376–391, 2017.
  * [10] R. Sun and Z. Luo, “Guaranteed matrix completion via non-convex factorization,” _IEEE Transactions on Information Theory_ , vol. 62, no. 11, pp. 6535–6579, 2016.
  * [11] T. Zhao, Z. Wang, and H. Liu, “A nonconvex optimization framework for low rank matrix estimation,” _Advances in Neural Information Processing Systems_ , vol. 28, 2015.
  * [12] R. Keshavan, A. Montanari, and S. Oh, “Matrix completion from a few entries,” _IEEE Transactions on Information Theory_ , vol. 56, no. 6, pp. 2980–2998, 2010.
  * [13] ——, “Matrix completion from noisy entries,” _Advances in neural information processing systems_ , vol. 22, 2009.
  * [14] S. Sun, W. Bajwa, and A. Petropulu, “MIMO-MC radar: A MIMO radar approach based on matrix completion,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 51, no. 3, pp. 1839–1852, 2015.
  * [15] D. Kalogerias and A. Petropulu, “Matrix completion in colocated MIMO radar: Recoverability, bounds & theoretical guarantees,” _IEEE Transactions on Signal Processing_ , vol. 62, no. 2, pp. 309–321, 2013.
  * [16] S. Sun and A. Petropulu, “Waveform design for MIMO radars with matrix completion,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 9, no. 8, pp. 1400–1414, 2015.
  * [17] S. Sun, K. V. Mishra, and A. Petropulu, “Target estimation by exploiting low rank structure in widely separated MIMO radar,” in _2019 IEEE Radar Conference (RadarConf)_. IEEE, 2019, pp. 1–6.
  * [18] L. Jacques, J. Laska, P. Boufounos, and R. Baraniuk, “Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors,” _IEEE Transactions on Information Theory_ , vol. 59, no. 4, pp. 2082–2102, 2013.
  * [19] P. Boufounos, L. Jacques, F. Krahmer, and R. Saab, “Quantization and compressive sensing,” in _Compressed Sensing and its Applications: MATHEON Workshop 2013_. Springer, 2015, pp. 193–237.
  * [20] C. Kong, A. Mezghani, C. Zhong, A. Swindlehurst, and Z. Zhang, “Multipair massive MIMO relaying systems with one-bit ADC s and DAC s,” _IEEE Transactions on Signal Processing_ , vol. 66, no. 11, pp. 2984–2997, 2018.
  * [21] A. Mezghani and A. Swindlehurst, “Blind estimation of sparse broadband massive MIMO channels with ideal and one-bit ADCs,” _IEEE Transactions on Signal Processing_ , vol. 66, no. 11, pp. 2972–2983, 2018.
  * [22] Y. Li, C. Tao, G. Seco-Granados, A. Mezghani, A.and Swindlehurst, and L. Liu, “Channel estimation and performance analysis of one-bit massive MIMO systems,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 15, pp. 4075–4089, 2017.
  * [23] C.-L. Liu and P. Vaidyanathan, “One-bit sparse array DoA estimation,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2017, pp. 3126–3130.
  * [24] L. Schuchman, “Dither signals and their effect on quantization noise,” _IEEE Transactions on Communication Technology_ , vol. 12, no. 4, pp. 162–165, 1964.
  * [25] J. Vanderkooy and S. Lipshitz, “Dither in digital audio,” _Journal of the Audio Engineering Society_ , vol. 35, no. 12, pp. 966–975, 1987.
  * [26] M. Wagdy and W. Ng, “Validity of uniform quantization error model for sinusoidal signals without and with dither,” _IEEE Transactions on Instrumentation and Measurement_ , vol. 38, no. 3, pp. 718–722, 1989.
  * [27] P. Carbone, “Quantitative criteria for the design of dither-based quantizing systems,” _IEEE Transactions on Instrumentation and Measurement_ , vol. 46, no. 3, pp. 656–659, 1997.
  * [28] A. Ali, H. Dinc, P. Bhoraskar, S. Bardsley, C. Dillon, M. McShea, J. Periathambi, and S. Puckett, “A 12-b 18-GS/s RF sampling ADC with an integrated wideband track-and-hold amplifier and background calibration,” _IEEE Journal of Solid-State Circuits_ , vol. 55, no. 12, pp. 3210–3224, 2020\.
  * [29] M. Wagdy, “Effect of various dither forms on quantization errors of ideal A/D converters,” _IEEE Transactions on Instrumentation and Measurement_ , vol. 38, no. 4, pp. 850–855, 1989.
  * [30] P. Carbone and D. Petri, “Effect of additive dither on the resolution of ideal quantizers,” _IEEE Transactions on Instrumentation and Measurement_ , vol. 43, no. 3, pp. 389–396, 1994.
  * [31] F. Xi, Y. Xiang, S. Chen, and A. Nehorai, “Gridless parameter estimation for one-bit MIMO radar with time-varying thresholds,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 1048–1063, 2020.
  * [32] I. Robinson, J. Toplicar, and J. Heston, “Analog to digital conversion using differential dither,” 2019, US Patent 10,298,256.
  * [33] A. Ali and P. Gulati, “Background calibration of reference, DAC, and quantization non-linearity in ADCs,” Jan. 28 2020, US Patent 10,547,319.
  * [34] C. Gianelli, L. Xu, J. Li, and P. Stoica, “One-bit compressive sampling with time-varying thresholds for sparse parameter estimation,” in _IEEE Sensor Array and Multichannel Signal Processing Workshop_ , 2016, pp. 1–5.
  * [35] P. Wang, J. Li, M. Pajovic, P. T. Boufounos, and P. V. Orlik, “On angular-domain channel estimation for one-bit massive MIMO systems with fixed and time-varying thresholds,” in _Asilomar Conference on Signals, Systems, and Computers_ , 2017, pp. 1056–1060.
  * [36] C. Xu and L. Jacques, “Quantized compressive sensing with RIP matrices: The benefit of dithering,” _Information and Inference: A Journal of the IMA_ , vol. 9, no. 3, pp. 543–586, 2020.
  * [37] A. Eamaz, F. Yeganegi, and M. Soltanalian, “Modified arcsine law for one-bit sampled stationary signals with time-varying thresholds,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2021, pp. 5459–5463.
  * [38] A. Eamaz,, F. Yeganegi, and M. Soltanalian , “Covariance recovery for one-bit sampled non-stationary signals with time-varying sampling thresholds,” _IEEE Transactions on Signal Processing_ , 2022.
  * [39] A. Eamaz, F. Yeganegi, and M. Soltanalian, “Covariance recovery for one-bit sampled stationary signals with time-varying sampling thresholds,” _Signal Processing_ , vol. 206, p. 108899, 2023.
  * [40] S. Dirksen, J. Maly, and H. Rauhut, “Covariance estimation under one-bit quantization,” _The Annals of Statistics_ , vol. 50, no. 6, pp. 3538–3562, 2022.
  * [41] O. Dabeer and A. Karnik, “Signal parameter estimation using 1-bit dithered quantization,” _IEEE Transactions on Information Theory_ , vol. 52, no. 12, pp. 5389–5405, 2006.
  * [42] C. Thrampoulidis and A. S. Rawat, “The generalized LASSO for sub-Gaussian measurements with dithered quantization,” _IEEE Transactions on Information Theory_ , vol. 66, no. 4, pp. 2487–2500, 2020.
  * [43] S. Dirksen and S. Mendelson, “Non-Gaussian hyperplane tessellations and robust one-bit compressed sensing,” _Journal of the European Mathematical Society_ , vol. 23, no. 9, pp. 2913–2947, 2021.
  * [44] A. Eamaz, F. Yeganegi, D. Needell, and M. Soltanalian, “Harnessing the power of sample abundance: Theoretical guarantees and algorithms for accelerated one-bit sensing,” _arXiv preprint arXiv:2308.00695_ , 2023.
  * [45] A. Eamaz, F. Yeganegi, and M. Soltanalian, “One-bit phase retrieval: More samples means less complexity?” _IEEE Transactions on Signal Processing_ , vol. 70, pp. 4618–4632, 2022.
  * [46] A. Eamaz, K. V. Mishra, F. Yeganegi, and M. Soltanalian, “UNO: Unlimited sampling meets one-bit quantization,” _arXiv preprint arXiv:2301.10155_ , 2022.
  * [47] M. A. Davenport, Y. Plan, E. Van Den Berg, and M. Wootters, “1-bit matrix completion,” _Information and Inference: A Journal of the IMA_ , vol. 3, no. 3, pp. 189–223, 2014.
  * [48] T. Cai and W. Zhou, “A max-norm constrained minimization approach to 1-bit matrix completion.” _J. Mach. Learn. Res._ , vol. 14, no. 1, pp. 3619–3647, 2013.
  * [49] P. Gao, R. Wang, M. Wang, and J. Chow, “Low-rank matrix recovery from noisy, quantized, and erroneous measurements,” _IEEE Transactions on Signal Processing_ , vol. 66, no. 11, pp. 2918–2932, 2018.
  * [50] S. Foucart and L. Jacques, “One-bit sensing of low-rank and bisparse matrices,” in _2019 13th International conference on Sampling Theory and Applications (SampTA)_. IEEE, 2019, pp. 1–4.
  * [51] P. Martinsson and J. Tropp, “Randomized numerical linear algebra: Foundations and algorithms,” _Acta Numerica_ , vol. 29, pp. 403–572, 2020.
  * [52] T. Strohmer and R. Vershynin, “A randomized Kaczmarz algorithm with exponential convergence,” _Journal of Fourier Analysis and Applications_ , vol. 15, no. 2, pp. 262–278, 2009.
  * [53] D. Leventhal and A. S. Lewis, “Randomized methods for linear constraints: Convergence rates and conditioning,” _Mathematics of Operations Research_ , vol. 35, no. 3, pp. 641–654, 2010.
  * [54] R. Yuan, A. Lazaric, and R. Gower, “Sketched Newton–Raphson,” _SIAM Journal on Optimization_ , vol. 32, no. 3, pp. 1555–1583, 2022.
  * [55] S. Foucart and R. G Lynch, “Recovering low-rank matrices from binary measurements,” _Inverse Problems & Imaging_, vol. 13, no. 4, 2019.
  * [56] S. Bhaskar and A. Javanmard, “1-bit matrix completion under exact low-rank constraint,” in _Annual Conference on Information Sciences and Systems_ , 2015, pp. 1–6.
  * [57] R. Ni and Q. Gu, “Optimal statistical and computational rates for one bit matrix completion,” in _Artificial Intelligence and Statistics_. PMLR, 2016, pp. 426–434.
  * [58] S. Bhaskar, “Probabilistic low-rank matrix completion from quantized measurements,” _The Journal of Machine Learning Research_ , vol. 17, no. 1, pp. 2131–2164, 2016.
  * [59] Y. Cao and Y. Xie, “Categorical matrix completion,” in _2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)_. IEEE, 2015, pp. 369–372.
  * [60] R. Baraniuk, S. Foucart, D. Needell, Y. Plan, and M. Wootters, “Exponential decay of reconstruction error from binary measurements of sparse signals,” _IEEE Transactions on Information Theory_ , vol. 63, no. 6, pp. 3368–3385, 2017.
  * [61] A. Bose, A. Ameri, M. Klug, and M. Soltanalian, “Low-rank matrix recovery from one-bit comparison information,” in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2018, pp. 4734–4738.
  * [62] S. Ma, D. Goldfarb, and L. Chen, “Fixed point and bregman iterative methods for matrix rank minimization,” _Mathematical Programming_ , vol. 128, no. 1-2, pp. 321–353, 2011.
  * [63] W. Yin, S. Osher, D. Goldfarb, and J. Darbon, “Bregman iterative algorithms for l1-minimization with applications to compressed sensing,” _SIAM Journal on Imaging sciences_ , vol. 1, no. 1, pp. 143–168, 2008.
  * [64] C. Van Loan and G. Golub, _Matrix computations_. The Johns Hopkins University Press, 1996.
  * [65] B. Polyak, “Gradient methods for solving equations and inequalities,” _USSR Computational Mathematics and Mathematical Physics_ , vol. 4, no. 6, pp. 17–32, 1964.
  * [66] M. Dereziński and E. Rebrova, “Sharp analysis of sketch-and-project methods via a connection to randomized singular value decomposition,” _arXiv preprint arXiv:2208.09585_ , 2022.
  * [67] R. Vershynin, _High-dimensional probability: An introduction with applications in data science_. Cambridge university press, 2018, vol. 47.
  * [68] E. Candès and Y. Plan, “Matrix completion with noise,” _Proceedings of the IEEE_ , vol. 98, no. 6, pp. 925–936, 2010.
  * [69] E. Candès and T. Tao, “The power of convex relaxation: Near-optimal matrix completion,” _IEEE Transactions on Information Theory_ , vol. 56, no. 5, pp. 2053–2080, 2010.
  * [70] A. Eamaz, F. Yeganegi, D. Needell, and M. Soltanalian, “One-bit quadratic compressed sensing: From sample abundance to linear feasibility,” _arXiv preprint arXiv:2303.09594_ , 2023.
  * [71] J. N. Laska, Z. Wen, W. Yin, and R. G. Baraniuk, “Trust, but verify: Fast and accurate signal recovery from 1-bit compressive measurements,” _IEEE Transactions on Signal Processing_ , vol. 59, no. 11, pp. 5289–5301, 2011.
  * [72] B. C. Eaves, “On the basic theorem of complementarity,” _Mathematical Programming_ , vol. 1, no. 1, pp. 68–75, 1971.
  * [73] A. J. Hoffman, “On approximate solutions of systems of linear inequalities,” in _Selected Papers Of Alan J Hoffman: With Commentary_. World Scientific, 2003, pp. 174–176.
  * [74] M. Carlsson, “Lipschitz continuity for isotropic matrix functions,” _Linear Algebra and its Applications_ , vol. 624, pp. 259–266, 2021.
  * [75] F. Andersson, M. Carlsson, and K. Perfekt, “Operator-Lipschitz estimates for the singular value functional calculus,” _Proceedings of the American Mathematical Society_ , vol. 144, no. 5, pp. 1867–1875, 2016.