Sample abundance

Short description: Signal-processing paradigm that trades precision for volume of measurements

Sample abundance is a signal processing paradigm in which very large numbers of low-precision measurements—often one-bit samples produced by comparators with time-varying thresholds—are leveraged to recover signals or parameters with high fidelity and reduced computational cost. Instead of enforcing difficult constraints (e.g., positive-semidefiniteness or low rank) during reconstruction, many problems under sample abundance are reformulated as overdetermined linear feasibility tasks defined by half-space inequalities. With sufficiently many binary measurements, these inequalities confine the solution to a small polyhedral region around the ground truth, making formerly essential constraints unnecessary. Beyond a critical number of samples, the algorithmic load collapses suddenly—a phenomenon that may be referred to as the sample abundance singularity.

Conceptual illustration of a one-bit polyhedron (black lines) formed by half-spaces from binary comparisons. As samples increase, the feasible region shrinks around the true solution (purple) and can lie entirely inside a broader constraint set (orange).

Background

One-bit and few-bit analog-to-digital converters (ADCs) are attractive in applications such as massive MIMO and radar because comparators are inexpensive, fast, and power-efficient. Introducing dither or time-varying thresholds allows binary signs to retain sufficient statistical information for estimation, including covariance and spectrum recovery via generalized arcsine-law results. Hybrid architectures such as Unlimited One-Bit Sampling (UNO) combine modulo folding with one-bit thresholds to further increase dynamic range while retaining low hardware cost. Related efforts span low-resolution MIMO channel estimation and radar processing with binary data.

Definition

Let a one-bit sample be obtained by comparing a measurement $y_k$ with a threshold ${\tau }_k$: $r_k=\mathrm{sgn}(y_k-{\tau }_k)\in \{-1,+1\}.$ Each observation yields the linear inequality $r_k(y_k-{\tau }_k)\ge 0$. Stacking many samples and writing $\mathbf{𝐲}=\mathbf{𝐀}\mathbf{𝐱}$ for linear sensing gives the one-bit polyhedron:

${{𝒫}}_{\mathbf{𝐱}}=\{\mathbf{𝐱}\in {\mathbb{ℝ}}^d\mid \mathbf{𝐏}\mathbf{𝐱}⪰\mathbf{𝐛}\}$,

where $\mathbf{𝐏}$ collects signed rows of $\mathbf{𝐀}$ and $\mathbf{𝐛}$ stacks the threshold terms. Under sample abundance (many more inequalities than unknowns), ${{𝒫}}_{\mathbf{𝐱}}$ typically has finite volume near the ground truth and shrinks as more samples are added.

Sample abundance singularity

The sample abundance singularity refers to the observed regime change in which, after a problem-dependent measurement threshold is exceeded, computational requirements collapse from non-convex or constrained programs (e.g., semidefinite or rank-constrained formulations) to simple projections onto linear half-spaces. In this regime, enforcing positive semidefiniteness, rank, or sparsity may become unnecessary because the polyhedral feasible set already localizes the solution to within the desired accuracy.

Mathematical formulation and examples

Phase retrieval

With quadratic measurements known only through one-bit comparisons to thresholds, each binary sample imposes an inequality in the lifted variable $\mathbf{𝐗}=\mathbf{𝐱}{\mathbf{𝐱}}^{\mathrm{\top }}$: $r_j^{(\ell )}{\mathbf{𝐚}}_j^{\mathrm{\top }}\mathbf{𝐗}{\mathbf{𝐚}}_j\ge r_j^{(\ell )}{\tau }_j^{(\ell )}.$ Beyond ample sampling, explicit PSD and rank-one constraints used by semidefinite programs (e.g., PhaseLift) can be omitted in practice.

Low-rank matrix sensing

For linear measurements $y_j=\mathrm{Tr}({\mathbf{𝐀}}_j^{\mathrm{\top }}\mathbf{𝐗})$, one-bit signs $r_j^{(\ell )}=\mathrm{sgn}(y_j-{\tau }_j^{(\ell )})$ define a polyhedron in the matrix space; with abundant samples, nuclear-norm or rank constraints can become optional to enforce.

Compressed sensing

Given $\mathbf{𝐲}=\mathbf{𝐀}\mathbf{𝐱}$ and signs $r_j^{(\ell )}=\mathrm{sgn}(⟨{\mathbf{𝐚}}_j,\mathbf{𝐱}⟩-{\tau }_j^{(\ell )})$, the feasible set

${{𝒫}}_{\mathbf{𝐱}}^{(C)}=\{{\mathbf{𝐱}}^{\prime }\in {\mathbb{ℝ}}^n\mid r_j^{(\ell )}⟨{\mathbf{𝐚}}_j,{\mathbf{𝐱}}^{\prime }⟩\ge r_j^{(\ell )}{\tau }_j^{(\ell )}\}$

can localize a sparse vector without explicit ${\ell }_1$ minimization when many binary comparisons are available.

Algorithms

Because sample abundance yields overdetermined systems of linear inequalities, projection methods are natural. The Randomized Kaczmarz Algorithm (RKA) selects a row at random and projects the iterate; for consistent systems it converges linearly in expectation at a rate governed by a scaled condition number. The Sampling Kaczmarz–Motzkin (SKM) method draws a mini-batch of rows, chooses the most violated constraint, and projects, often accelerating convergence on large systems. Unrolled and plug-and-play variants tailored to one-bit data have also been reported for speed and robustness.

Finite volume property

The Finite Volume Property (FVP) provides sample-complexity bounds ensuring that the polyhedron formed by one-bit inequalities has small volume (e.g., lies inside an $\epsilon$-ball around the truth). For isotropic measurements, one set of results implies that

$m=O({\epsilon }^{-3})$ samples yield error $O(m^{-1/3})$,

with improved $O({\epsilon }^{-2})$ scaling when the signal belongs to structured sets (e.g., sparse vectors or low-rank matrices) whose Kolmogorov entropies are smaller. These guarantees help explain why explicit PSD, rank, or sparsity constraints can become redundant once the number of binary comparisons exceeds a problem-dependent threshold.

Applications

• Low-resolution receivers in massive MIMO communications and detection.

• Radar and automotive sensing, including covariance-based DOA and one-bit Hankel matrix completion.

• Unlimited/one-bit sampling for bandlimited and finite-rate-of-innovation signals, and HDR imaging with sweeping thresholds.

See also

• Kaczmarz method

• Compressed sensing

• Phase retrieval

• Quantization (signal processing)