# UNO: Unlimited Sampling Meets One-Bit Quantization

Arian Eamaz, , Kumar Vijay Mishra, , 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 has been submitted for
publication at the 2023 IEEE International Conference on Acoustics, Speech and
Signal Processing (ICASSP)
(_Corresponding author: Arian Eamaz_)A. Eamaz, F. Yeganegi, and M. Soltanalian
are with the Department of Electrical and Computer Engineering, University of
Illinois Chicago, Chicago, IL 60607, USA (e-mail: _{aeamaz2, fyegan2,
msol}@uic.edu_).K. V. Mishra is with the United States DEVCOM Army Research
Laboratory, Adelphi, MD 20783 USA (e-mail: _kvm@ieee.org_).

###### Abstract

Recent results in one-bit sampling provide a framework for a relatively low-
cost, low-power sampling, at a high rate by employing time-varying sampling
threshold sequences. Another recent development in sampling theory is
unlimited sampling, which is a high-resolution technique that relies on _self-
reset ADCs_ to yield an unlimited dynamic range. In this paper, we leverage
the appealing attributes of the two aforementioned techniques to propose a
novel _un_ limited _o_ ne-bit (UNO) sampling approach. In this framework, the
information on the distance between the input signal value and the threshold
are stored and utilized to accurately reconstruct the one-bit sampled signal.
We then utilize this information to accurately reconstruct the signal from its
one-bit samples via the randomized Kaczmarz algorithm (RKA); a strong linear
feasibility solver that selects a random linear equation at each iteration. In
the presence of noise, we employ the recent plug-and-play (PnP) priors
technique with alternating direction method of multipliers (ADMM) to exploit
integration of state-of-the-art regularizers in the reconstruction process.
Numerical experiments with RKA and PnP-ADMM-based reconstruction illustrate
the effectiveness of our proposed UNO, including its superior performance
compared to the one-bit $\Sigma\Delta$ sampling.

###### Index Terms:

Kaczmarz algorithm, one-bit quantization, PnP-ADMM, self-reset ADCs, unlimited
sampling.

##  I Introduction

Sampling theory lies at the heart of all modern digital processing systems.
The original sampling problem entails identifying a continuous function on
Euclidean space from discrete data samples. It is addressed by the classical
sampling theorem, commonly and variously, attributed to Cauchy [1], de La
Vallée Poussin [2], Whittaker [3], Ogura [4], Kotelńikov [5], Raabe [6],
Shannon [7], and/or Someya [8]. A seminal result in this context, referred to
as Whittaker-Kotelńikov-Shannon (or, simply Shannon’s) theorem, states that it
is possible to fully recover a bandlimited function from values measured on a
regular sampling grid as long as the bandlimitation is an interval with length
not exceeding the density of the sampling grid. Restating this in signal
processing terms, a lowpass bandlimited signal can be perfectly reconstructed
from its discrete samples taken uniformly at a sampling frequency that is at
least the Nyquist rate, i.e., twice the signal bandwidth. During the past few
decades, several variants and extensions of this result have solidified the
extensive role of sampling theory in science and engineering [9, 10, 11].

Shannon’s theorem assumes the existence of samples that are of infinite
precision and infinite dynamic range (DR). But, in practice, it is realized by
the quantization of the signals through analog-to-digital converters (ADCs)
that clip or saturate whenever the signal amplitude exceeds the maximum
recordable ADC voltage, leading to a significant information loss. The effects
of finite precision quantization are characterized in the form of rate
distortion theory [12, 13]. However, investigations into finite DR or clipping
effects are relatively recent [14, 15, 16, 17]. Substantial work has been done
and is still ongoing to overcome this problem, and the literature is too large
to summarize here; see, e.g., [18] and the references therein, for comparisons
of various techniques. Overall, these approaches require declipping [19],
multiple ADCs [20], and scaling techniques [21], which are expensive and
cumbersome. Recently, some studies [18, 22, 23] have proposed the _unlimited
sampling_ architecture to fully overcome this limitation by employing modular
arithmetic. To perfectly reconstruct the signal of interest from modulo
samples (up to a unknown constant), the unlimited sampling theory suggests the
sampling rate to be slightly higher than the Nyquist rate and the norm
estimate of the bandlimited signal be known.

Conventional multi-bit ADCs require a very large number of quantization levels
to represent the original continuous signal in high resolution settings.
Sampling at high data rates with high resolution ADCs, however, would
dramatically increase the overall power consumption and the manufacturing cost
of such ADCs [24]. This problem is exacerbated in systems that require
multiple ADCs such as large array receivers [25]. An immediate solution to
such challenges is to use fewer bits for sampling. Therefore, in the recent
years, the design of receivers with low-complexity one-bit ADC has been
emphasized to meet the requirements of both wide signal bandwidth and low
cost/power. _One-bit quantization_ is an extreme quantization scenario, in
which the ADCs are merely comparing the signals with given threshold levels,
producing sign ($\pm 1$) outputs. This enables the signal processing equipment
to sample at a very high rate yet with considerably lower cost and energy
consumption than the conventional ADCs [26, 27, 28, 24, 29].

In the classical problem of one-bit sampling, the signal is reconstructed by
comparing the signal with a fixed, usually zero, threshold. This leads to
difficulties in estimating signal parameters. In particular, when zero
threshold is used, the power information of the input signal $\mathbf{x}$ is
lost in one-bit data because the signs of $\mathbf{x}$ and $\eta\mathbf{x}$
are identical for $\eta>0$. This problem has been addressed in a few recent
works [28, 30, 31, 32, 33, 34, 35], which show that time-varying sampling
thresholds enable better estimation of the signal characteristics. In
particular, time-varying thresholds were considered for the covariance
recovery from one-bit measurements in [28]. This was extended in [33] for a
significantly improved estimation of signal autocorrelation via the _modified
arcsine law_. In non-stationary scenarios, [33] applied the modified arcsine
law to utilize time-varying sampling thresholds. Applications of one-bit
sampling to diverse problems such as sparse parameter estimation [31],
localization [36], and phase retrieval [32] have also appeared in the
contemporary literature.

Evidently, one-bit and unlimited sampling frameworks address complementary
requirements. A one-bit ADC only compares an input signal with a given
threshold. Therefore, essentially, one-bit sampling is indifferent to DR
because, apart from the comparison bit, other information such as the distance
between the signal value and the threshold is not stored. On the other hand,
the self-reset ADC in unlimited sampling provides a natural approach to
producing judicious time-varying thresholds for one-bit ADCs. In this paper,
to harness advantages of both methods, we propose _un_ limited _o_ ne-bit
(UNO) sampling to design sampling thresholds which are highly informative
about the signal of interest.

###  I-A Prior Art

Unlimited sampling of continuous-time signals that are sparse in Fourier
domain was discussed in [37]. Extensions to graph signals [38], multi-channel
arrays [39], and sparse outliers (noise) [40] have also been proposed.
Reconstruction algorithms have included wavelet-based [23], generalized
approximate message passing [41], and local average [42] techniques. Very
recently, non-idealities in hardware prototyping were considered in [43, 44];
a computational sampling strategy in the form of unlimited sampling with
hysteresis [45] was found to be more flexible for circuit design
specifications.

To reconstruct the full-precision signal from one-bit sampled data,
conventional approaches [46, 47] include maximum likelihood estimation (MLE)
and weighted least squares. However, these methods have high computational
cost, especially for high-dimensional input signals. To this end, we propose
using the randomized Kaczmarz algorithm (RKA) [48, 49], which is an iterative
algorithm for solving a system of linear inequalities that arise naturally in
the one-bit quantization framework. While the deterministic version[50] of the
Kaczmarz method usually selects the linear equation sequentially, the RKA is
random in its selection in each iteration leading to a faster convergence. The
RKA is simple to implement and performs comparably with the state-of-the-art
optimization methods.

Among prior studies involving both one-bit and unlimited frameworks, state-of-
the-art results in [51] proposed one-bit $\Sigma\Delta$ quantization via
unlimited sampling, whose objective is to shrink the DR between the input
signal and its one-bit samples. This study developed a guaranteed
reconstruction as long as the DR of the input signal is less than the DR of
the one-bit data (i.e., 1). However, when the ratio of the input signal
amplitude to the ADC threshold is large, then the imperfect noise shaping in
sigma-delta conversion degrades this reconstruction. Contrary to this work,
our proposed UNO technique focuses on a different problem, i.e., shrinking the
DR between the input signal and the time-varying sampling thresholds. The one-
bit sampling is typically performed at significantly high rates. As a result,
the resulting observation inequalities form an overdetermined system. When the
difference between the DR of the input signal and that of the thresholds
increases, the reconstruction degrades significantly. We show that jointly
exploiting both unlimited and one-bit sampling techniques provides a more
efficient solution by a considerable reduction of the aforementioned gap.

In practice, errors arising from quantization noise degrade the reconstruction
quality in unlimited sampling framework. In this context, [18] derived the
reconstruction guarantees by including this error as bounded additive noise to
the modulo samples. Contrary to this approach, we consider the more realistic
case of additive noise to the input signal. We show that our RKA-based
reconstruction is also effective for noisy one-bit sampled signals because it
is independent from the statistical properties of the modulo samples.

###  I-B Our Contributions

Our main contributions in this paper are:
1) Combined unlimited and one-bit sampling framework. In the proposed UNO
framework, we leverage upon the benefits of both one-bit and unlimited
sampling techniques. The result is a sampling approach that yields unlimited
DR and a low-cost, low-power receiver while retaining a high sampling rate. We
design time-varying sampling thresholds for one-bit quantization, whose DR is
closer to that of the original signal. This aids in accurately storing the
information of distance between the signal values and thresholds to utilize in
the signal reconstruction task. We show that compared to the one-bit
reconstruction with random thresholds [24], our proposed UNO sampling based on
time-varying thresholds performs better, especially for high DR signals.
2) RKA-based reconstruction. The signal reconstruction from one-bit
measurements requires solving an overdetermined linear feasibility problem
that we recast as a one-bit polyhedron and efficiently solve it via the RKA.
By generating an abundant number of one-bit samples, we show that the singular
values of one-bit data matrix that creates the one-bit polyhedron are equal to
the number of time-varying threshold sequences employed in one-bit sampling.
Further, we numerically investigate the effects of ADC threshold and signal
amplitude in the RKA-based UNO reconstruction.
3) Performance guarantees. Our theoretical analyses show that a proper
selection of the sufficient number of samples further enhances the
reconstruction performance of the UNO. We prove that the convergence rate of
the RKA when applied to the one-bit polyhedron depends on the size of the
input signal and the total number of RKA iterations. In this context, we also
obtain a lower bound on the number of required iterations for perfect
reconstruction.
4) Reconstruction in the presence of additive noise. When the input signal is
contaminated with additive noise, we apply the recently introduced new plug-
and-play (PnP) priors [52] to the alternating direction method of multipliers
(ADMM) as an additional reconstruction algorithm step. In image denoising
problems, the PnP-ADMM is used to replace the shrinkage step of the standard
ADMM algorithm with any off-the-shelf algorithm to ensure the noise variance
is sufficiently suppressed. Although PnP-ADMM appears ad hoc, it yields a
better performance than state-of-the-art methods in several different inverse
problems [52, 53]. For the noisy UNO, we deploy this algorithm to reconstruct
the original signal from overdetermined and underdetermined noisy systems.
Moreover, we show that the additive noise to the input signal contaminates the
modulo samples with noise that is expressed in terms of the input noise.

###  I-C Organization and Notations

In the next section, we provide an introduction to one-bit quantization with
time-varying sampling thresholds. Particularly, the one-bit sampled signal
reconstruction problem is formulated as an overdetermined system of linear
inequalities. In Section III, we recall the concept of unlimited sampling as
proposed in [22, 18]. We introduce the RKA in the context of signal
reconstruction in Section IV. This is a prelude to Section V, which proposes
UNO sampling to design judicious thresholds and guarantee the one-bit signal
reconstruction in the high-DR. In Section VI, we provide several numerical
experiments to illustrate UNO-based sampling and analyze the reconstruction
error. We consider the noisy measurement scenario in Section VII and conclude
in Section VIII.

