Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations.

Area of Science:

• Machine Learning
• Numerical Analysis
• Algorithm Design

Background:

• Fast linear transforms are crucial in machine learning, often represented by dense matrix-vector multiplication.
• Specialized algorithms exist for transforms like FFT and discrete cosine transform, but hand-crafting is labor-intensive.
• The necessity of manual algorithm design and the knowledge required for automated learning of fast transforms are key questions.

Purpose of the Study:

• To investigate the extent to which fast algorithms for structured transforms can be automatically learned.
• To explore the structural priors encoded in these algorithms.
• To develop a generic framework for learning efficient matrix-vector multiplication algorithms.

Main Methods:

• A parameterization of divide-and-conquer methods is introduced, inspired by representing fast matrix-vector multiplication as sparse matrix products.
• This generic formulation is used to automatically learn efficient algorithms for various structured transforms.
• The method is integrated into machine learning pipelines as a replacement for generic matrices.

Main Results:

• The method successfully recovers the Cooley-Tukey FFT algorithm (O(N log N)) to machine precision for dimensions up to 1024.
• In a network compression task on CIFAR-10, the structured approach achieved 3.9 points higher accuracy than unconstrained matrices.
• The learned transformations demonstrated significant efficiency gains: 4x faster inference and 40x fewer parameters.

Conclusions:

• Automated learning of fast algorithms for structured transforms is feasible and effective.
• The proposed method offers a way to create efficient and compressible transformations within machine learning pipelines.
• This approach represents a significant advancement, enabling structured methods to surpass unconstrained ones in specific tasks.