Modern neural network architectures use structured linear transformations,\nsuch as low-rank matrices, sparse matrices, permutations, and the Fourier\ntransform, to improve inference speed and reduce memory usage compared to\ngeneral linear maps. However, choosing which of the myriad structured\ntransformations to use (and its associated parameterization) is a laborious\ntask that requires trading off speed, space, and accuracy. We consider a\ndifferent approach: we introduce a family of matrices called kaleidoscope\nmatrices (K-matrices) that provably capture any structured matrix with\nnear-optimal space (parameter) and time (arithmetic operation) complexity. We\nempirically validate that K-matrices can be automatically learned within\nend-to-end pipelines to replace hand-crafted procedures, in order to improve\nmodel quality. For example, replacing channel shuffles in ShuffleNet improves\nclassification accuracy on ImageNet by up to 5%. K-matrices can also simplify\nhand-engineered pipelines -- we replace filter bank feature computation in\nspeech data preprocessing with a learnable kaleidoscope layer, resulting in\nonly 0.4% loss in accuracy on the TIMIT speech recognition task. In addition,\nK-matrices can capture latent structure in models: for a challenging permuted\nimage classification task, a K-matrix based representation of permutations is\nable to learn the right latent structure and improves accuracy of a downstream\nconvolutional model by over 9%. We provide a practically efficient\nimplementation of our approach, and use K-matrices in a Transformer network to\nattain 36% faster end-to-end inference speed on a language translation task.\n