Throughout this paper, we use boldface lowercase, boldface uppercase, and
calligraphic letters for vectors, matrices, and sets, respectively. The
notations $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$ represent the set of
complex, real, and integer numbers, respectively. We represent a vector
$\mathbf{x}$ in terms of its elements $\\{x_{i}\\}$ or
$\left(\mathbf{x}\right)_{i}$ as $\mathbf{x}=[x_{i}]$. We use $(\cdot)^{\top}$
and $(\cdot)^{\mathrm{H}}$ to denote the vector/matrix transpose and the
Hermitian transpose, respectively. The identity matrix of size $N$ is
$\mathbf{I}_{N}\in\mathbb{R}^{N\times N}$. 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 function
$\text{diag}(\cdot)$ outputs a diagonal matrix with the input vector along its
main diagonal. The $\ell_{p}$-norm of a vector $\mathbf{b}$ is
$\|\bm{b}\|_{p}=\left(\sum_{i}b^{p}_{i}\right)^{1/p}$. The infinity or max-
norm of a function $x$ is $\|x\|_{\infty}=\operatorname{inf}\left\\{c_{0}\geq
0:|x(t)|\leq c_{0}\right\\}$, where $\textrm{inf}(\cdot)$ denotes the infimum
of its argument; for vectors, we have
$\|\mathbf{x}\|_{\infty}=\max_{k}|x_{k}|$. For a vector $\mathbf{x}$,
$\Delta\mathbf{x}=x_{k+1}-x_{k}$ denotes the finite difference and recursively
applying the same yields $N$-th order difference, $\Delta^{N}\mathbf{x}$. We
denote the $\Omega$-bandlimited Paley-Wiener subspace of the square-integrable
function space $L^{2}$ by $\textrm{PW}_{\Omega}$ such that
$\textrm{PW}_{\Omega}=\\{f:f,\widehat{f}\in
L^{2},\;\operatorname{supp}(\widehat{f})\subset[-\Omega,\Omega]\\}$, where
$\widehat{f}$ is the Fourier transform of $f$. The Hadamard (element-wise)
product of two matrices $\mathbf{B}_{1}$ and $\mathbf{B}_{2}$ is
$\mathbf{B}_{1}\odot\mathbf{B}_{2}$. The column-wise vectorized form of a
matrix $\mathbf{B}$ is $\operatorname{vec}(\mathbf{B})$. 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 function $\operatorname{sgn}(\cdot)$ yields
the sign of its argument. In the context of numerical computations,
$\lfloor\rfloor$ and $\lceil\rceil$ denote the floor and ceiling functions,
respectively. 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 operator $\operatorname{mod}(a,b)$
between two values $a$ and $b$, returns the remainder of the division
operation $a/b$.

##  II One-Bit Sampling: Overdetermined Linear System Formulation

Several approaches have been proposed in the literature to reconstruct the
signal of interest from one-bit samples with the most of them formulating this
task as an optimization problem. For example, the covariance matrix
formulation of [24] employs the cyclic optimization method to recover the
input autocorrelation elements. A convex program based on the Gauss-Legendre
integration to recover the input covariance matrix from one-bit sampled data
was suggested in [33]. Other recent works exploit sparsity of the signal and
apply techniques such as $\ell_{1}$-norm minimization [54, 55],
$\ell_{1}$-regularized MLE formulation [47, 56], log-relaxation [57], and
Lasserre’s semidefinite program relaxation [36] to lay the ground for signal
reconstruction. In the following, we explain our one-bit polyhedron
formulation, wherein a strong efficient and easily implementable solver of
linear feasibility problems is applied to the aforementioned application-
specific methods.

###  II-A One-Bit Quantization Using Time-Varying Thresholds

Consider a bandlimited continuous-time signal $x\in\textrm{PW}_{\Omega}$ that
we represent via Shannon’s sampling theorem as [10]

$0<\mathrm{T}\leqslant\frac{\pi}{\Omega},\quad
x(t)=\sum_{k=-\infty}^{k=+\infty}x(k\mathrm{T})\operatorname{sinc}\left(\frac{t}{\mathrm{T}}-k\right),$
(1)

where $1/\mathrm{T}$ is the sampling rate, $\Omega$ is the signal bandwidth,
and $\operatorname{sinc}(t)=\frac{\sin(\pi t)}{\pi t}$ is an _ideal_ low-pass
filter. Denote the uniform samples of $x(t)$ with the sampling rate
$1/\mathrm{T}$ by $x_{k}=x(k\mathrm{T})$.

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 [24, 33]. These thresholds may be
chosen from any distribution. In this work, to be consistent with state-of-
the-art [24, 46, 28], we consider a Gaussian non-zero time-varying threshold
vector $\bm{\uptau}=\left[\tau_{k}\right]$ that follows the distribution
$\bm{\uptau}\sim\mathcal{N}\left(\mathbf{d}=\mathbf{1}d,\bm{\Sigma}\right)$.
For one-bit quantization with such time-varying sampling thresholds,
$r_{k}=\operatorname{sgn}\left(x_{k}-\tau_{k}\right)$.

###  II-B One-Bit Polyhedron

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)\geq\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\mathcal{L}=\\{1,\cdots,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\mathcal{L},$
(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.

##  III Unlimited Sampling

In a variety of applications, clipping or saturation poses a serious problem
to signal reconstruction. For instance, in scientific imaging systems such as
ultrasound [14], radar [58], and seismic imaging [59], strong reflections or
pulse echoes blind the sensor. In audio processing, clipped sound results in
high-frequency artifacts [15]. In this context, unlimited sampling suggests
that, instead of point-wise samples of the bandlimited function $x(t)$, the
signal is digitized using a self-reset ADC with an appropriately selected
threshold $\lambda>0$ such that any signal value outside the range
$\left[-\lambda,\lambda\right]$ is _folded_ to the same range [22, 18]. The
folding corresponds to introducing a non-linearity in the sensing process [22,
18]. We denote the folding by the modulo operator $\mathcal{M}_{\lambda}$ that
represents the following mapping:

$\mathcal{M}_{\lambda}(x_{k}):\tilde{x}_{k}=x_{k}-2\lambda\left\lfloor\frac{x_{k}}{2\lambda}+\frac{1}{2}\right\rfloor,$
(8)

where $\tilde{x}_{k}$ are the modulo samples of $x(t)$.

The _unlimited sampling theorem_ [18] (reproduced below) states that, if the
estimate of the norm of the bandlimited signal is known, then its perfect
reconstruction (up to additive multiples of $2\lambda$) from its modulo
samples is possible with at least sampling period $T\leq(2\pi e)^{-1}$, where
$e$ is the Euler’s number and the signal bandwidth has been normalized to
$\pi$.

######  Theorem 1 (Unlimited sampling theorem [18]).

Assume $x(t)$ to be a finite energy, bandlimited signal with maximum frequency
$\Omega_{\textrm{max}}$ and let $\tilde{x}_{k}$, $k\in\mathbb{Z}$ in (8) be
the modulo samples of $x(t)$ with sampling rate $1/T$. Then a sufficient
condition for the reconstruction of $x(t)$ from
$\left\\{\tilde{x}_{k}\right\\}$ is that
$T\leq\frac{1}{2\Omega_{\textrm{max}}e}$ (up to additive multiples of
$2\lambda$).

Theorem 1 implies that the sampling rate depends on only the bandwidth and is
independent of the ratio of ADC threshold $\lambda$ to the signal amplitude.
In other words, the DR of the input signal is _unlimited_. Recently, stable
unlimited sampling reconstruction in the presence of noise has also been
obtained [18].

The reconstruction of the bandlimited function $x(t)$ from its modulo samples
$\left\\{\tilde{x}_{k}\right\\}$ is achieved as follows. Assume that $x(t)$
admits a decomposition [22, 18],

$x(t)=\tilde{x}(t)+\epsilon_{x}(t),$ (9)

where $\tilde{x}(t)=\mathcal{M}_{\lambda}\left(x(t)\right)$ and the error
$\epsilon_{x}$ between the input signal and its modulo samples is

$\epsilon_{x}(t)=2\lambda\sum_{u\in\mathbb{Z}}e_{u}\mathbb{1}_{\mathcal{D}_{u}}(t),\quad
e_{u}\in\mathbb{Z},$ (10)

where $\bigcup_{u\in\mathbb{Z}}\mathcal{D}_{u}=\mathbb{R}$ is a partition of
the real line into intervals $\mathcal{D}_{u}$. As indicated by (9), if
$\epsilon_{x}$ is known, then $x$ can be reconstructed from $\tilde{x}$. It
follows from (10) that $\epsilon_{x}$ takes only those values that are integer
multiples of $2\lambda$ thereby leading to a robust reconstruction algorithm
[18]. To obtain $\epsilon_{x}$ (up to an unknown additive constant) and
subsequently the desired signal $x(t)$, the reconstruction procedure in [22,
18] requires the higher-order differences of
$\tilde{\mathbf{x}}=[\tilde{x}_{k}]$ to obtain
$\Delta^{N}\bm{\epsilon}_{x}=\mathcal{M}_{\lambda}\left(\Delta^{N}\tilde{\mathbf{x}}\right)-\Delta^{N}\tilde{\mathbf{x}}$,
where $\bm{\epsilon}_{x}=[\epsilon_{x}]$. Define the inverse-difference
operator as a sum of real sequence $\\{s_{b}\\}$, i.e.,

$\nabla:\\{s_{k}\\}_{k\in\mathbb{Z}^{+}}\rightarrow\sum_{b=1}^{k}s_{b}.$ (11)

Then, applying $\nabla\left(\Delta^{N}\bm{\epsilon}_{x}\right)$ and rounding
the result to the nearest multiple of $2\lambda\mathbb{Z}$ yields
$\epsilon_{x}$. For a guaranteed and stable reconstruction performance, a
suitable choice for difference order $N$ is [18],

$N\geq\left\lceil\frac{\log\lambda-\log\beta_{x}}{\log\left(T\Omega
e\right)}\right\rceil,$ (12)

where $\beta_{x}$ is chosen such that $\beta_{x}\in 2\lambda\mathbb{Z}$ and
$\|x\|_{\infty}\leq\beta_{x}$. Algorithm 1 summarizes the unlimited sampling
reconstruction procedure.

Algorithm 1 Input signal reconstruction from modulo folded samples.

1:Input: $\tilde{x}_{k}=\mathcal{M}_{\lambda}\left(x_{k}\right)$, ADC
threshold $\lambda$, and $2\lambda\mathbb{Z}\ni\beta_{x}\geq\|x\|_{\infty}$.

2:Output: The approximation of the input signal $\bar{\mathbf{x}}$.

3:$N\leftarrow\left\lceil\frac{\log\lambda-\log\beta_{x}}{\log\left(T\Omega
e\right)}\right\rceil$ using (12).

4:$\Delta^{N}\bm{\epsilon}_{x}\leftarrow\mathcal{M}_{\lambda}\left(\Delta^{N}\tilde{\mathbf{x}}\right)-\Delta^{N}\tilde{\mathbf{x}}$.

5:$\mathbf{s}_{0}\leftarrow\Delta^{N}\bm{\epsilon}_{x}$.

6:for $p=0:N-2$ do

7: $\mathbf{s}_{p+1}\leftarrow\nabla\mathbf{s}_{p}$ $\triangleright$ $\nabla$
is the inverse-difference operator defined in (11).

8: $\mathbf{s}_{p+1}\leftarrow
2\lambda\left\lceil\frac{\left\lfloor\mathbf{s}_{p+1}/\lambda\right\rfloor}{2}\right\rceil$
$\triangleright$ rounding to $2\lambda\mathbb{Z}$.

9:
$\kappa_{p}\leftarrow\left\lfloor\frac{\left(\nabla^{2}\Delta^{p}\bm{\epsilon}_{x}\right)_{1}-\left(\nabla^{2}\Delta^{p}\bm{\epsilon}_{x}\right)_{J+1}}{12\beta_{x}}+\frac{1}{2}\right\rfloor$
$\triangleright$ $J=\frac{6\beta_{x}}{\lambda}$.

10: $\mathbf{s}_{p+1}\leftarrow\mathbf{s}_{p+1}+2\lambda\kappa_{p}$.

11:return
$\bar{\mathbf{x}}\leftarrow\nabla\mathbf{s}_{N-1}+\tilde{\mathbf{x}}+2a\lambda,\quad
a\in\mathbb{Z}$.

##  IV One-Bit Signal Reconstruction

To reconstruct $\mathbf{x}$ from the sign data
$\left\\{\mathbf{r}^{(\ell)}\right\\}^{m}_{\ell=1}$, we solve the polyhedron
search problem through RKA because of its optimal projection and linear
convergence in expectation [32, 60, 49].

###  IV-A Basic Theory of RKA

The RKA is a _subconjugate gradient method_ to solve overdetermined linear
systems, i.e, $\mathbf{C}\mathbf{x}\leq\mathbf{b}$ where $\mathbf{C}$ is a
$m^{\prime}\times n^{\prime}$ matrix with $m^{\prime}>n^{\prime}$ [49, 48].
The conjugate-gradient methods turn this inequality to an equality of the
following form:

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

and then solve it as any other system of equations. Given a sample index set
$\mathcal{J}$, without loss of generality, rewrite (13) as the polyhedron

$\displaystyle\begin{cases}\mathbf{c}_{j}\mathbf{x}\leq
b_{j}&\left(j\in\mathcal{I}_{\leq}\right),\\\
\mathbf{c}_{j}\mathbf{x}=b_{j}&\left(j\in\mathcal{I}_{=}\right),\end{cases}$
(14)

where $\\{\mathbf{c}_{j}\\}$ are the rows of $\mathbf{C}$ and the disjoint
index sets $\mathcal{I}_{\leq}$ and $\mathcal{I}_{=}$ partition $\mathcal{J}$.
The projection coefficient $\beta_{i}$ of the RKA is [49, 60, 61]:

$\beta_{i}=\begin{cases}\left(\mathbf{c}_{j}\mathbf{x}_{i}-b_{j}\right)^{+}&\left(j\in\mathcal{I}_{\leq}\right),\\\
\mathbf{c}_{j}\mathbf{x}_{i}-b_{j}&\left(j\in\mathcal{I}_{=}\right).\end{cases}$
(15)

The unknown column vector $\mathbf{x}$ is iteratively updated as

$\mathbf{x}_{i+1}=\mathbf{x}_{i}-\frac{\beta_{i}}{\left\|\mathbf{c}_{j}\right\|^{2}_{2}}\mathbf{c}^{\mathrm{H}}_{j},$
(16)

where, at each iteration $i$, the index $j$ is drawn from the set
$\mathcal{J}$ independently at random following the distribution

$\operatorname{Pr}\\{j=k\\}=\frac{\left\|\mathbf{c}_{k}\right\|^{2}_{2}}{\|\mathbf{C}\|_{\mathrm{F}}^{2}}.$
(17)

Note that, (7) has only the inequality partition $I_{\leq}$. Herein,
$m^{\prime}=m\times n$ and $n^{\prime}=n$. The row vector $\mathbf{c}_{j}$ and
the scalar $b_{j}$ in the RKA (14)-(17) are $j$-th row of
$-\tilde{\bm{\Omega}}$ and $j$-th element of
$-\left(\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}\right)\right)$,
respectively. It may be readily verified that the distribution of choosing a
specific sample index $j$ for the inequalities in (7) is uniform, i.e.,
$\operatorname{Pr}\\{j=k\\}=\frac{1}{mn}$.

