Sample abundance

☆ Save On Wikipedia ↗

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 y k {\displaystyle y_{k}} {\displaystyle y_{k}} with a threshold τ k {\displaystyle \tau _{k}} {\displaystyle \tau _{k}}: r k = sgn ⁡ ( y k − τ k ) ∈ { − 1 , + 1 } . {\displaystyle r_{k}=\operatorname {sgn} (y_{k}-\tau _{k})\in \{-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} {\displaystyle r_{k}(y_{k}-\tau _{k})\geq 0}. Stacking many samples and writing y = A x {\displaystyle \mathbf {y} =\mathbf {A} \mathbf {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} \ \}} {\displaystyle {\mathcal {P}}_{\mathbf {x} }=\{\ \mathbf {x} \in \mathbb {R} ^{d}\mid \mathbf {P} \mathbf {x} \succeq \mathbf {b} \ \}},

where P {\displaystyle \mathbf {P} } {\displaystyle \mathbf {P} } collects signed rows of A {\displaystyle \mathbf {A} } {\displaystyle \mathbf {A} } and b {\displaystyle \mathbf {b} } {\displaystyle \mathbf {b} } stacks the threshold terms. Under sample abundance (many more inequalities than unknowns), P x {\displaystyle {\mathcal {P}}_{\mathbf {x} }} {\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 X = x x ⊤ {\displaystyle \mathbf {X} =\mathbf {x} \mathbf {x} ^{\top }} {\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 )}.} {\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 y j = Tr ⁡ ( A j ⊤ X ) {\displaystyle y_{j}=\operatorname {Tr} (\mathbf {A} _{j}^{\top }\mathbf {X} )} {\displaystyle y_{j}=\operatorname {Tr} (\mathbf {A} _{j}^{\top }\mathbf {X} )}, one-bit signs r j ( ℓ ) = sgn ⁡ ( y j − τ j ( ℓ ) ) {\displaystyle r_{j}^{(\ell )}=\operatorname {sgn} (y_{j}-\tau _{j}^{(\ell )})} {\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 y = A x {\displaystyle \mathbf {y} =\mathbf {A} \mathbf {x} } {\displaystyle \mathbf {y} =\mathbf {A} \mathbf {x} } and signs r j ( ℓ ) = sgn ⁡ ( ⟨ a j , x ⟩ − τ j ( ℓ ) ) {\displaystyle r_{j}^{(\ell )}=\operatorname {sgn} (\langle \mathbf {a} _{j},\mathbf {x} \rangle -\tau _{j}^{(\ell )})} {\displaystyle r_{j}^{(\ell )}=\operatorname {sgn} (\langle \mathbf {a} _{j},\mathbf {x} \rangle -\tau _{j}^{(\ell )})}, the feasible set

P x ( C ) = {   x ′ ∈ R n ∣ r j ( ℓ ) ⟨ a j , x ′ ⟩ ≥ r j ( ℓ ) τ j ( ℓ )   } {\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 )}\ \}} {\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 ℓ 1 {\displaystyle \ell _{1}} {\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 } {\displaystyle \varepsilon }-ball around the truth). For isotropic measurements, one set of results implies that

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

