This work formalizes a lot of really effective ideas I've run across in making high-performance neural networks. Structural (eg, block) sparsity allows a massive reduction in parameters, while still playing nice with GPU/TPU/SIMD memory alignment. As an inductive bias, block diagonality corresponds to breaking a problem into parts, which we tend to recognize as a good problem solving strategy in other domains! The low-rank matrices then allow 'sharing' information between blocks.
The additional nice trick with butterfly matrices is permuting the block diagonal activations to achieve additional sparsity patterns, and then chaining them together. This is in practice very similar to how the Fast Fourier Transform achieves n*log(n) complexity.