In one-bit reconstruction, $\mathbf{c}_{j}=-\upomega_{j}$, wherein
$\upomega_{j}$ is the $j$-th row of $\tilde{\bm{\Omega}}$; a $j^{\prime}$-th
_coordinate vector_ with $\pm 1$ as its $j^{\prime}$-th element and

$\displaystyle j^{\prime}=\begin{cases}\operatorname{mod}(j,n),&j\neq kn,\\\
n,&j=kn,\end{cases}$ (18)

with $1\leq k\leq m$. This property makes the update process (16) similar to
that of the _randomized Gauss-Seidal_ method using the coordinate vector in
each iteration [49, 62]. This approach is commonly used for solving high-
dimensional linear feasibility problems by updating only one dimension at any
iteration. The structure of matrix $\tilde{\bm{\Omega}}$ leads to a similar
efficient RKA implementation by updating only the generic element $j^{\prime}$
at each iteration, i.e.,
$\left(\mathbf{x}_{i+1}\right)_{j^{\prime}}=\left(\mathbf{x}_{i}\right)_{j^{\prime}}-\beta_{i}r_{j^{\prime}}$,
where $r_{j^{\prime}}$ is the one-bit data at index $j^{\prime}$.

Figure 1:  (a) The input sawtooth wave signal $\mathbf{x}$ is reconstructed
from one-bit measurements using the RKA to yield $\bar{\mathbf{x}}$. Here,
$\text{DR}_{\mathbf{x}}=1$ and $\text{DR}_{\bm{\uptau}}=1$. The inset shows
the same plot on a larger scale. (b) As in (a) but for the bandlimited input
signal from [18] with $\text{DR}_{\mathbf{x}}=5$. (c) As in (b) but for
$\text{DR}_{\mathbf{x}}=8$.

###  IV-B Error Reconstruction Bound

At the $i$-th iteration, the error between the RKA estimate $\mathbf{x}_{i}$
and the optimal solution $\mathbf{x}^{\star}$ has been shown to follow the
convergence bound [48, 49, 60, 63]

$\mathbb{E}\left\\{\left\|\mathbf{x}_{i}-\mathbf{x}^{\star}\right\|_{2}^{2}\right\\}\leq
q^{i}\left\|\mathbf{x}_{0}-\mathbf{x}^{\star}\right\|_{2}^{2},$ (19)

where
$q=1-\frac{1}{\kappa\left(\tilde{\bm{\Omega}}\right)}\;\in\left(0,1\right)$
and
$\kappa\left(\tilde{\bm{\Omega}}\right)=\|\tilde{\bm{\Omega}}\|^{2}_{\mathrm{F}}\|\tilde{\bm{\Omega}}^{\dagger}\|^{2}_{2}$
is scaled condition number [64] of $\tilde{\bm{\Omega}}$, which is a block
matrix of $m$ diagonal matrices per (5). We have

$\|\tilde{\bm{\Omega}}\|^{2}_{\mathrm{F}}=\sum^{mn}_{j=1}r^{2}_{j}=\sum^{mn}_{j=1}1=mn.$
(20)

Moreover,
$\|\tilde{\bm{\Omega}}^{\dagger}\|^{2}_{2}=\frac{1}{\sigma^{2}_{\textrm{min}}}$,
where $\sigma_{\textrm{min}}=\min\left\\{\sigma_{i}\right\\}$ is the minimum
singular value of $\tilde{\bm{\Omega}}$ [65] (maximum singular value is
$\sigma_{\textrm{max}}$ similarly defined). Following Lemma 1 evaluates
singular values of $\tilde{\bm{\Omega}}$.

######  Lemma 1.

Consider the concatenation of all $m$ sign data matrices in (5), i.e.,
$\tilde{\bm{\Omega}}\in\mathbb{R}^{mn\times n}$, where $n$ is the size of the
input signal and $m$ is the number of time-varying sampling thresholds. The
matrix $\tilde{\bm{\Omega}}$ is full-rank and its singular values are

$\sigma_{1}=\sigma_{2}=\cdots=\sigma_{n}=\sqrt{m}.$ (21)

###### Proof:

Compute the square matrix

$\displaystyle\mathbf{P}$
$\displaystyle=\tilde{\bm{\Omega}}^{\top}\tilde{\bm{\Omega}}=\left[\begin{array}[]{c|c|c}\bm{\Omega}^{(1)}&\cdots&\bm{\Omega}^{(m)}\end{array}\right]\left[\begin{array}[]{c|c|c}\bm{\Omega}^{(1)}&\cdots&\bm{\Omega}^{(m)}\end{array}\right]^{\top}$
(22)
$\displaystyle=\bm{\Omega}^{(1)}\left(\bm{\Omega}^{(1)}\right)^{\top}+\bm{\Omega}^{(2)}\left(\bm{\Omega}^{(2)}\right)^{\top}+\cdots+\bm{\Omega}^{(m)}\left(\bm{\Omega}^{(m)}\right)^{\top},$
$\displaystyle=m\mathbf{I}.$

Hence, the eigenvalues of $\mathbf{P}$ are equal to $m$. In other words, the
singular values of $\tilde{\bm{\Omega}}$ are
$\left\\{\sigma_{i}\right\\}_{i=1}^{n}=\sqrt{m}$. ∎

It follows from (20) and Lemma 1 that
$\kappa\left(\tilde{\bm{\Omega}}\right)=\frac{mn}{\sigma^{2}_{\textrm{min}}}=n$.
Conventionally, the condition number of a matrix is defined as
$\frac{\sigma_{\textrm{max}}}{\sigma_{\textrm{min}}}$. From Lemma 1, all
singular values are equal. Hence,
$\kappa\left(\tilde{\bm{\Omega}}\right)=n\frac{\sigma_{\textrm{max}}}{\sigma_{\textrm{min}}}$
is indeed the condition number scaled by $n$. This leads to

$\displaystyle q=\frac{n-1}{n}.$ (23)

Set the algorithm termination criterion to the condition

$\mathbb{E}\left\\{\left\|\mathbf{x}_{i}-\mathbf{x}^{\star}\right\|_{2}^{2}\right\\}\leq\epsilon_{1},$
(24)

where $\epsilon_{1}$ is a positive constant. Based on this criterion and (19),
the following Proposition 1 states the lower bound on the number of required
RKA iterations.

######  Proposition 1.

The number of RKA iterations $i$ required to achieve the optimal solution
$\mathbf{x}^{\star}$ of length $n$ from its one-bit samples within the error
specified by (24) is

$\displaystyle i$
$\displaystyle\geq\frac{\log\left(\frac{\omega_{0}}{\epsilon_{1}}\right)}{\log\left(\frac{1}{1-\frac{1}{n}}\right)},$
(25)

where $\omega_{0}=\left\|\mathbf{x}_{0}-\mathbf{x}^{\star}\right\|_{2}^{2}$ is
the initial squared error (at $i=0$) and $\epsilon_{1}$ is a positive
constant.

###### Proof:

Define
$q^{i}\left\|\mathbf{x}_{0}-\mathbf{x}^{\star}\right\|_{2}^{2}\leq\epsilon_{1}$,
or equivalently,

$\displaystyle q^{i}$ $\displaystyle\leq\frac{\epsilon_{1}}{\omega_{0}}.$ (26)

Note that $\omega_{0}$ is a constant scalar that depends on only the initial
and optimal solutions. Substituting (23) in (26) and taking logarithm on both
sides yields

$i\log\left(1-\frac{1}{n}\right)\leq\log\left(\frac{\epsilon_{1}}{\omega_{0}}\right).$
(27)

∎

Since the optimal solution is unknown, $\omega_{0}$ may not be precisely
determined. However, a suitable number of required iterations may still be
selected following Theorem 1 with a reasonable guess for $\omega_{0}$. For
instance, an initial value $\mathbf{x}_{0}$ may be chosen in the direction of
optimal solution $\mathbf{x}^{\star}$ so that a $\omega_{0}$ is obtained [48,
49].

###  IV-C Numerical Example

Fig. 1a illustrates the RKA reconstruction of a sawtooth signal from one-bit
polyhedron in (7) for $10$ sweeps (periods) with a fundamental frequency of
$50\leavevmode\nobreak\ \mathrm{Hz}$. We discretized the generated signal
$x(t)$ at the sampling rate (interval) of $1\leavevmode\nobreak\ \mathrm{kHz}$
($\mathrm{T}=0.001\leavevmode\nobreak\ \mathrm{s}$). The time-varying sampling
thresholds were drawn from the distribution
$\bm{\uptau}^{(\ell)}\sim\mathcal{N}\left(\mathbf{0},\mathbf{I}\right)$, for
all $\ell\in\mathcal{L}$. Define the normalized mean squared error,
$\operatorname{NMSE}\triangleq\frac{\left\|\mathbf{x}-\bar{\mathbf{x}}\right\|_{2}^{2}}{\left\|\mathbf{x}\right\|_{2}^{2}}$,
where $\mathbf{x}$ and $\bar{\mathbf{x}}$ denote the true (discretized) signal
and its reconstructed version, respectively. Since RKA selects each hyperplane
randomly in each iteration, we repeat the reconstruction in Fig. 1a for $15$
times. The averaged NMSE over all experiments is only $\sim 0.0012$ or
$-29.2082\leavevmode\nobreak\ \mathrm{dB}$.

###  IV-D Limitations of Conventional One-Bit Reconstruction

Denote the DRs of the desired signal $\mathbf{x}$ and the time-varying
threshold $\bm{\uptau}$ by $\text{DR}_{\mathbf{x}}$ and
$\text{DR}_{\bm{\uptau}}$, respectively, where we define the DR of a vector as
its $\ell_{\infty}$-norm. _If
$\text{DR}_{\mathbf{x}}\leq\text{DR}_{\bm{\uptau}}$, then the reconstructed
signal $\mathbf{x}^{\star}$ may be found inside the polyhedron (7) with a high
probability for an adequate number of samples. Otherwise, if
$\text{DR}_{\mathbf{x}}>\text{DR}_{\bm{\uptau}}$, there is no guarantee to
obtain $\mathbf{x}^{\star}$ since the desired solution cannot be inside the
finite-volume space imposed by the set of inequalities in (7) indicating an
irretrievable information loss._ We demonstrate this as follows. Without loss
of generality, consider $x_{k}=\text{DR}_{\mathbf{x}}$ for $x_{k}>0$. Assume
$\tau_{k}^{\star}=\max_{\ell}\leavevmode\nobreak\ \tau_{k}^{(\ell)}$. Since
$\text{DR}_{\bm{\uptau}}=\|\bm{\uptau}\|_{\infty}$, we have
$\tau_{k}^{\star}\leq\text{DR}_{\bm{\uptau}}$. If
$\text{DR}_{\mathbf{x}}>\text{DR}_{\bm{\uptau}}$, then we have
$\tau_{k}^{\star}<\text{DR}_{\mathbf{x}}=x_{k}$. Therefore, to reconstruct the
$k$-th entry of the input signal $x_{k}$, we always have a gap
$\delta=x_{k}-\tau_{k}^{\star}>0$ that is not covered by any sample to capture
the amplitude information of $\mathbf{x}$. Hence, the desired signal is not
found inside the finite-volume space imposed by the inequalities in (7).

