  That neural networks may be pruned to high sparsities and retain high
accuracy is well established. Recent research efforts focus on pruning
immediately after initialization so as to allow the computational savings
afforded by sparsity to extend to the training process. In this work, we
introduce a new `DCT plus Sparse' layer architecture, which maintains
information propagation and trainability even with as little as 0.01% trainable
kernel parameters remaining. We show that standard training of networks built
with these layers, and pruned at initialization, achieves state-of-the-art
accuracy for extreme sparsities on a variety of benchmark network architectures
and datasets. Moreover, these results are achieved using only simple heuristics
to determine the locations of the trainable parameters in the network, and thus
without having to initially store or compute with the full, unpruned network,
as is required by competing prune-at-initialization algorithms. Switching from
standard sparse layers to DCT plus Sparse layers does not increase the storage
footprint of a network and incurs only a small additional computational
overhead.
