  One-bit quantization with time-varying sampling thresholds (also known as
random dithering) has recently found significant utilization potential in
statistical signal processing applications due to its relatively low power
consumption and low implementation cost. In addition to such advantages, an
attractive feature of one-bit analog-to-digital converters (ADCs) is their
superior sampling rates as compared to their conventional multi-bit
counterparts. This characteristic endows one-bit signal processing frameworks
with what one may refer to as sample abundance. We show that sample abundance
plays a pivotal role in many signal recovery and optimization problems that are
formulated as (possibly non-convex) quadratic programs with linear feasibility
constraints. Of particular interest to our work are low-rank matrix recovery
and compressed sensing applications that take advantage of one-bit
quantization. We demonstrate that the sample abundance paradigm allows for the
transformation of such problems to merely linear feasibility problems by
forming large-scale overdetermined linear systems -- thus removing the need for
handling costly optimization constraints and objectives. To make the proposed
computational cost savings achievable, we offer enhanced randomized Kaczmarz
algorithms to solve these highly overdetermined feasibility problems and
provide theoretical guarantees in terms of their convergence, sample size
requirements, and overall performance. Several numerical results are presented
to illustrate the effectiveness of the proposed methodologies.