In Fig. 1a, $\text{DR}_{\bm{\uptau}}=3$ is larger than
$\text{DR}_{\mathbf{x}}=1$ thereby leading to a low reconstruction NMSE. We
now consider $x$ to be a bandlimited function with piece-wise constant Fourier
transform values are drawn uniformly at random, i.e.,
$\widehat{x}(\omega)\sim\operatorname{unif}(0,1)$. This signal is the same as
the one used in [18]. The time-varying sampling thresholds were generated
following the procedure explained in Section IV-C. Fig. 1b shows the RKA-based
reconstruction of the bandlimited signal from the polyhedron (7). Around $t=0$
(corresponding sample index is $364$ in the plot), the reconstruction severely
degrades because $\text{DR}_{\mathbf{x}}=5$ is set to be larger than
$\text{DR}_{\bm{\uptau}}=3$. Indeed, when the difference between
$\text{DR}_{\mathbf{x}}$ and $\text{DR}_{\bm{\uptau}}$ increases further, we
observe a significant loss of information in the reconstructed signal (Fig.
1c).

##  V Toward a Reconstruction Guarantee for One-Bit Sampling

Since RKA does not guarantee an exact signal reconstruction from one-bit
measurements in (7) when the DR of the signal exceeds that of the time-varying
sampling threshold, it is pertinent to design the time-varying sampling
threshold such that
$\text{DR}_{\mathbf{x}}\leq\text{DR}_{\mathbf{\bm{\uptau}}}$. This is not
always possible because the desired signal is unknown. We address this
limitation via UNO, which is our proposed new one-bit sampling method based on
the concept of unlimited sampling.

As discussed in Section III, unlimited sampling yields signal amplitudes
folded within the range $\left[-\lambda,\lambda\right]$. This suggests an
alternative time-varying threshold with the same DR as the modulo samples
$\tilde{\mathbf{x}}=[\tilde{x}_{k}]$; i.e. $\text{DR}_{\bm{\uptau}}=\lambda$.
In other words, the thresholds are modified to be closer to the clipping value
and the self-reset ADC is integrated with one-bit sampling. We summarize this
UNO sampling framework as follows:

  1. 1.

Apply the modulo operator defined in (8) to the input signal $\mathbf{x}$ and
obtain modulo samples
$\tilde{\mathbf{x}}=\mathcal{M}_{\lambda}\left(\mathbf{x}\right)$.

  2. 2.

Design sequences of the time-varying sampling threshold
$\left\\{\bm{\uptau}^{(\ell)}\right\\}_{\ell=1}^{m}$ such that
$\left|\text{DR}_{\bm{\uptau}^{(\ell)}}-\lambda\right|\leq\varepsilon_{0}$ for
all $\ell\in\mathcal{L}=\\{1,\cdots,m\\}$ and a small number
$\varepsilon_{0}$.

  3. 3.

Apply the one-bit quantization to modulo samples as
$\mathbf{r}^{(\ell)}=\operatorname{sgn}\left(\tilde{\mathbf{x}}-\bm{\uptau}^{(\ell)}\right)$.

Fig. 2 illustrates various steps of our UNO sampling technique. The following
Proposition 2 states the UNO threshold design.

######  Proposition 2 (Judicious threshold design).

Under the UNO sampling framework, the following DR guarantee holds: Assume
each one-bit sampling threshold $\bm{\uptau}^{(\ell)}$ is distributed as
$\bm{\uptau}^{(\ell)}\sim\mathcal{N}\left(\mathbf{0},\sigma^{2}_{\bm{\uptau}}\mathbf{I}\right)$.
Then, considering the ADC threshold $\lambda$, $\sigma_{\bm{\uptau}}$ will be
equal to $\frac{\lambda}{3}$ with a probability of at least $0.99$.

###### Proof:

With a probability of at least $0.99$, the DR of each
$\bm{\uptau}^{(\ell)}\sim\mathcal{N}\left(\mathbf{0},\sigma^{2}_{\mathbf{\uptau}}\mathbf{I}\right)$
is $3\sigma_{\bm{\uptau}}$ [66]. When
$\sigma_{\bm{\uptau}}=\frac{\lambda}{3}$, then time-varying sampling threshold
also has a DR of $\lambda$ with a probability of at least $0.99$. ∎

Figure 2: The UNO sampling architecture. The proper choice of the sampling
interval $T$ in the middle block is specified by Theorem 2.

(a) Transfer function of 1-bit ADC

(b) Input signal and threshold

(c) Transfer function of UNO ADC

(d) Modulo samples and threshold

Figure 3: (a) Transfer function of conventional one-bit ADC where the $i$-th
element of the input signal $x=(\mathbf{x})_{i}$ is compared with a randomly
selected threshold $\bm{\uptau}$ (b) High DR input signal $\mathbf{x}$ and its
thresholds samples $\uptau$. (c) As in (a), but for UNO with the judicious
time-varying threshold $\lambda$. (d) The unlimited samples
$\tilde{\mathbf{x}}$ compared with the thresholded samples $\bm{\uptau}$ and
$\lambda$.

(a) $m=2$

(b) $m=6$

(c) $m=20$

(d) $m=2$

(e) $m=6$

(f) $m=20$

Figure 4: Top: Trihedron space (polyhedron (28) in $3$ dimensions) (blue),
unlimited sampling cube (red), and true value of the modulo signal
$\tilde{\mathbf{x}}\in\mathbb{R}^{3}$ (yellow) for (a) $m=2$ (b) $m=6$ and (c)
$m=20$. Bottom: As in the top panel, but only a cross-section (unshaded with
same color boundary) at $Z=0$ plane is shown for (d) $m=2$ (e) $m=6$ and (f)
$m=20$. Each inequality constraint is shown by a half-space whose feasible
region is marked by black arrows.

In Proposition 2, we design time-varying sampling threshold sequences so that
their DR is close to that of the input signal. This enables storing the
information of distance between the input signal and the thresholds without
any loss of information via one-bit sampling. Fig. 3 shows a comparison of
conventional one-bit sampling and UNO for the high DR scenario; the transfer
function of the former is plotted in Fig. 3a. We consider the same bandlimited
signal as in Section IV-D and a random threshold
$\bm{\uptau}\sim\mathcal{N}\left(\mathbf{0},\mathbf{I}\right)$. In case of
one-bit sampling, the signal values and thresholds differ considerably at some
points (Fig. 3b) and, consequently, the information on the distance between
the signal value and the threshold samples is completely lost. For UNO, the
threshold is chosen closer to the folded signal with $\lambda=0.5$ (Fig. 3c).
This preserves the information of the input signal in the modulo samples (Fig.
3d).

For reconstruction of the signal of interest $\mathbf{x}$ from UNO samples, we
reformulate the polyhedron (7) for modulo samples as

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

This overdetermined system of linear inequalities in (28) is then solved via
RKA and, from the resulting approximated modulo samples, we obtain
$\mathbf{x}$ via Algorithm 1. Algorithm 2 summarizes these steps of the _UNO
algorithm_.

Algorithm 2 Signal reconstruction in UNO.

1:Input: Sequences of one-bit measurements
$\left\\{\mathbf{r}^{(\ell)}=\operatorname{sgn}\left(\mathcal{M}_{\lambda}\left(\mathbf{x}\right)-\bm{\uptau}^{(\ell)}\right)\right\\}_{\ell=1}^{m}$,
$\bm{\uptau}^{(\ell)}\sim\mathcal{N}\left(\mathbf{0},\sigma^{2}_{\bm{\uptau}}\mathbf{I}\right)$,
ADC threshold $\lambda$, total number of iterations $i_{\textrm{max}}$.

2:Output: The approximation of the input signal $\bar{\mathbf{x}}$.

3:$\mathbf{R}\leftarrow\left\\{\mathbf{r}^{(\ell)}\right\\}_{\ell=1}^{m}$.

4:$\sigma_{\bm{\uptau}}\leftarrow\frac{\lambda}{3}$

5:$\bm{\Gamma}\leftarrow\left\\{\bm{\uptau}^{(\ell)}\right\\}_{\ell=1}^{m}$

6:$\bm{\Omega}^{(\ell)}\leftarrow\operatorname{diag}\left(\mathbf{r}^{(\ell)}\right)$

7:$\tilde{\bm{\Omega}}\leftarrow\left[\begin{array}[]{c|c|c}\bm{\Omega}^{(1)}&\cdots&\bm{\Omega}^{(m)}\end{array}\right]^{\top}$

8:$\tilde{\mathcal{P}}\leftarrow\left\\{\tilde{\mathbf{x}}\mid\tilde{\bm{\Omega}}\tilde{\mathbf{x}}\succeq\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}\right)\right\\}$.

9:Find the modulo signal in $\tilde{\mathcal{P}}$ via RKA.

10:for $i=1:i_{\textrm{max}}$ do

11:
$\tilde{\mathbf{x}}_{i+1}\leftarrow\tilde{\mathbf{x}}_{i}+\left(-\upomega_{j}\tilde{\mathbf{x}}_{i}+\upomega_{j}\bm{\uptau}^{(\ell)}\right)^{+}\upomega^{\top}_{j}$

12:$\bar{\tilde{\mathbf{x}}}\leftarrow\tilde{\mathbf{x}}_{i_{\textrm{max}}}$

13:Reconstruct the input signal via Algorithm 1 from
$\bar{\tilde{\mathbf{x}}}$.

14:return $\bar{\mathbf{x}}$

In Fig. 4, we show that increasing the number $m$ of time-varying sampling
threshold sequences guarantees the RKA-based reconstruction as it leads the
space formed by the intersection of half-spaces (inequality constraints in
(28)) to completely shrink to the true value modulo signal
$\tilde{\mathbf{x}}$ inside the volume space imposed by unlimited sampling.
This volume space is a _cube_ because the constraints applied to the modulo
samples are $-\lambda\leq\tilde{x}_{k}\leq\lambda$. Here, the blue
planes/lines representing the linear inequalities form a finite-volume space
around the optimal point (displayed by the yellow circle inside the cube) by
increasing the number of one-bit sampling thresholds. In the top panel, we
show the specific case of a trihedron (i.e., modulo samples are
$\tilde{\mathbf{x}}\in\mathbb{R}^{3}$) to represent the effect of increasing
the number of threshold sequences on the reconstruction performance. The
bottom panel shows the same effect for 2-D cross-section of the trihedron. The
constraints are not enough to create a finite-volume space in Fig. 4a and d.
On the other hand, in Fig. 4b and e, such constraints create the desired
finite-volume polyhedron space but are unable to capture the optimal point.
Finally, in Fig. 4c and f, the optimal point is successfully captured by the
resulting finite-volume space. The following theorem summarizes the UNO
guarantees.

Figure 5: Reconstruction of the input signal from one-bit measurements using
UNO when the ADC threshold is (a) $\lambda=1$, (b) $\lambda=0.5$, and (c)
$\lambda=0.2$. (d)-(f) As in, respectively, (a)-(c) but the true unlimited
samples are compared with their reconstructed samples.

######  Theorem 2 (UNO sampling theorem).

Assume $x(t)$ to be a finite energy, bandlimited signal with maximum frequency
$\Omega_{\textrm{max}}$. Let $\tilde{x}_{k}$, $k\in\mathbb{Z}$, introduced in
(8) be the modulo samples of $x(t)$ with sampling rate $1/T$. Assume
$\bar{\tilde{\mathbf{x}}}$ contains the modulo samples reconstructed by the
RKA and define the reconstruction error as
$\mathbf{e}=\left(\bar{\tilde{\mathbf{x}}}-\tilde{\mathbf{x}}\right)$. Then,
the sufficient condition for the reconstruction of bandlimited samples $x_{k}$
from UNO samples
$\left\\{\mathbf{r}^{(\ell)}=\operatorname{sgn}\left(\mathcal{M}_{\lambda}\left(\mathbf{x}\right)-\bm{\uptau}^{(\ell)}\right)\right\\}_{\ell=1}^{m}$,
where
$\bm{\uptau}^{(\ell)}\sim\mathcal{N}\left(\mathbf{0},\frac{\lambda^{2}}{9}\mathbf{I}\right)$,
up to additive multiples of $2\lambda$ is

$T\leq\frac{1}{2^{h}\Omega_{\textrm{max}}e},$ (29)

where $h\in\mathbb{N}$ is given by

$h\geq\frac{\log\left(\frac{2\beta_{x}}{\lambda}\right)}{\log\left(\frac{\lambda}{4\left\|\mathbf{e}\right\|_{\infty}}\right)},$
(30)

and

$\lambda\geq 4\zeta\left\|\mathbf{e}\right\|_{\infty},\quad\zeta>1.$ (31)

###### Proof:

While reconstructing the modulo samples from one-bit data via RKA, the real
modulo samples are represented by the linear model

$\bar{\tilde{\mathbf{x}}}=\tilde{\mathbf{x}}+\mathbf{e}.$ (32)

The error in RKA reconstruction may be viewed as _noise_ for modulo samples.
According to [43, Theorem 3], the sampling rate for the _contaminated_ modulo
samples in (32) to reconstruct the bandlimited samples $x_{k}$ to satisfy
$\bar{x}_{k}=x_{k}+e_{k}$ is $T\leq\frac{1}{2^{h}\Omega_{\textrm{max}}e}$,
where $h\in\mathbb{N}$, and

$\left\|\mathbf{e}\right\|_{\infty}\leq\frac{\lambda}{4}\left(\frac{2\beta_{x}}{\lambda}\right)^{-\frac{1}{h}}.$
(33)

