Majority Vote Compressed Sensing

Henrik Hellström, Jiwon Jeong, Ayfer Özgür, Viktoria Fodor, Carlo FischionearXiv 2025 · DOI · arXiv

TL;DR

Majority Vote Compressed Sensing (MVCS) is a new framework for "over-the-air computation" that allows a wireless receiver to estimate the sum of sparse, high-dimensional data from multiple devices without needing difficult phase synchronization. By combining 1-bit compressed sensing with a power-based majority voting scheme, MVCS significantly reduces communication latency and energy consumption while remaining robust to wireless channel noise.

What Problem Does This Paper Address?

In distributed systems like Federated Learning, an Access Point (AP) often needs to compute the sum of data vectors (like gradients) from many devices. Over-the-Air Computation (AirComp) is a clever way to do this: instead of devices taking turns to transmit, they all transmit simultaneously, and the wireless channel itself performs the "summation" via signal superposition.

However, standard AirComp has a major hurdle: phase synchronization. For signals to sum correctly, their phases must be perfectly aligned at the receiver, requiring sub-nanosecond precision that is nearly impossible for low-cost IoT devices. "Non-coherent" versions exist that don't require phase alignment, but they typically require more radio resources (channel uses) than the actual dimension of the data.

This paper addresses the inefficiency of non-coherent AirComp by exploiting sparsity. Since many real-world signals are mostly zeros, the authors ask: Can we use Compressed Sensing to compute these sums using far fewer channel uses than the data's original dimension?

Methods

The authors introduce Majority Vote Compressed Sensing (MVCS), which works in three main stages:

  1. Projection: Each device takes its high-dimensional sparse vector $\mathbf{x}_i$ (dimension $d$) and multiplies it by a shared random Gaussian matrix to create a lower-dimensional projection $\mathbf{s}_i$ (dimension $T$, where $T \ll d$).
  2. Transmission (Majority Vote): Devices transmit these projections using a non-coherent "Majority Vote" scheme. For each element in the projected vector, the devices "vote" on whether it is positive or negative by transmitting in one of two orthogonal radio resources. The AP simply compares the received power in these two resources to determine the "winning" sign.
  3. Reconstruction (1-bit CS): The AP now has a vector of signs—essentially 1-bit measurements. It then uses a "passive" 1-bit Compressed Sensing (1bCS) algorithm (based on soft-thresholding) to reconstruct the original high-dimensional sum $\sum \mathbf{x}_i$.

The brilliance of this approach is that 1-bit CS is inherently designed to work with sign data, making it a perfect match for the "majority vote" nature of non-coherent wireless aggregation.

Datasets

  • MNIST: The classic dataset of handwritten digits was used to evaluate MVCS in a distributed machine learning context (Stochastic Gradient Descent and Federated Averaging).
  • Synthetic Data: Used to rigorously test the theoretical error bounds and the performance of the scheme for histogram estimation.

Key Insights and Ideas

  • Phase-Independence as a Feature: By relying on energy detection (power levels) rather than phase, MVCS bypasses the most significant technical barrier to deploying AirComp in the real world.
  • Sparsity as a Latency Reducer: The paper proves that the required number of channel uses $T$ scales with $O(kn \log(d))$, where $k$ is the sparsity. This means as data becomes more sparse, the communication becomes significantly "cheaper."
  • The "Passive" Advantage: Unlike many compressed sensing algorithms that require knowing the exact number of non-zero elements, the "passive algorithm" used here only needs an upper bound, making it much more robust to the unpredictable noise of wireless environments.
  • Tunability: MVCS allows a system designer to trade off communication efficiency for estimation error by simply adjusting the dimension $T$, similar to choosing a code rate in traditional digital communications.

Key Results

  • Improved Accuracy: In distributed SGD simulations on MNIST, MVCS achieved a 2-3% improvement in classification accuracy over the state-of-the-art "Dense" Majority Vote scheme while using the same total radio resources.
  • Exact Histogram Recovery: The authors proved (and demonstrated numerically) that MVCS can retrieve an exact histogram from distributed devices with high probability, even when the AP is barred from seeing individual user data for privacy reasons.
  • Theoretical Guarantee: The paper provides a rigorous proof that the estimation error $\epsilon$ can be made arbitrarily small as long as the number of channel uses $T$ follows the $O(kn \log(d)/\epsilon^2)$ scaling law.

Limitations and Future Work

  • The "Norm" Problem: 1-bit Compressed Sensing naturally loses the magnitude (the "norm") of the reconstructed vector—it only recovers the direction. In machine learning, the magnitude of a gradient is important for deciding the step size. The authors currently use a pre-set "step size schedule" to work around this, but they note that integrating 1bCS with norm estimation is a promising future direction.
  • Discrete Data Exploitation: The current reconstruction algorithm treats the data as continuous real numbers. The authors suggest that future versions could be even more efficient by exploiting the discrete (integer) nature of data like histograms.
  • Scaling with $n$: While the scheme scales well with data dimension $d$, the error bound still depends on the number of devices $n$. Further research into "sketching" techniques might help optimize this further.

Summary updated

Abstract

We consider the problem of non-coherent over-the-air computation (AirComp), where $n$ devices carry high-dimensional data vectors $\mathbf{x}_i\in\mathbb{R}^d$ of sparsity $\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$ channel uses to compute functions of $\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 $\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., $\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 $\sum_i\mathbf{x}_i$ can be recovered from $\mathbf{y}$. We prove analytically that the proposed MVCS scheme estimates the aggregated data vector $\sum_i \mathbf{x}_i$ with $\ell_2$-norm error $ε$ in $T=\mathcal{O}(kn\log(d)/ε^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.
BibTeX
@misc{hellstrom2025majority,
  author = {Henrik Hellström and Jiwon Jeong and Ayfer Özgür and Viktoria Fodor and Carlo Fischione},
  title = {{Majority Vote Compressed Sensing}},
  year = {2025},
  eprint = {2510.18008},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.18008},
  howpublished = {arXiv},
}
Figure