Majority Vote Compressed Sensing for Over-the-Air Histogram Estimation

We consider the problem of non-coherent over-the-air computation (AirComp), where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> devices carry highdimensional data vectors <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{x}_{i} \in \mathbb{R}^{d}$</tex> of sparsity <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\left\vert\mathrm{x}_{i}\right\vert_{0} \leq k$</tex> and the sum of these data vectors has to be computed at a receiver. Previous results on non-coherent AirComp require more than <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex> channel uses to compute functions of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{x}_{i}$</tex>, 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$s_{i} \in \mathbb{R}^{T}$</tex> 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., <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{y}=\text{sign}\left(\sum_{i} \mathbf{s}_{i}\right)$</tex>. By leveraging 1-bit compressed sensing (1bCS) at the receiver, the real-valued and high-dimensional aggregate <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\sum_{i} \mathrm{x}_{i}$</tex> can be recovered from <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$y$</tex>. We prove analytically that the proposed MVCS scheme estimates the aggregate data vector <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\sum_{i} \mathrm{x}_{i}$</tex> with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{2}$</tex>-norm error <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\epsilon$</tex> in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T=\mathcal{O}\left(k n \log (d) / \epsilon^{2}\right)$</tex> channel uses. We consider distributed histogram estimation, a canonical building block for federated analytics, as an aplication for MVCS where the data vectors <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{x}_{i}$</tex> are inherently 1 -sparse. Our numerical evaluations demonstrate that our scheme achieves the same order of communication cost as state-of-the-art methods while avoiding the complexity and overhead of additional cryptographic tools.