Clearly, (30) follows from (33). Moreover, to ensure that the log function
used in (30) is positive, we have
$\frac{\lambda}{4\left\|\mathbf{e}\right\|_{\infty}}\geq\zeta>1$ leading to a
lower bound for the ADC threshold $\lambda\geq
4\zeta\left\|\mathbf{e}\right\|_{\infty}$. This completes the proof. ∎

Theorem 2 provides the lower bound for the ADC threshold $\lambda$ in Eq.
(31). The upper bound on $T$ for UNO sampling is lower than or equal to that
of the unlimited sampling (the equality holds when $h=1$) which associates
with a higher sampling rate in UNO. As mentioned later in Section VI-B,
oversampling is a a common scenario in one-bit quantization techniques and not
a major concern in UNO implementation. Note that the resulting error
$\mathbf{e}$ of RKA is different than the noise considered in [43, Theorem 3]
in the sense that, unlike the latter, the corresponding reconstructed modulo
samples in UNO obey $\left|\bar{\tilde{x}}_{k}\right|<\lambda$. This ensures
that $N$ in (12) guarantees
$\Delta^{N}\bar{\mathbf{x}}\equiv\mathcal{M}_{\lambda}\left(\Delta^{N}\bar{\mathbf{x}}\right)$
or equivalently
$\Delta^{N}\bar{\mathbf{x}}\equiv\mathcal{M}_{\lambda}\left(\Delta^{N}\bar{\tilde{\mathbf{x}}}\right)$;
we refer the reader to [18] for more details on this aspect. As a result, UNO
perfectly reconstructs the input samples $x_{k}$ in the sense that
$\bar{x}_{k}=x_{k}+e_{k}$ (up to additive multiples of $2\lambda$) with the
same $N$ considered in the noiseless unlimited sampling reconstruction of [43,
Section IV.B].

##  VI UNO Reconstruction: Numerical Illustrations and Error Analyses

We assessed the performance of the UNO reconstruction through extensive
numerical experiments. In particular, we validate that the size of the cube
imposed by self-reset ADCs (red contours and shaded regions in Fig. 4) and,
hence, the reconstruction error depend on the ADC threshold $\lambda$. We then
investigate the effect of input signal amplitude
$\left\|\mathbf{x}\right\|_{\infty}$ on the reconstruction performance. In all
experiments, we considered the same high DR input signal as in Section IV-D.

Figure 6: Reconstruction of the input signal from one-bit measurements using
UNO Algorithm 2 when the ADC threshold is set to $\lambda=0.5$ and the input
signal amplitude $\left\|\mathbf{x}\right\|_{\infty}$ is (a) $10$, (b) $15$,
and (c) $20$. (d) As in (a) but for $\lambda=1$ and
$\left\|\mathbf{x}\right\|_{\infty}=1000$. The inset shows the same plot on a
larger scale.

###  VI-A Varying ADC Threshold

The number of time-varying sampling thresholds was set to $m=400$. In each
experiment, the generated signals have the same $\mathrm{DR}_{\mathbf{x}}=8$
but the ADC threshold $\lambda$ changes. For a given $\lambda$, the sequences
of time-varying sampling threshold are drawn randomly following the
distribution
$\left\\{\bm{\uptau}^{(\ell)}\sim\mathcal{N}\left(\mathbf{0},\frac{\lambda^{2}}{9}\mathbf{I}\right)\right\\}_{\ell=1}^{m}$.
Fig. 5 illustrates accurate UNO reconstruction for different values of
$\lambda\in\\{0.2,0.5,1\\}$. Table I lists the reconstruction NMSE (on a
$\log_{10}$ scale), averaged over $15$ experiments, for different values of
$\lambda$. We observe that increasing in $\lambda$ leads to higher NMSE
because the volume of the unlimited sampling cube grows further, and
consequently, more hyperplanes may be required to contain a specific volume
around the optimal point in the feasible region.

###  VI-B Varying Input Signal Amplitude

Here, we generated the input signals with varying DRs. In each experiment, the
ADC threshold $\lambda$ was fixed to $\lambda=0.5$, for which we generated
sequences of time-varying sampling threshold as
$\left\\{\bm{\uptau}^{(\ell)}\sim\mathcal{N}\left(\mathbf{0},\frac{1}{36}\mathbf{I}\right)\right\\}_{\ell=1}^{m}$.
Fig. 6 shows accurate UNO reconstruction for different values of
$\left\|\mathbf{x}\right\|_{\infty}$. Table II reports the corresponding NMSE
averaged over $15$ experiments.

Next, we study the reconstruction for a signal with an extremely high DR, with
$\left\|x(t)\right\|_{\infty}=1000$. In theory, the unlimited sampling theorem
guarantees reconstruction with $T\leq\frac{1}{2\Omega_{\textrm{max}}e}$.
However, in practice, signal reconstruction from unlimited samples has its own
limitations due to error propagation by the finite-difference operator.
Specifically, for a large DR of input signal compared to that of the ADC
threshold $\lambda$, the order of difference operator $N$ should also be
large. But a large $N$ would also amplify the quantization/round-off noise,
leading to an unstable reconstruction. In this scenario, more samples (given
by the oversampling factor) are required to decrease $N$. Note that, unlike
conventional ADCs, an abundant number of samples does not lead to an increase
in power consumption, manufacturing cost, and per-bit chip area in one-bit
ADCs. Fig. 6d shows an accurate UNO reconstruction for $\lambda=1$ and a 40
times higher sampling rate $1/T$ than the previous experiments.

Table I: Averaged UNO reconstruction NMSE for fixed $\mathbf{x}$ $\lambda$ | $0.2$ | $0.5$ | $1$
---|---|---|---
$10\log_{10}\operatorname{NMSE}$ | $-72.721$ | $-67.660$ | $-60.987$

Although UNO and one-bit $\Sigma\Delta$ method [51] are different in their
respective theoretical foundations and applications, here we compare their
reconstruction performance for the same signal. The ADC threshold was set to
$\lambda=1$ and sequences of the time-varying sampling threshold were drawn as
$\left\\{\bm{\uptau}^{(\ell)}\sim\mathcal{N}\left(\mathbf{0},\frac{1}{9}\mathbf{I}\right)\right\\}_{\ell=1}^{m}$.
For the specific case of $\left\|\mathbf{x}\right\|_{\infty}=40$, Fig. 7
compares the UNO-reconstructed signal $\bar{\mathbf{x}}$ with the one-bit
unlimited $\Sigma\Delta$-reconstructed signal
$\bar{\mathbf{x}}_{\Sigma\Delta}$ when the ratio between the input signal
amplitude and the ADC threshold
$\eta=\frac{\left\|\mathbf{x}\right\|_{\infty}}{\lambda}$ is large. The one-
bit unlimited $\Sigma\Delta$ degenerates in some parts of the input samples,
while the UNO accurately reconstruct the signal. Table III further compares
the reconstruction NMSE, averaged over $15$ experiments, of both sampling
methods for different amplitudes
$\left\|\mathbf{x}\right\|_{\infty}\in\left\\{20,50\right\\}$. Here, the
degradation in one-bit $\Sigma\Delta$ reconstruction for large $\eta$ is
because of the round-off noise in software and, primarily, imperfect noise
shaping in sigma-delta conversion that results in sample corruption.

Table II: Averaged UNO reconstruction NMSE for $\lambda=0.5$ $\left\|\mathbf{x}\right\|_{\infty}$ | $10$ | $15$ | $20$
---|---|---|---
$10\log_{10}\operatorname{NMSE}$ | $-63.925$ | $-65.820$ | $-63.969$
Figure 7: A comparison of reconstruction via UNO and one-bit unlimited $\Sigma\Delta$ when $\lambda=1$ and $\left\|\mathbf{x}\right\|_{\infty}=40$.  Table III: Reconstruction $10\log_{10}\operatorname{NMSE}$ for $\lambda=1$ $\left\|\mathbf{x}\right\|_{\infty}$ |  One-bit unlimited $\bm{\Sigma}\bm{\Delta}$ | UNO
---|---|---
$20$ | $0.402$ | $-63.969$
$50$ | $3.777$ | $-62.081$

###  VI-C Analysis of Reconstruction Error

To ensure a bounded reconstruction error, the feasible region in (28) cannot
have an infinite volume in an asymptotic sense when amplitude constraints are
imposed by unlimited sampling. As mentioned before, by introducing more
samples, it is possible to obtain a polyhedron with a bounded volume that
contains the desired point. Further, as we illustrated in Fig. 4, adding more
inequality constraints to (28) leads to shrinkage of this polyhedron. We now
prove this result, i.e., in a probabilistic sense, that increasing the number
of samples leads to the reconstruction error approaching zero, and that the
resulting overdetermined linear system of inequalities guarantees the
convergence of RKA [32, 49, 60]. In other words, using an abundant number of
samples (or oversampling in one-bit), the probability of creating the finite-
volume space around the desired point $\tilde{\mathbf{x}}^{\star}$ is
increased.

Define the distance between the optimal solution $\tilde{\mathbf{x}}^{\star}$
and the $j$-th hyperplane of (28) as

$\displaystyle
d_{j}\left(\tilde{\mathbf{x}}^{\star},\bm{\uptau}^{(\ell)}\right)$
$\displaystyle=\left\|\upomega_{j}\left(\tilde{\mathbf{x}}^{\star}-\bm{\uptau}^{(\ell)}\right)\right\|^{2}_{2},\quad
j\in\left\\{1,\cdots,m^{\prime}\right\\},$ (34)

where $\upomega_{j}$ is the $j$-th row of $\tilde{\bm{\Omega}}$. This distance
is also the residual error111In a linear feasibility problem
$\mathbf{C}\mathbf{x}\leq\mathbf{b}$, the _residual error_ is defined as
$\left\|\mathbf{C}\mathbf{x}^{\star}-\mathbf{b}\right\|_{2}^{2}$ [65]. of
(28). Intuitively, it is easy to observe that by reducing the distances
between $\tilde{\mathbf{x}}^{\star}$ and the constraint-associated hyperplanes
generally increases the possibility of capturing the optimal point. For a
specific sample size $m^{\prime}=mn$, when the volume of the finite space
around the optimal point is reduced, the mean
$\left\\{d_{j}\left(\tilde{\mathbf{x}}^{\star},\bm{\uptau}^{(\ell)}\right)\right\\}_{j=1}^{m^{\prime}}$
[49], i.e.,
$T_{\text{ave}}=\frac{1}{m^{\prime}}\sum^{m^{\prime}}_{j=1}d_{j}\left(\tilde{\mathbf{x}}^{\star},\bm{\uptau}^{(\ell)}\right)$,
also decreases. Denote
$D_{\ell}\left(\tilde{\mathbf{x}}^{\star},\bm{\uptau}^{(\ell)}\right)=\left\|\tilde{\mathbf{x}}^{\star}-\bm{\uptau}^{(\ell)}\right\|^{2}_{2}$.
Then, $T_{\text{ave}}$ becomes

$\displaystyle
T_{\text{ave}}=\frac{1}{m^{\prime}}\sum^{m}_{\ell=1}D_{\ell}\left(\tilde{\mathbf{x}}^{\star},\bm{\uptau}^{(\ell)}\right).$
(35)

In the one-bit phase retrieval approach studied in [32], a _Chernoff bound_
was derived to quantify the possibility of creating the above-mentioned
finite-volume and the number of samples required for RKA. We apply this result
below in Theorem 3 to the UNO reconstruction from one-bit samples. Here, we
have replaced the error between the true value signal and the initial value
$\left\|\tilde{\mathbf{x}}_{0}-\tilde{\mathbf{x}}^{\star}\right\|^{2}_{2}$
with the residual error
$\left\|\upomega_{j}\left(\tilde{\mathbf{x}}^{\star}-\bm{\uptau}^{(\ell)}\right)\right\|^{2}_{2}$
in the Chernoff bound. The latter explains the distance between the
hyperplanes and the true value $\mathbf{x}^{\star}$ by including the sampling
threshold sequences into its expression.

######  Theorem 3.

[32, Theorem 1] Assume the distances
$\left\\{d_{j}\left(\tilde{\mathbf{x}}^{\star},\bm{\uptau}^{(\ell)}\right)\right\\}_{j=1}^{m}$
between the desired point $\tilde{\mathbf{x}}^{\star}$ and the hyperplanes of
the polyhedron defined in (28) are independent and identically distributed
random variables. Then,

  1. 1.

The Chernoff bound of $T_{\text{ave}}$ is

$\operatorname{Pr}\left(\frac{1}{m^{\prime}}\sum^{m^{\prime}}_{j=1}d_{j}\left(\tilde{\mathbf{x}}^{\star},\bm{\uptau}^{(\ell)}\right)\leq
a\right)\geq 1-\inf_{t\geq 0}\frac{M_{T}}{e^{ta}},$ (36)

where $a$ is an average distance point in space at which the finite-volume
space around the desired signal is created, and

$M_{T}=\left(1+t\frac{\mu^{(1)}_{d_{j}}}{m^{\prime}}+\cdots+t^{\kappa}\frac{\mu^{(\kappa)}_{d_{j}}}{\kappa!m^{\prime\kappa}}+\mathcal{O}\left(m^{\prime}\right)\right)^{m^{\prime}},$
(37)

