Fast linear transforms are ubiquitous in machine learning, including the
discrete Fourier transform, discrete cosine transform, and other structured
transformations such as convolutions. All of these transforms can be
represented by dense matrix-vector multiplication, yet each has a specialized
and highly efficient (subquadratic) algorithm. We ask to what extent
hand-crafting these algorithms and implementations is necessary, what
structural priors they encode, and how much knowledge is required to
automatically learn a fast algorithm for a provided structured transform.
Motivated by a characterization of fast matrix-vector multiplication as
products of sparse matrices, we introduce a parameterization of
divide-and-conquer methods that is capable of representing a large class of
transforms. This generic formulation can automatically learn an efficient
algorithm for many important transforms; for example, it recovers the $O(N \log
N)$ Cooley-Tukey FFT algorithm to machine precision, for dimensions $N$ up to
$1024$. Furthermore, our method can be incorporated as a lightweight
replacement of generic matrices in machine learning pipelines to learn
efficient and compressible transformations. On a standard task of compressing a
single hidden-layer network, our method exceeds the classification accuracy of
unconstrained matrices on CIFAR-10 by 3.9 points -- the first time a structured
approach has done so -- with 4X faster inference speed and 40X fewer
parameters.

通过将快速矩阵向量乘法的特性定义为稀疏矩阵的积，我们引入了一种分治方法的参数化形式，可以自动学习很多重要的变换的有效算法，并且在机器学习流水线中可以作为通用矩阵的轻量级替代，以学习高效且可压缩的变换。