We consider the problem of non-coherent over-the-air computation (AirComp), where n devices carry highdimensional data vectors x_i ∈ R^d of sparsity ||x_i||₀ ≤ k and the sum of these data vectors has to be computed at a receiver. Previous results on non-coherent AirComp require more than d channel uses to compute functions of 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 s_i ∈ 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., y=sign (Σ_i s_i). By leveraging 1-bit compressed sensing (1bCS) at the receiver, the real-valued and high-dimensional aggregate Σ_i x_i can be recovered from y. We prove analytically that the proposed MVCS scheme estimates the aggregate data vector Σ_ix_i with ℓ₂-norm error ϵ in T=O (k n log (d) / ϵ²) channel uses. We consider distributed histogram estimation, a canonical building block for federated analytics, as an aplication for MVCS where the data vectors x_i 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.