is the moment generating function (MGF) of the reconstruction error,
$\mu^{(\kappa)}_{d_{j}}=\mathbb{E}\left\\{d^{\kappa}_{j}\right\\}$, and
$\mathcal{O}\left(m^{\prime}\right)$ denotes the higher-order terms.

  2. 2.

$M_{T}$ decreases with an increase in the sample size leading to an increase
in the lower bound in (36).

Theorem 3 states that the abundant number of samples in conventional one-bit
quantization significantly affect the reconstruction performance of RKA for a
system of linear inequalities in (28). Based on this result, Claim 1 shows the
efficacy of UNO sampling.

######  Claim 1.

Increasing the number of time-varying sampling threshold sequences $m$ is not
an effective approach to guarantee the desired signal reconstruction with RKA
without using unlimited sampling.

###### Proof:

For RKA-based reconstruction in Section IV, assume that we increase the number
of time-varying sampling threshold sequences from $m$ to $m+\kappa$.
Therefore, from (36) of Theorem 3, the Chernoff bound of the reconstruction
error is

$\operatorname{Pr}\left(\frac{1}{(m+\kappa)n}\sum^{(m+\kappa)n}_{j=1}d_{j}\left(\mathbf{x}^{\star},\bm{\uptau}^{(\ell)}\right)\leq
a\right)\geq 1-P_{T},$ (38)

where $P_{T}=\inf_{t\geq 0}\frac{M_{T}}{e^{ta}}$ and
$d_{j}\left(\mathbf{x}^{\star},\bm{\uptau}^{(\ell)}\right)=\left\|\upomega_{j}\left(\mathbf{x}^{\star}-\bm{\uptau}^{(\ell)}\right)\right\|^{2}_{2}$.
Without loss of generality, assume $x_{k}=\text{DR}_{\mathbf{x}}$ for
$x_{k}>0$, and $\delta=x_{k}-\text{DR}_{\bm{\uptau}}$ when
$\text{DR}_{\mathbf{x}}>\text{DR}_{\bm{\uptau}}$. The infimum of the distance
$\frac{1}{(m+\kappa)n}\sum^{(m+\kappa)n}_{j=1}d_{j}\left(\mathbf{x}^{\star},\bm{\uptau}^{(\ell)}\right)$
in (38) occurs when $\tau_{k}^{(\ell)}=\text{DR}_{\bm{\uptau}}$ for
$\ell\in\left\\{1,\cdots,m+\kappa\right\\}$. As a result, this infimum is

$\displaystyle\bar{d}$
$\displaystyle=\inf\left(\frac{1}{(m+\kappa)n}\sum^{(m+\kappa)n}_{j=1}d_{j}\left(\mathbf{x}^{\star},\bm{\uptau}^{(\ell)}\right)\right),$
(39)
$\displaystyle=\inf\left(\frac{1}{(m+\kappa)n}\sum^{(m+\kappa)(n-1)}_{j=1}d_{j}\left(\mathbf{x}^{\star},\bm{\uptau}^{(\ell)}\right)\right)+\frac{(m+\kappa)\delta}{(m+\kappa)n},$
$\displaystyle=\inf\left(\frac{1}{(m+\kappa)n}\sum^{(m+\kappa)(n-1)}_{j=1}d_{j}\left(\mathbf{x}^{\star},\bm{\uptau}^{(\ell)}\right)\right)+\frac{\delta}{n}.$

The term $\frac{\delta}{n}$ in (39) does not depend on the number of time-
varying sampling thresholds $m+\kappa$. In other words, increasing the value
of $m$ does not guarantee the reconstruction of the desired signal in the
polyhedron (7) via the RKA. This phenomenon is also observed in connection to
$P_{T}$. A considerable difference between the signal values and thresholds
leads to larger values of
$\left\\{d_{j}\left(\mathbf{x}^{\star},\bm{\uptau}^{(\ell)}\right)\right\\}$
thereby increasing the moments $\left\\{\mu^{(\kappa)}_{d_{j}}\right\\}$ or
MGF $M_{T}$. Therefore, the dependence of $P_{T}$ on $M_{T}$ is unaffected
when $m$ is increased. ∎

Note that by using the unlimited sampling and imposing amplitude constraints,
the considered distances become bounded and $T_{\text{ave}}$ (35) is
guaranteed to be lower than a small $a$. Then, the volume of the resulting
finite-space will be smaller than that of the cube imposed by unlimited
sampling. In Fig. 8, we show that UNO reconstruction NMSE, averaged over $15$
experiments, significantly improves with the increase in the number of time-
varying threshold sequences $m$. The ADC threshold was set to $\lambda=0.5$
and the signal DR was $\left\|\mathbf{x}\right\|_{\infty}=20$.

Figure 8: Average NMSE for RKA-based UNO reconstruction with respect to the
number of time-varying threshold sequences $m$ for $\lambda=0.5$ and
$\left\|\mathbf{x}\right\|_{\infty}=20$.

######  Remark 1.

According to Theorem 3, when the number of time-varying threshold sequences
$m$ is increased, the reconstruction error
$\mathbf{e}=\left(\tilde{\mathbf{x}}-\bar{\tilde{\mathbf{x}}}\right)$ and
$\|\mathbf{e}\|_{\infty}$ become smaller. We have a smaller lower bound on $h$
defined in (30) and, consequently, a lower sampling rate based on (29). In
other words, a larger $m$ yields a smaller UNO oversampling factor.

##  VII Reconstruction in the Presence of Noise

In the presence of noise, one-bit $\Sigma\Delta$ sampling currently lacks
similar guarantees. In one-bit noisy models of [47, 67], a linear measurement
model with additive Gaussian noise was considered. Then, based on the MLE
formulation for Gaussian likelihood function, the input signal is recovered.
However, in case of non-Gaussian contamination, the MLE objective is nonconvex
and the recovered solution is not unique. Moreover, MLE-based reconstruction
is computationally more complex for high-dimensional signals.

Previously, for unlimited sampling, [18] has shown recovery of noisy
bandlimited samples from their modulo samples up to an unknown additive
constant, where the noise is entry-wise additive to the modulo samples, i.e.,
$\tilde{\mathbf{y}}=\tilde{\mathbf{x}}+\bm{\epsilon}$, and $\bm{\epsilon}$ is
the noise vector. Contrary to this, we propose an approach to reconstruct
unlimited one-bit sampled signal when the noise is additive to the input
signal, which itself has a linear relationship with a desired parameter. This
linear model for the noisy measurement $\mathbf{y}$ is

$\displaystyle\mathbf{y}$ $\displaystyle=\mathbf{x}+\bm{\epsilon},$ (40)
$\displaystyle\mathbf{x}$
$\displaystyle=\mathbf{A}\bm{\uptheta},\quad\mathbf{A}\in\mathbb{R}^{r\times
s},$

where $\bm{\uptheta}$ is the desired parameter vector and the noise follows
the distribution
$\bm{\epsilon}\sim\mathcal{N}\left(0,\sigma^{2}_{\bm{\epsilon}}\mathbf{I}_{m}\right)$.
Here, we may have $\mathbf{y}\notin[-\lambda,\lambda]$. Our goal is to
estimate $\bm{\uptheta}$ from the UNO samples of noisy measurement
$\mathbf{y}$ obtained as

$\displaystyle\mathbf{r}^{(\ell)}=\operatorname{sgn}(\mathcal{M}_{\lambda}\left(\mathbf{y}\right)-\bm{\uptau}^{(\ell)}),\quad\ell\in\mathcal{L}.$
(41)

Our recovery approach comprises using RKA and Algorithm 1 (with N specified by
(55)) to reconstruct noisy measurements from one-bit data, and then exploiting
the PnP-ADMM method to estimate the desired parameters from linear
overdetermined or undetermined systems.

###  VII-A PnP-ADMM-Based UNO Reconstruction

From the UNO samples (41), we reconstruct $\mathbf{y}$ via Algorithm 2. The
reconstructed signal $\bar{\mathbf{y}}$ also follows the linear model (40).
Therefore, we use $\bar{\mathbf{y}}$ to estimate $\bm{\uptheta}$ through the
regularization

$\widehat{\bm{\uptheta}}=\arg\min_{\bm{\uptheta}}\leavevmode\nobreak\
\|\bar{\mathbf{y}}-\mathbf{A}\bm{\uptheta}\|_{2}^{2}+\eta\rho(\bm{\uptheta}),$
(42)

where $\rho(\bm{\uptheta})$ is the penalty term and $\eta>0$ is the real-
valued regularization parameter. There is a rich body of literature to select
the penalty function $\rho(\cdot)$ including the $\ell_{1}$-norm [68],
smoothly clipped absolute deviation (SCAD) [69], adaptive least absolute
shrinkage and selection operator (LASSO) [70] and the minimax-concave (MC)
penalty which has a relationship with Huber functions [71].

One of the standard approaches to solve regularized problems such as in (42)
is ADMM that relies on splitting variables [72]. We consider

$\widehat{\bm{\uptheta}}=\arg\min_{\bm{\uptheta}}\leavevmode\nobreak\
\|\bar{\mathbf{y}}-\mathbf{A}\bm{\uptheta}\|_{2}^{2}+\eta\rho(\upnu)\leavevmode\nobreak\
\text{subject to}\leavevmode\nobreak\ \bm{\uptheta}=\upnu.$ (43)

Using the augmented Lagrangian, we reformulate problem (43) as

$\underset{\bm{\uptheta},\upnu}{\textrm{minimize}}\max_{\mathbf{p}}\left\\{\|\bar{\mathbf{y}}-\mathbf{A}\bm{\uptheta}\|_{2}^{2}+\eta\rho(\upnu)+\mathbf{p}^{\top}(\bm{\uptheta}-\upnu)+\frac{\beta}{2}\|\bm{\uptheta}-\upnu\|^{2}\right\\},$
(44)

where $\mathbf{p}$ is the dual variable and $\beta$ is a real-valued design
parameter. Denote $\mathbf{u}=\frac{\mathbf{p}}{\beta}$. Then,

$\underset{\bm{\uptheta},\upnu}{\textrm{minimize}}\max_{\mathbf{u}}\left\\{\|\bar{\mathbf{y}}-\mathbf{A}\bm{\uptheta}\|_{2}^{2}+\eta\rho(\upnu)+\frac{\beta}{2}\|\bm{\uptheta}-\upnu+\mathbf{u}\|^{2}-\frac{\beta}{2}\|\mathbf{u}\|^{2}\right\\}.$
(45)

The ADMM tackles (45) by alternating the minimization of $\bm{\uptheta}$ and
$\upnu$. The update of $\upnu$ is essentially denoising of
$\bm{\uptheta}_{k}+\mathbf{u}_{k-1}$ by the regularization $\eta\rho(\upnu)$.
This is the key idea behind PnP-ADMM, where the proximal projection

$\upnu_{k}=\arg\min_{\upnu}\left\\{\eta\rho(\upnu)+\frac{\beta}{2}\|\upnu-\bm{\uptheta}_{k}-\mathbf{u}_{k-1}\|^{2}\right\\}$
(46)

is replaced with an appropriate denoiser $\mathcal{D}(.)$. For further details
on various denoisers used in PnP techniques, we refer the interested reader to
[52]. Algorithm 3 summarizes the noisy UNO reconstruction procedure.

Algorithm 3 Noisy UNO algorithm.

1:Input: Sequences of one-bit measurements
$\left\\{\mathbf{r}^{(\ell)}=\operatorname{sgn}\left(\mathcal{M}_{\lambda}\left(\mathbf{y}\right)-\bm{\uptau}^{(\ell)}\right)\right\\}_{\ell=1}^{m}$,
where $\mathbf{y}$ follows (40),
$\bm{\uptau}^{(\ell)}\sim\mathcal{N}\left(\mathbf{0},\sigma^{2}_{\bm{\uptau}}\mathbf{I}\right)$,
ADC threshold $\lambda$, design parameters $\eta$ and $\beta$, total number of
iterations $k_{\textrm{max}}$.

2:Output: The approximation of the parameter of interest
$\widehat{\bm{\uptheta}}$ .

3:$\mathbf{R}\leftarrow\left\\{\mathbf{r}^{(\ell)}\right\\}_{\ell=1}^{m}$.

4:$\sigma_{\bm{\uptau}}\leftarrow\frac{\lambda}{3}$

5:$\bm{\Gamma}\leftarrow\left\\{\bm{\uptau}^{(\ell)}\right\\}_{\ell=1}^{m}$

6:$\bm{\Omega}^{(\ell)}\leftarrow\operatorname{diag}\left(\mathbf{r}^{(\ell)}\right)$

7:$\tilde{\bm{\Omega}}\leftarrow\left[\begin{array}[]{c|c|c}\bm{\Omega}^{(1)}&\cdots&\bm{\Omega}^{(m)}\end{array}\right]^{\top}$

8:$\tilde{\mathcal{P}}\leftarrow\left\\{\bar{\tilde{\mathbf{y}}}\mid\tilde{\bm{\Omega}}\bar{\tilde{\mathbf{y}}}\succeq\operatorname{vec}\left(\mathbf{R}\right)\odot\operatorname{vec}\left(\bm{\Gamma}\right)\right\\}$
$\triangleright$ $\bar{\tilde{\mathbf{y}}}$ reconstructed modulo samples from
RKA.

