We explore a scheme that enables the training of a deep neural network in aFederated Learning configuration over an additive white Gaussian noise channel.The goal is to create a low complexity, linear compression strategy, calledPolarAir, that reduces the size of the gradient at the user side to lower thenumber of channel uses needed to transmit it. The suggested approach belongs tothe family of compressed sensing techniques, yet it constructs the sensingmatrix and the recovery procedure using multiple access techniques. Simulationsshow that it can reduce the number of channel uses by ~30% when compared toconveying the gradient without compression. The main advantage of the proposedscheme over other schemes in the literature is its low time complexity. We alsoinvestigate the behavior of gradient updates and the performance of PolarAirthroughout the training process to obtain insight on how best to construct thiscompression scheme based on compressed sensing.