with improved O ( ε − 2 ) {\displaystyle O(\varepsilon ^{-2})} {\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

References

  1. Eamaz, Arian; Yeganegi, Farhang; Needell, Deanna; Soltanalian, Mojtaba (2024). "Harnessing the Power of Sample Abundance: Theoretical Guarantees and Algorithms for Accelerated One-Bit Sensing". IEEE Transactions on Information Theory. 70 (9): 6690–6713. Bibcode:2024ITIT...70.6690E. doi:10.1109/TIT.2024.3422918.
  2. "SA-TWG Webinar: New Frontiers in One-Bit Signal Processing: From Sample Abundance to Efficient Intelligence at Scale". IEEE Signal Processing Society. IEEE.
  3. Eamaz, Arian; Yeganegi, Farhang; Soltanalian, Mojtaba (2023). "Covariance Recovery for One-Bit Sampled Stationary Signals with Time-Varying Sampling Thresholds". Signal Processing. 206 108899. arXiv:2203.09460. Bibcode:2023SigPr.20608899E. doi:10.1016/j.sigpro.2022.108899.
  4. Eamaz, Arian; Yeganegi, Farhang (2022). "Covariance Recovery for One-Bit Sampled Non-Stationary Signals with Time-Varying Sampling Thresholds". IEEE Transactions on Signal Processing. 70: 5222–5236. Bibcode:2022ITSP...70.5222E. doi:10.1109/TSP.2022.3217379.
  5. Eamaz, Arian; Mishra, Kumar V.; Yeganegi, Farhang; Soltanalian, Mojtaba (2024). "UNO: Unlimited Sampling Meets One-Bit Quantization". IEEE Transactions on Signal Processing. 72: 997–1014. arXiv:2301.10155. Bibcode:2024ITSP...72..997E. doi:10.1109/TSP.2024.3356253.
  6. Mezghani, Amine; Swindlehurst, A. Lee (2018). "Blind Estimation of Sparse Broadband Massive MIMO Channels with Ideal and One-Bit ADCs". IEEE Transactions on Signal Processing. 66 (11): 2972–2983. arXiv:1709.06698. Bibcode:2018ITSP...66.2972M. doi:10.1109/TSP.2018.2821640.
  7. Ameri, Aria; Bose, Arindam; Li, Jian; Soltanalian, Mojtaba (2019). "One-Bit Radar Processing with Time-Varying Sampling Thresholds". IEEE Transactions on Signal Processing. 67 (20): 5297–5308. arXiv:1911.10170. Bibcode:2019ITSP...67.5297A. doi:10.1109/TSP.2019.2939086.
  8. Eamaz, Arian; Yeganegi, Farhang; Soltanalian, Mojtaba (2022). "One-Bit Phase Retrieval: More Samples Means Less Complexity?". IEEE Transactions on Signal Processing. 70: 4618–4632. arXiv:2203.08982. Bibcode:2022ITSP...70.4618E. doi:10.1109/TSP.2022.3208430. preprint Freely accessible
  9. Eamaz, Arian; Yeganegi, Farhang; Needell, Deanna; Soltanalian, Mojtaba (2023). One-Bit Quadratic Compressed Sensing: From Sample Abundance to Linear Feasibility. IEEE International Symposium on Information Theory (ISIT). doi:10.1109/ISIT54713.2023.10206479.
  10. Yeganegi, Farhang; Eamaz, Arian; Soltanalian, Mojtaba (2024). Low-Rank Matrix Sensing with Dithered One-Bit Quantization. IEEE International Symposium on Information Theory (ISIT). pp. 527–532. doi:10.1109/ISIT57864.2024.10619615.
  11. Dirksen, Sjoerd; Mendelson, Shahar (2021). "Non-Gaussian Hyperplane Tessellations and Robust One-Bit Compressed Sensing". Journal of the European Mathematical Society. 23 (9): 2913–2947. arXiv:1805.09409. doi:10.4171/JEMS/1066.
  12. Xu, Chunlei; Jacques, Laurent (2020). "Quantized Compressive Sensing with RIP Matrices: The Benefit of Dithering". Information and Inference. 9 (3): 543–586. doi:10.1093/imaiai/iaz021. hdl:2078.1/216652.
  13. Strohmer, Thomas; Vershynin, Roman (2009). "A Randomized Kaczmarz Algorithm with Exponential Convergence". Journal of Fourier Analysis and Applications. 15 (2): 262–278. arXiv:math/0702226. Bibcode:2009JFAA...15..262S. doi:10.1007/s00041-008-9030-4.
  14. Leventhal, Daniel; Lewis, Adrian S. (2010). "Randomized Methods for Linear Constraints: Convergence Rates and Conditioning". Mathematics of Operations Research. 35 (3): 641–654. doi:10.1287/moor.1100.0456.
  15. De Loera, Jesús A.; Haddock, John; Needell, Deanna (2017). "A Sampling Kaczmarz–Motzkin Algorithm for Linear Feasibility". SIAM Journal on Scientific Computing. 39 (5): S66–S87. arXiv:1605.01418. Bibcode:2017SJSC...39S..66D. doi:10.1137/16M1073807.
  16. Jacques, Laurent; Cambareri, Vittorio (2017). "Time for Dithering: Fast and Quantized Random Embeddings via the Restricted Isometry Property". Information and Inference. 6 (4): 441–476. arXiv:1607.00816. doi:10.1093/imaiai/iax004.
  17. Mezghani, Amine; Swindlehurst, A. Lee (2018). "Blind Estimation of Sparse Broadband Massive MIMO Channels with Ideal and One-Bit ADCs". IEEE Transactions on Signal Processing. 66 (11): 2972–2983. arXiv:1709.06698. Bibcode:2018ITSP...66.2972M. doi:10.1109/TSP.2018.2821640.
  18. Ameri, Aria; Bose, Arindam; Li, Jian; Soltanalian, Mojtaba (2019). "One-Bit Radar Processing with Time-Varying Sampling Thresholds". IEEE Transactions on Signal Processing. 67 (20): 5297–5308. arXiv:1911.10170. Bibcode:2019ITSP...67.5297A. doi:10.1109/TSP.2019.2939086.
  19. Eamaz, Arian; Yeganegi, Farhang; Hu, Yunqiao; Sun, Shunqiao; Soltanalian, Mojtaba (2024). "Automotive Radar Sensing with Sparse Linear Arrays Using One-Bit Hankel Matrix Completion". 2024 IEEE Radar Conference (RadarConf24). pp. 1–6. doi:10.1109/RadarConf2458775.2024.10548330. ISBN 979-8-3503-2920-9.
  20. Eamaz, Arian; Mishra, Kumar V.; Yeganegi, Farhang; Soltanalian, Mojtaba (2023). "Unlimited Sampling via One-Bit Quantization". 2023 International Conference on Sampling Theory and Applications (SampTA). pp. 1–5. doi:10.1109/SampTA59647.2023.10301408. ISBN 979-8-3503-2885-1.