9:Reconstruct $\bar{\mathbf{y}}$ from $\bar{\tilde{\mathbf{y}}}$ with
Algorithm 1.

10:for $k=1:k_{\textrm{max}}$ do

11:
$\bm{\uptheta}_{k}\leftarrow\min_{\bm{\uptheta}}\left\\{\|\bar{\mathbf{y}}-\mathbf{A}\bm{\uptheta}\|_{2}^{2}+\frac{\beta}{2}\|\bm{\uptheta}-\upnu_{k-1}+\mathbf{u}_{k-1}\|^{2}\right\\}$.

12:
$\upnu_{k}\leftarrow\mathcal{D}\left(\bm{\uptheta}_{k}+\mathbf{u}_{k-1}\right).$

13: $\mathbf{u}_{k}\leftarrow\mathbf{u}_{k-1}+\bm{\uptheta}_{k}-\upnu_{k}$.

14:return $\widehat{\bm{\uptheta}}\leftarrow\bm{\uptheta}_{k_{\textrm{max}}}$.

###  VII-B ADC Threshold Selection in Noisy UNO

Theorem 4 certifies that the additive noise to the input signal results in an
additive noise in modulo domain.

######  Theorem 4.

Assume the noise vector in the measurement model
$\mathbf{y}=\mathbf{x}+\mathbf{z}$ to be
$\mathbf{z}=\left[z_{k}\right]\sim\mathcal{N}\left(0,\sigma^{2}_{\mathbf{z}}\mathbf{I}_{m}\right)$.
Denote $\tilde{\mathbf{x}}=\mathcal{M}_{\lambda}\left(\mathbf{x}\right)$ and
$\tilde{\mathbf{z}}=\left[\tilde{z}_{k}\right]$,
$\tilde{z}_{k}=\operatorname{mod}\left(z_{k},2\lambda\right)-2(1-q_{k})\lambda$,
$q_{k}\in\\{0,1\\}$. Then,

$\tilde{\mathbf{y}}=\tilde{\mathbf{x}}+\tilde{\mathbf{z}},$ (47)

where $\tilde{\mathbf{y}}=\mathcal{M}_{\lambda}\left(\mathbf{y}\right)$.

###### Proof:

Applying the modulo operator $\mathcal{M}_{\lambda}$ in (8) to the noisy
measurements $\mathbf{y}$ produces

$\displaystyle\tilde{\mathbf{y}}$
$\displaystyle=\mathcal{M}_{\lambda}\left(\mathbf{y}\right)=\mathcal{M}_{\lambda}\left(\mathbf{x}+\mathbf{z}\right)$
(48)
$\displaystyle=\mathbf{x}+\mathbf{z}-2\lambda\left\lfloor\frac{\mathbf{x}}{2\lambda}+\frac{1}{2}+\frac{\mathbf{z}}{2\lambda}\right\rfloor,$

where
$\mathbf{z}\sim\mathcal{N}\left(0,\sigma^{2}_{\mathbf{z}}\mathbf{I}_{m}\right)$.
Since we have $\left\lfloor a+b\right\rfloor\geq\left\lfloor
a\right\rfloor+\left\lfloor b\right\rfloor$ for two arbitrary real numbers $a$
and $b$, it follows from (48) that

$\displaystyle\mathcal{M}_{\lambda}\left(\mathbf{x}+\mathbf{z}\right)$
$\displaystyle=\mathbf{x}+\mathbf{z}-2\lambda\left\lfloor\frac{\mathbf{x}}{2\lambda}+\frac{1}{2}+\frac{\mathbf{z}}{2\lambda}\right\rfloor$
(49)
$\displaystyle\leq\mathbf{x}-2\lambda\left\lfloor\frac{\mathbf{x}}{2\lambda}+\frac{1}{2}\right\rfloor+\mathbf{z}-2\lambda\left\lfloor\frac{\mathbf{z}}{2\lambda}\right\rfloor$
$\displaystyle=\tilde{\mathbf{x}}+\mathbf{z}-2\lambda\left\lfloor\frac{\mathbf{z}}{2\lambda}\right\rfloor=\tilde{\mathbf{x}}+\operatorname{mod}\left(\mathbf{z},2\lambda\right).$

Using the identity $\left\lfloor a+b\right\rfloor\leq\left\lfloor
a\right\rfloor+\left\lfloor b\right\rfloor+1$, we obtain

$\mathcal{M}_{\lambda}\left(\mathbf{x}+\mathbf{z}\right)\geq\tilde{\mathbf{x}}+\operatorname{mod}\left(\mathbf{z},2\lambda\right)-2\lambda.$
(50)

A binary combination of the right-hand sides of (49) and (50) is equivalent to
$\mathcal{M}_{\lambda}\left(x_{k}+z_{k}\right)$, i.e.,

$\displaystyle\tilde{y}_{k}$
$\displaystyle=\mathcal{M}_{\lambda}\left(x_{k}+z_{k}\right)$ (51)
$\displaystyle=q_{k}\left(\tilde{x}_{k}+\operatorname{mod}\left(z_{k},2\lambda\right)\right)+(1-q_{k})\left(\tilde{x}_{k}+\operatorname{mod}\left(z_{k},2\lambda\right)-2\lambda\right),$
$\displaystyle=\tilde{x}_{k}+\operatorname{mod}\left(z_{k},2\lambda\right)-2(1-q_{k})\lambda,$

where $q_{k}\in\\{0,1\\}$. Rewrite (51) as

$\tilde{y}_{k}=\tilde{x}_{k}+\tilde{z}_{k},$ (52)

where
$\tilde{z}_{k}=\operatorname{mod}\left(z_{k},2\lambda\right)-2(1-q_{k})\lambda$,
which completes the proof. ∎

It follows from Theorem 4 that the noise corruption in the input signal
carries over to the modulo samples. The following theorem unveils the UNO
reconstruction guarantee in the presence of noise.

Figure 9: Reconstruction of the desired parameter vector $\bm{\theta}$
following the linear model (40) using PnP-ADMM-based UNO for an (a)
overdetermined system with $\mathbf{A}\in\mathbb{R}^{728\times 100}$ and (b)
underdetermined system with $\mathbf{A}\in\mathbb{R}^{728\times 1000}$. Here,
to facilitate a better visual presentation, the number of threshold sequences
start from $m=500$. (c) Reconstruction of the noisy input signal from one-bit
measurements using PnP-ADMM-based UNO.

######  Theorem 5.

(UNO sampling with noise) Assume $x(t)$ to be a finite energy, bandlimited
signal with maximum frequency $\Omega_{\textrm{max}}$. Let $y(t)$ denote the
noisy signal following a linear model $y(t)=x(t)+z(t)$, where $z(t)$ denotes
the additive noise signal. Denote the pre-filtered $y(t)$, $x(t)$ and $z(t)$
by, respectively, $y_{\phi}(t)$, $x_{\phi}(t)$ and $z_{\phi}(t)$, where
$\phi\in\textrm{PW}_{\Omega}$ with cut-off frequency $\Omega_{\textrm{max}}$
following a linear model $y_{\phi}(t)=x_{\phi}(t)+z_{\phi}(t)$. Denote the
samples of $y_{\phi}(t)$, $x_{\phi}(t)$, $z_{\phi}(t)$ and the modulo samples
of $y_{\phi}(t)$ by, respectively, $\left(y_{\phi}\right)_{k}$,
$\left(x_{\phi}\right)_{k}$, $\left(z_{\phi}\right)_{k}$ and
$\left(\tilde{y}_{\phi}\right)_{k}$, where the sampling rate is $1/T$. The
modulo samples reconstructed by the RKA are denoted by
$\bar{\tilde{\mathbf{y}}}_{\phi}$ with the reconstruction error is
$\mathbf{e}=\left(\bar{\tilde{\mathbf{y}}}_{\phi}-\tilde{\mathbf{y}}_{\phi}\right)$.
Then, the sufficient condition to reconstruct bandlimited samples $x_{k}$ from
UNO samples
$\left\\{\mathbf{r}^{(\ell)}=\operatorname{sgn}\left(\mathcal{M}_{\lambda}\left(\mathbf{y}_{\phi}\right)-\bm{\uptau}^{(\ell)}\right)\right\\}_{\ell=1}^{m}$,
where
$\bm{\uptau}^{(\ell)}\sim\mathcal{N}\left(\mathbf{0},\frac{\lambda^{2}}{9}\mathbf{I}\right)$,
up to additive multiples of $2\lambda$ in the sense that
$\left(\bar{\tilde{y}}_{\phi}\right)_{k}=x_{k}+\left(\tilde{z}_{\phi}\right)_{k}+e_{k}$
is

$T\leq\frac{1}{2^{h}\Omega_{\textrm{max}}e},$ (53)

where $\left(\tilde{z}_{\phi}\right)_{k}$ is defined in Theorem 4 and
$h\in\mathbb{N}$ is determined by

$h\geq\frac{\log\left(\frac{2\beta_{x}}{\lambda}\right)}{\log\left(\frac{\lambda}{4\left\|\tilde{\mathbf{z}}_{\phi}+\mathbf{e}\right\|_{\infty}}\right)},$
(54)

with

$\lambda\geq
4\zeta\left\|\tilde{\mathbf{z}}_{\phi}+\mathbf{e}\right\|_{\infty},\quad\zeta>1.$
(55)

###### Proof:

The proof, ceteris paribus, follows from repeating the proof of Theorem 2 by
replacing the RKA error $\mathbf{e}$ with
$\tilde{\mathbf{z}}_{\phi}+\mathbf{e}$. ∎

According to Theorem 5, noisy UNO sampling requires more samples (given by the
oversampling factor) specified by (53) than the noiseless case in (29). This
is similar to other conventional noisy samplers. For example, Cadzow denoising
[73], used to suppress the effect of noise in sparse samplers similarly
requires such an oversampling [74].

###  VII-C Numerical Examples

We investigated PnP-ADMM-based noisy UNO reconstruction with
$\mathbf{A}=\left[a_{ij}\right]$ to be $a_{ij}\sim\mathcal{N}\left(0,1\right)$
and $\mathbf{y}=\mathbf{y}_{t}+\bm{\epsilon}$, where $\mathbf{y}_{t}$ was
generated as in Section IV-D and
$\bm{\epsilon}\sim\mathcal{N}\left(\mathbf{0},\sigma^{2}_{\bm{\epsilon}}\mathbf{I}_{m}\right)$.
Fig. 9a and b show accurate noisy UNO reconstruction of the parameter vector
with fixed $\sigma^{2}_{\bm{\epsilon}}=0.1$ in case of, respectively,
overdetermined ($r=728$, $s=100$) and underdetermined ($r=728$, $s=1000$)
systems in (40). Fig. 9c demonstrates the efficacy of Noisy UNO in estimating
the desired parameter $\bm{\uptheta}$ from (40) when only UNO samples of noisy
measurement $\mathbf{y}$ are available.

Table IV reports the reconstruction NMSE of $\theta$, i.e.,
$\operatorname{NMSE}_{\bm{\uptheta}}\triangleq\frac{\left\|\bm{\uptheta}-\widehat{\bm{\uptheta}}\right\|_{2}^{2}}{\left\|\bm{\uptheta}\right\|_{2}^{2}}$,
averaged over $15$ experiments for different noise variances
$\sigma^{2}_{\bm{\epsilon}}\in\left\\{0.01,0.05,0.1\right\\}$ using the PnP-
ADMM-based UNO. Here, following Theorem 5, the ADC threshold was set to
$\lambda=1.5$.

Table IV: Reconstruction $10\log_{10}\operatorname{NMSE}_{\bm{\uptheta}}$ with PnP-ADMM Noisy UNO $\sigma^{2}_{\bm{\epsilon}}$ | Overdetermined system | Underdetermined system
---|---|---
$0.1$ | $-48.294$ | $-38.128$
$0.05$ | $-52.676$ | $-42.347$
$0.01$ | $-56.815$ | $-45.259$

##  VIII Summary

The design of alternative sampling schemes to enable practical implementations
of Shannon’s theorem – from theory to praxis – has been an active research
topic for decades. In this context, our proposed UNO presents a framework of
merging one-bit quantization and unlimited sampling. This sampling framework
naturally facilitates a judicious design of time-varying sampling thresholds
by properly utilizing the information on the distance between the signal
values and the thresholds in a high DR regime. The noiseless UNO
reconstruction relies on exploiting RKA algorithm while the noisy
reconstruction is based on the PnP-ADMM heuristic. These low-complexity
approaches are preferable over existing costly reconstruction optimization
approaches [52, 53].

The UNO framework achieves multiple objectives of high sampling rate,
unlimited DR, less complex and potentially low-power implementations. Our
numerical and theoretical analyses demonstrate accurate reconstruction for
several different scenarios. Some theoretical questions remain open, e.g. on
the relationship between the number of threshold sequences $m$ and
reconstruction error in a closed form. This may help in finding the required
number of thresholds sequences for perfect reconstruction. Further, a hardware
verification of UNO on the lines of unlimited sampling in [43] is also
desired.

