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.
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 {\displaystyle y_{k}} with a threshold τ k {\displaystyle \tau _{k}} : r k = sgn ( y k − τ k ) ∈ { − 1 , + 1 } . {\displaystyle r_{k}=\operatorname {sgn} (y_{k}-\tau _{k})\in \{-1,+1\}.} Each observation yields the linear inequality r k ( y k − τ k ) ≥ 0 {\displaystyle r_{k}(y_{k}-\tau _{k})\geq 0} . Stacking many samples and writing y = A x {\displaystyle \mathbf {y} =\mathbf {A} \mathbf {x} } for linear sensing gives the one-bit polyhedron:
P x = { x ∈ R d ∣ P x ⪰ b } {\displaystyle {\mathcal {P}}_{\mathbf {x} }=\{\ \mathbf {x} \in \mathbb {R} ^{d}\mid \mathbf {P} \mathbf {x} \succeq \mathbf {b} \ \}} , where P {\displaystyle \mathbf {P} } collects signed rows of A {\displaystyle \mathbf {A} } and b {\displaystyle \mathbf {b} } stacks the threshold terms. Under sample abundance (many more inequalities than unknowns), P x {\displaystyle {\mathcal {P}}_{\mathbf {x} }} 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 X = x x ⊤ {\displaystyle \mathbf {X} =\mathbf {x} \mathbf {x} ^{\top }} : r j ( ℓ ) a j ⊤ X a j ≥ r j ( ℓ ) τ j ( ℓ ) . {\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.
… excerpt ends here. Continue reading the full article.
