Majority Vote Compressed Sensing
Henrik Hellström 2 1, Jiwon Jeong 1, Ayfer Özgür 1, Viktoria Fodor 2, and Carlo Fischione 2 · 2025
Read Majority Vote Compressed Sensing by Henrik Hellström 2 1, Jiwon Jeong 1, Ayfer Özgür 1, Viktoria Fodor 2, and Carlo Fischione 2 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-18008.txt.
Introduction
Henrik Hellström and four co-authors compute a sum over the air from many devices without wasting scarce channel time. Each device holds a sparse high-dimensional vector, and a receiver needs the total. Older non-coherent schemes need more channel uses than the data length, which is wasteful when most entries are zero.
Random projections shrink each vector before sending. A majority vote scheme then recovers the signs of the summed projections at the receiver. Sparsity does the heavy lifting, cutting cost sharply. Wireless researchers get a scheme tuned to the common case where data are mostly empty.
Catalog record
| CREATOR | Henrik Hellström 2 1, Jiwon Jeong 1, Ayfer Özgür 1, Viktoria Fodor 2, and Carlo Fischione 2 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-18008
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Majority Vote Compressed Sensing Thanks: We acknowledge the financial support of the Ericsson Research Foundation, the Swedish Foundation for Strategic Research: SAICOM, and KTH Digital Futures. Henrik Hellström 2 1, Jiwon Jeong 1, Ayfer Özgür 1, Viktoria Fodor 2, and Carlo Fischione 2 Abstract We consider the problem of non-coherent over-the-air computation (AirComp), where n n devices carry high-dimensional data vectors 𝐱 i ∈ ℝ d \mathbf{x}_{i}\in\mathbb{R}^{d} of sparsity ∥ 𝐱 i ∥ 0 ≤ k \lVert\mathbf{x}_{i}\rVert_{0}\leq k whose sum has to be computed at a receiver. Previous results on non-coherent AirComp require more than d d channel uses to compute functions of 𝐱 i \mathbf{x}_{i} , where the extra redundancy is used to combat non-coherent signal aggregation. However, if the data vectors are sparse, sparsity can be exploited to offer significantly cheaper communication. In this paper, we propose to use random transforms to transmit lower-dimensional projections 𝐬 i ∈ ℝ T \mathbf{s}_{i}\in\mathbb{R}^{T} of the data vectors. These projected vectors are communicated to the receiver using a majority vote (MV)-AirComp scheme, which estimates the bit-vector corresponding to the signs of the aggregated projections, i.e., 𝐲 = sign ( ∑ i 𝐬 i ) \mathbf{y}=\text{sign}(\sum_{i}\mathbf{s}_{i}) . By leveraging 1-bit compressed sensing (1bCS) at the receiver, the real-valued and high-dimensional aggregate ∑ i 𝐱 i \sum_{i}\mathbf{x}_{i} can be recovered from 𝐲 \mathbf{y} . We prove analytically that the proposed MVCS scheme estimates the aggregated data vector ∑ i 𝐱 i \sum_{i}\mathbf{x}_{i} with ℓ 2 \ell_{2} -norm error ϵ \epsilon in T = 𝒪 ( k n log ( d ) / ϵ 2 ) T=\mathcal{O}(kn\log(d)/\epsilon^{2}) channel uses. Moreover, we specify algorithms that leverage MVCS for histogram estimation and distributed machine learning. Finally, we provide numerical evaluations that reveal the advantage of MVCS compared to the state-of-the-art. 1bCS 1-bit Compressed Sensing 2G Second Generation 3-DAP 3-Dimensional Assignment Problem 3G 3 {}^{\text{rd}} Generation 3GPP 3 {}^{\text{rd}} Generation Partnership Project 4G 4 {}^{\text{th}} Generation 5G 5 {}^{\text{th}} Generation AA Antenna Array AC Admission Control AD Attack-Decay ADC analog-to-digital converter ADMM alternating direction method of multipliers ADSL Asymmetric Digital Subscriber Line AHW Alternate Hop-and-Wait AirComp over-the-air computation AirGT Over-the-Air Group Testing AMC Adaptive Modulation and Coding AP Access Point APA Adaptive Power Allocation ARMA Autoregressive Moving Average ARQ Automatic Repeat Request ATES Adaptive Throughput-based Efficiency-Satisfaction Trade-Off AWGN additive white Gaussian noise BAA Broadband Analog Aggregation BB Branch and Bound BCD block coordinate descent BD Block Diagonalization BER Bit Error Rate BF Best Fit BFD bidirectional full duplex BLER BLock Error Rate BPC Binary Power Control BPSK Binary Phase-Shift Keying BRA Balanced Random Allocation BS base station BSUM block successive upper-bound minimization CAP Combinatorial Allocation Problem CAPEX Capital Expenditure CBF Coordinated Beamforming CBR Constant Bit Rate CBS Class Based Scheduling CC Congestion Control CDF Cumulative Distribution Function CDMA Code-Division Multiple Access CE Channel Estimation CL Closed Loop CLPC Closed Loop Power Control CML centralized machine learning CNR Channel-to-Noise Ratio CNN Convolutional Neural Network COMP combinatorial orthogonal matching pursuit CPA Cellular Protection Algorithm CPICH Common Pilot Channel CoCoA Communication efficient distributed dual Coordinate Ascent CoMAC Computation over Multiple-Access Channels CoMP Coordinated Multi-Point CQI Channel Quality Indicator CRC cyclic redundancy check CRM Constrained Rate Maximization CRN Cognitive Radio Network CS Compressed Sensing CSI Channel State Information CSMA Carrier Sense Multiple Access CUE Cellular User Equipment D2D device-to-device DAC digital-to-analog converter DC direct current DCA Dynamic Channel Allocation DE Differential Evolution DFT Discrete Fourier Transform DIST Distance DL downlink DMA Double Moving Average DML Distributed Machine Learning DMRS demodulation reference signal D2DM D2D Mode DMS D2D Mode Selection DPC Dirty Paper Coding DRA Dynamic Resource Assignment DSA Dynamic Spectrum Access DSGD Distributed Stochastic Gradient Descent DSM Delay-based Satisfaction Maximization ECC Electronic Communications Committee EFLC Error Feedback Based Load Control EI Efficiency Indicator eNB Evolved Node B EPA Equal Power Allocation EPC Evolved Packet Core EPS Evolved Packet System E-UTRAN Evolved Universal Terrestrial Radio Access Network ES Exhaustive Search FA Federated Analytics FC Fusion Center FD Federated Distillation FDD frequency division duplex FDM Frequency Division Multiplexing FDMA Frequency Division Multiple Access FedAvg Federated Averaging FER Frame Erasure Rate FF Fast Fading FL federated learning FSB Fixed Switched Beamforming FEC forward error correcting FST Fixed SNR Target FTP File Transfer Protocol GA Genetic Algorithm GBR Guaranteed Bit Rate GD Gradient Descent GLR Gain to Leakage Ratio GOS Generated Orthogonal Sequence GPL GNU General Public License GRP Grouping GT Group Testing HARQ Hybrid Automatic Repeat Request HD half-duplex HMS Harmonic Mode Selection HOL Head Of Line HSDPA High-Speed Downlink Packet Access HSPA High Speed Packet Access HTTP HyperText Transfer Protocol ICMP Internet Control Message Protocol ICI Intercell Interference ID Identification IETF Internet Engineering Task Force iff if and only if ILP Integer Linear Program JRAPAP Joint RB Assignment and Power Allocation Problem UID Unique Identification IID Independent and Identically Distributed IIR Infinite Impulse Response ILP Integer Linear Problem IMT International Mobile Telecommunications INV Inverted Norm-based Grouping IoT Internet of Things IP Integer Programming IPv6 Internet Protocol Version 6 ISD Inter-Site Distance ISI Inter Symbol Interference ITU International Telecommunication Union IQ in-phase and quadrature JAFM joint assignment and fairness maximization JAFMA joint assignment and fairness maximization algorithm JOAS Joint Opportunistic Assignment and Scheduling JOS Joint Opportunistic Scheduling JP Joint Processing JS Jump-Stay KKT Karush-Kuhn-Tucker L3 Layer-3 LAC Link Admission Control LA Link Adaptation LC Load Control LDC Learning-Driven Communication LDPC low-density parity-check LO Local Oscillator LOS line of sight LP Linear Programming LTE Long Term Evolution LTE-A LTE ( LTE )-Advanced LTE-Advanced Long Term Evolution Advanced M2M Machine-to-Machine MAC multiple access channel MANET Mobile Ad hoc Network MC Modular Clock MCS modulation and coding scheme MDB Measured Delay Based MDI Minimum D2D Interference MF Matched Filter MG Maximum Gain MGF Moment Generating Function MH Multi-Hop MIMO Multiple Input Multiple Output MINLP mixed integer nonlinear programming MIP Mixed Integer Programming MISO multiple input single output ML Machine Learning MLWDF Modified Largest Weighted Delay First MME Mobility Management Entity MMSE minimum mean squared error MOS Mean Opinion Score MPF Multicarrier Proportional Fair MRA Maximum Rate Allocation MR Maximum Rate MRC Maximum Ratio Combining MRT Maximum Ratio Transmission MRUS Maximum Rate with User Satisfaction MS Mode Selection MSE Mean Squared Error MSI Multi-Stream Interference MTC Machine-Type Communication MTSI Multimedia Telephony Services over IMS MTSM Modified Throughput-based Satisfaction Maximization MU-MIMO Multi-User Multiple Input Multiple Output MU Multi-User MV Majority Vote MVCS majority vote compressed sensing NAS Non-Access Stratum NB Node B NCL Neighbor Cell List NCOMP Noisy Combinatorial Orthogonal Matching Pursuit NLP Nonlinear Programming NLOS non-line of sight NMSE Normalized Mean Square Error NOMA Non-Orthogonal Multiple Access NORM Normalized Projection-based Grouping NP non-polynomial time NRT Non-Real Time NSPS National Security and Public Safety Services O2I Outdoor to Indoor OFDMA Orthogonal Frequency Division Multiple Access OFDM Orthogonal Frequency Division Multiplexing OFPC Open Loop with Fractional Path Loss Compensation O2I Outdoor-to-Indoor OL Open Loop OLPC Open-Loop Power Control OL-PC Open-Loop Power Control OPEX Operational Expenditure ORB Orthogonal Random Beamforming JO-PF Joint Opportunistic Proportional Fair OSI Open Systems Interconnection PAIR D2D Pair Gain-based Grouping PAPR Peak-to-Average Power Ratio P2P Peer-to-Peer PC Power Control PCI Physical Cell ID PDCCH physical downlink control channel PDD penalty dual decomposition PDF Probability Density Function PER Packet Error Rate PF Proportional