## Acknowledgement

The authors are grateful to Prof. Ayush Bhandari of Imperial College, London
for helpful discussions related to his work in [51] and for providing the
relevant source codes to facilitate meaningful comparison.

## References

  * [1] A. Cauchy, “Memoire sur diverses formules d’analyse,” _Comptes Rendus de l’Académie des Sciences_ , vol. 12, no. 283, pp. 63–78, 1841, in French.
  * [2] C.-J. de La Vallée Poussin, “Sur la convergence des formules d’interpolation entre ordonnées equidistantes,” _Bulletins de l’Academie Royale des Sciences, des Lettres et des Beaux Arts de Belgique_ , vol. 4, p. 319–403, 1908, in French.
  * [3] E. T. Whittaker, “On the functions which are represented by the expansion of interpolating theory,” _Proceedings of the Royal Society_ , vol. 35, pp. 181–194, 1915.
  * [4] K. Ogura, “On a certain transcendental integral function in the theory of interpolation,” _Tohoku Mathematical Journal, First Series_ , vol. 17, pp. 64–72, 1920.
  * [5] V. A. Kotelńikov, “On the transmission capacity of “ether” and wire in electrocommunications,” in _Material for the First All-Union Conference on Questions of Communication_ , 1933, in Russian.
  * [6] H. Raabe, “Untersuchungen an der wechselzeitigen mehrfachübertragung (multiplexübertragung),” Ph.D. dissertation, TH Berlin, 1939, in German.
  * [7] C. E. Shannon, “Communication in the presence of noise,” _Proceedings of the IRE_ , vol. 37, no. 1, pp. 10–21, 1949.
  * [8] I. Someya, _Waveform transmission_. Shyukyo Ltd., Tokyo, 1949.
  * [9] A. J. Jerri, “The Shannon sampling theorem – Its various extensions and applications: A tutorial review,” _Proceedings of the IEEE_ , vol. 65, no. 11, pp. 1565–1596, 1977.
  * [10] J. A. Hogan and J. D. Lakey, _Duration and bandwidth limiting: Prolate functions, sampling, and applications_. Springer, 2012.
  * [11] G. E. Pfander, _Sampling theory, a renaissance: Compressive sensing and other developments_. Springer, 2015.
  * [12] T. Kailath, “An application of shannon’s rate-distortion theory to analog communication over feedback channels,” _Proceedings of the IEEE_ , vol. 55, no. 6, pp. 1102–1103, 1967.
  * [13] T. Berger, “Rate-distortion theory,” in _Wiley Encyclopedia of Telecommunications_ , J. G. Proakis, Ed. Wiley Online Library, 2003.
  * [14] T. Olofsson, “Deconvolution and model-based restoration of clipped ultrasonic signals,” _IEEE Transactions on Instrumentation and Measurement_ , vol. 54, no. 3, pp. 1235–1240, 2005.
  * [15] A. Adler, V. Emiya, M. G. Jafari, M. Elad, R. Gribonval, and M. Plumbley, “Audio inpainting,” _IEEE Transactions on Audio, Speech, and Language Processing_ , vol. 20, no. 3, pp. 922–932, 2011.
  * [16] J. S. Abel, “Restoring a clipped signal,” in _IEEE International Conference On Acoustics, Speech, and Signal Processing_ , 1991, pp. 1745–1748.
  * [17] S. Ting and A. H. Sayed, “Mitigation of clipping in sensors,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2013, pp. 5934–5938.
  * [18] A. Bhandari, F. Krahmer, and R. Raskar, “On unlimited sampling and reconstruction,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 3827–3839, 2020.
  * [19] F. Esqueda, S. Bilbao, and V. Välimäki, “Aliasing reduction in clipped signals,” _IEEE Transactions on Signal Processing_ , vol. 64, no. 20, pp. 5255–5267, 2016.
  * [20] V. Gregers-Hansen, S. M. Brockett, and P. E. Cahill, “A stacked A-to-D converter for increased radar signal processor dynamic range,” in _IEEE Radar Conference_ , 2001, pp. 169–174.
  * [21] D. Prasanna, C. R. Murthy, and C. Sriram, “On the application of modulo-ADCs for compressed sensing,” in _Asilomar Conference on Signals, Systems, and Computers_ , 2021, pp. 852–856.
  * [22] A. Bhandari, F. Krahmer, and R. Raskar, “On unlimited sampling,” in _IEEE International Conference on Sampling Theory and Applications_ , 2017, pp. 31–35.
  * [23] S. Rudresh, A. Adiga, B. Shenoy, and C. S. Seelamantula, “Wavelet-based reconstruction for unlimited sampling,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2018, pp. 4584–4588.
  * [24] A. Ameri, J. Li, and M. Soltanalian, “One-bit radar processing and estimation with time-varying sampling thresholds,” in _IEEE Sensor Array and Multichannel Signal Processing Workshop_ , 2018, pp. 208–212.
  * [25] D. K. W. Ho and B. D. Rao, “Antithetic dithered 1-bit massive MIMO architecture: Efficient channel estimation via parameter expansion and PML,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 9, pp. 2291–2303, 2019.
  * [26] T. Kugelstadt, “Active filter design techniques,” in _Op Amps for Everyone Literature Number SLOD006A_ , R. Mancini, Ed. Texas Instruments, 2002.
  * [27] 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.
  * [28] 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.
  * [29] S. Sedighi, B. Shankar, M. Soltanalian, and B. Ottersten, “One-bit DoA estimation via sparse linear arrays,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2020, pp. 9135–9139.
  * [30] C. Qian and J. Li, “ADMM for harmonic retrieval from one-bit sampling with time-varying thresholds,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2017, pp. 3699–3703.
  * [31] 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.
  * [32] 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.
  * [33] 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.
  * [34] 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.
  * [35] 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.
  * [36] S. Sedighi, K. V. Mishra, M. B. Shankar, and B. Ottersten, “Localization with one-bit passive radars in narrowband internet-of-things using multivariate polynomial optimization,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 2525–2540, 2021.
  * [37] A. Bhandari, F. Krahmer, and R. Raskar, “Unlimited sampling of sparse signals,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2018, pp. 4569–4573.
  * [38] F. Ji, P. Pratibha, and W. P. Tay, “On folded graph signals,” in _IEEE Global Conference on Signal and Information Processing_ , 2019, pp. 1–5.
  * [39] S. Fernández-Menduina, F. Krahmer, G. Leus, and A. Bhandari, “DoA estimation via unlimited sensing,” in _European Signal Processing Conference_ , 2021, pp. 1866–1870.
  * [40] A. Bhandari, “Unlimited sampling with sparse outliers: Experiments with impulsive and jump or reset noise,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2022, pp. 5403–5407.
  * [41] O. Musa, P. Jung, and N. Goertz, “Generalized approximate message passing for unlimited sampling of sparse signals,” in _IEEE Global Conference on Signal and Information Processing_ , 2018, pp. 336–340.
  * [42] D. Florescu and A. Bhandari, “Unlimited sampling with local averages,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2022, pp. 5742–5746.
  * [43] A. Bhandari, F. Krahmer, and T. Poskitt, “Unlimited sampling from theory to practice: Fourier-Prony recovery and prototype ADC,” _IEEE Transactions on Signal Processing_ , vol. 70, pp. 1131–1141, 2021.
  * [44] M. Beckmann, F. Krahmer, and A. Bhandari, “HDR tomography via modulo Radon transform,” in _IEEE International Conference on Image Processing_ , 2020, pp. 3025–3029.
  * [45] D. Florescu, F. Krahmer, and A. Bhandari, “Unlimited sampling with hysteresis,” in _Asilomar Conference on Signals, Systems, and Computers_ , 2021, pp. 831–835.
  * [46] S. Khobahi and M. Soltanalian, “Signal recovery from 1-bit quantized noisy samples via adaptive thresholding,” in _Asilomar Conference on Signals, Systems, and Computers_ , 2018, pp. 1757–1761.
  * [47] A. Zymnis, S. Boyd, and E. Candes, “Compressed sensing with quantized measurements,” _IEEE Signal Processing Letters_ , vol. 17, no. 2, pp. 149–152, 2009.
  * [48] 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.
  * [49] 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.
  * [50] S. Kaczmarz, “Angenäherte auflösung von systemen linearer gleichungen,” _Bulletin International de l’Académie Polonaise des Sciences et des Lettres_ , vol. 35, p. 355–357, 1937, in German; English translation by Jason Stockmann: “Approximate solution of systems of linear equations”.
  * [51] O. Graf, A. Bhandari, and F. Krahmer, “One-bit unlimited sampling,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2019, pp. 5102–5106.
  * [52] S. Venkatakrishnan, C. Bouman, and B. Wohlberg, “Plug-and-play priors for model based reconstruction,” in _Global Conference on Signal and Information Processing_ , 2013, pp. 945–948.
  * [53] S. Chan, X. Wang, and O. Elgendy, “Plug-and-Play ADMM for image restoration: Fixed-point convergence and applications,” _IEEE Transactions on Computational Imaging_ , vol. 3, no. 1, pp. 84–98, 2016.
  * [54] S. J. Zahabi, M. M. Naghsh, M. Modarres-Hashemi, and J. Li, “One-bit compressive radar sensing in the presence of clutter,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 56, no. 1, pp. 167–185, 2020.
  * [55] K. Knudson, R. Saab, and R. Ward, “One-bit compressive sensing with norm estimation,” _IEEE Transactions on Information Theory_ , vol. 62, no. 5, pp. 2748–2758, 2016.
  * [56] S. Khobahi and M. Soltanalian, “Model-based deep learning for one-bit compressive sensing,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 5292–5307, 2020.
  * [57] H. Zhu, X. Shang, and J. Li, “Target parameter estimation via one-bit PMCW radar,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2020, pp. 9145–9149.
  * [58] N. Cassidy and H. Jol, “Ground penetrating radar data processing, modelling and analysis,” in _Ground Penetrating Radar: Theory and Applications_ , H. M. Jol, Ed. Elsevier Science, 2009, pp. 141–176.
  * [59] J. Zhang, J. Hao, X. Zhao, S. Wang, L. Zhao, W. Wang, and Z. Yao, “Restoration of clipped seismic waveforms using projection onto convex sets method,” _Scientific Reports_ , vol. 6, no. 1, pp. 1–10, 2016.
  * [60] J. Briskman and D. Needell, “Block Kaczmarz method with inequalities,” _Journal of Mathematical Imaging and Vision_ , vol. 52, no. 3, pp. 385–396, 2015.
  * [61] L. Dai, M. Soltanalian, and K. Pelckmans, “On the randomized Kaczmarz algorithm,” _IEEE Signal Processing Letters_ , vol. 21, no. 3, pp. 330–333, 2013.
  * [62] A. Ma, D. Needell, and A. Ramdas, “Convergence properties of the randomized extended Gauss–Seidel and Kaczmarz methods,” _SIAM Journal on Matrix Analysis and Applications_ , vol. 36, no. 4, pp. 1590–1604, 2015.
  * [63] B. Polyak, “Gradient methods for solving equations and inequalities,” _USSR Computational Mathematics and Mathematical Physics_ , vol. 4, no. 6, pp. 17–32, 1964.
  * [64] A. Edelman, “On the distribution of a scaled condition number,” _Mathematics of computation_ , vol. 58, no. 197, pp. 185–190, 1992.
  * [65] C. Van Loan and G. Golub, _Matrix computations_. The Johns Hopkins University Press, 1996.
  * [66] M. G. Kendall, A. Stuart, and J. Ord, _Kendall’s advanced theory of statistics_. Oxford University Press, 1987\.
  * [67] S. Khobahi and M. Soltanalian, “Model-based deep learning for one-bit compressive sensing,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 5292–5307, 2020.
  * [68] R. Tibshirani, “Regression shrinkage and selection via the LASSO,” _Journal of the Royal Statistical Society: Series B (Methodological)_ , vol. 58, no. 1, pp. 267–288, 1996.
  * [69] J. Fan and R. Li, “Variable selection via nonconcave penalized likelihood and its oracle properties,” _Journal of the American statistical Association_ , vol. 96, no. 456, pp. 1348–1360, 2001.
  * [70] H. Zou, “The adaptive LASSO and its oracle properties,” _Journal of the American statistical association_ , vol. 101, no. 476, pp. 1418–1429, 2006\.
  * [71] I. Selesnick, “Sparse regularization via convex analysis,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 17, pp. 4481–4494, 2017.
  * [72] S. Boyd, N. Parikh, and E. Chu, _Distributed optimization and statistical learning via the alternating direction method of multipliers_. Now Publishers Inc, 2011.
  * [73] J. A. Cadzow, “Signal enhancement – A composite property mapping algorithm,” _IEEE Transactions on Acoustics, Speech, and Signal Processing_ , vol. 36, no. 1, pp. 49–62, 1988.
  * [74] S. Rudresh and C. S. Seelamantula, “Finite-rate-of-innovation-sampling-based super-resolution radar imaging,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 19, pp. 5021–5033, 2017.