Sample abundance

This article is about the signal-processing concept. For the ecological concept, see Species abundance.

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.^[1] 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.^[2]

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.^[3][4] 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.^[5] Related efforts span low-resolution MIMO channel estimation and radar processing with binary data.^[6][7]

Definition

Let a one-bit sample be obtained by comparing a measurement ${\displaystyle y_{k}}$ with a threshold ${\displaystyle \tau _{k}}$: ${\displaystyle r_{k}=\operatorname {sgn} (y_{k}-\tau _{k})\in \{-1,+1\}.}$ Each observation yields the linear inequality ${\displaystyle r_{k}(y_{k}-\tau _{k})\geq 0}$. Stacking many samples and writing ${\displaystyle \mathbf {y} =\mathbf {A} \mathbf {x} }$ for linear sensing gives the one-bit polyhedron:

${\displaystyle {\mathcal {P}}_{\mathbf {x} }=\{\ \mathbf {x} \in \mathbb {R} ^{d}\mid \mathbf {P} \mathbf {x} \succeq \mathbf {b} \ \}}$,

where ${\displaystyle \mathbf {P} }$ collects signed rows of ${\displaystyle \mathbf {A} }$ and ${\displaystyle \mathbf {b} }$ stacks the threshold terms. Under sample abundance (many more inequalities than unknowns), ${\displaystyle {\mathcal {P}}_{\mathbf {x} }}$ typically has finite volume near the ground truth and shrinks as more samples are added.^[1]

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.^[8][1]

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 ${\displaystyle \mathbf {X} =\mathbf {x} \mathbf {x} ^{\top }}$: ${\displaystyle r_{j}^{(\ell )}\mathbf {a} _{j}^{\top }\mathbf {X} \mathbf {a} _{j}\geq 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.^[8][9]

Low-rank matrix sensing

For linear measurements ${\displaystyle y_{j}=\operatorname {Tr} (\mathbf {A} _{j}^{\top }\mathbf {X} )}$, one-bit signs ${\displaystyle r_{j}^{(\ell )}=\operatorname {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.^[10]

Compressed sensing

Given ${\displaystyle \mathbf {y} =\mathbf {A} \mathbf {x} }$ and signs ${\displaystyle r_{j}^{(\ell )}=\operatorname {sgn} (\langle \mathbf {a} _{j},\mathbf {x} \rangle -\tau _{j}^{(\ell )})}$, the feasible set

${\displaystyle {\mathcal {P}}_{\mathbf {x} }^{(C)}=\{\ \mathbf {x} '\in \mathbb {R} ^{n}\mid r_{j}^{(\ell )}\langle \mathbf {a} _{j},\mathbf {x} '\rangle \geq r_{j}^{(\ell )}\tau _{j}^{(\ell )}\ \}}$

can localize a sparse vector without explicit ${\displaystyle \ell _{1}}$ minimization when many binary comparisons are available.^[11][12]

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.^[13][14] 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.^[15] Unrolled and plug-and-play variants tailored to one-bit data have also been reported for speed and robustness.^[1]

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 ${\displaystyle \varepsilon }$-ball around the truth). For isotropic measurements, one set of results implies that

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

with improved ${\displaystyle O(\varepsilon ^{-2})}$ scaling when the signal belongs to structured sets (e.g., sparse vectors or low-rank matrices) whose Kolmogorov entropies are smaller.^[1][16] 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.^[1]

Applications

• Low-resolution receivers in massive MIMO communications and detection.^[17]

• Radar and automotive sensing, including covariance-based DOA and one-bit Hankel matrix completion.^[18][19]

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

See also

• Kaczmarz method

• Compressed sensing

• Phase retrieval

• Quantization (signal processing)