Butterfly Factorization with Error Guarantees

Quoc-Tung Le, Léon Zheng, Elisa Riccietti, Rémi GribonvalSIAM J. Matrix Anal. Appl 2025 · DOI

Abstract

Butterfly factorization is a powerful technique for compressing large matrices into products of sparse factors, significantly reducing computational costs from $O(n^2)$ to $O(n \log n)$. Despite its practical success, the method has historically lacked rigorous theoretical error guarantees. This paper introduces the concept of chainability and a novel pseudo-orthonormalization algorithm to provide the first quasi-optimality bounds, ensuring that the approximation error remains within a constant factor of the global optimum.

Introduction

In modern machine learning and signal processing, the computational bottleneck often lies in large-scale matrix-vector multiplications. Butterfly factorization addresses this by approximating dense matrices as a product of $L \approx \log n$ sparse factors. This structure is inherent in fundamental operations like the Discrete Fourier Transform (DFT). However, two major challenges have persisted: determining if an optimal factorization exists for a given sparsity pattern and proving that hierarchical algorithms can reach it.

Methodology: Kronecker-Sparse Formalism and Chainability

The authors formalize butterfly architectures using a 4-parameter mathematical language based on Kronecker products of identity and all-ones matrices. This allows for a precise description of various sparse structures, from the overall factor down to individual sub-blocks.

Hierarchical structure of a Kronecker-sparse factor, showing the decomposition into blocks and diagonal sub-blocks.

A central discovery of this work is the property of chainability. An architecture is considered chainable if the product of its sparse factors remains stable within a predictable sparse structure. The authors prove that chainability is a sufficient condition to guarantee that an optimal solution exists within the search space.

Classification of matrix architectures and their chainability status, which determines the existence of optimal solutions.

To ensure numerical stability and theoretical convergence, the authors introduce pseudo-orthonormalization. This step uses QR decompositions to "normalize" factors during hierarchical construction, preventing error amplification without altering the final matrix product.

Experimental Evaluation

The framework was validated using structured and synthetic matrices to test speed and accuracy:

  • Hadamard Matrices: A $1024 \times 1024$ matrix was factorized to machine precision ($10^{-7}$ relative error) almost instantaneously, outperforming gradient-based methods by orders of magnitude.
  • Noise Robustness: In tests with Gaussian noise, the pseudo-orthonormalization step allowed the algorithm to consistently recover underlying structures better than standard hierarchical methods, often staying below the noise floor.
  • Flexibility: The "deformable" butterfly framework successfully handled non-dyadic sizes (e.g., $4608 = 3^2 \times 2^9$), proving its utility beyond simple powers of two.

Key Insights and Quasi-Optimality

The difficulty of butterfly factorization arises from the non-convexity of the search space. By enforcing chainability and using orthonormalization as a mathematical bridge, the authors prove that their algorithm is quasi-optimal. This means the resulting error is bounded by $C_\beta \cdot (\text{Minimum Possible Error})$, where the constant $C_\beta$ grows very slowly with the number of factors, making the guarantee practical for deep factorizations.

Conclusion and Future Work

This work provides the first theoretical foundation for butterfly factorization, bridging the gap between empirical performance and mathematical certainty. While the algorithm is highly efficient, it currently assumes a known row and column permutation. Future research will focus on discovering these permutations automatically and extending guarantees to non-chainable architectures.

Summary updated

BibTeX
@article{le2025butterfly,
  author = {Quoc-Tung Le and Léon Zheng and Elisa Riccietti and Rémi Gribonval},
  title = {{Butterfly Factorization with Error Guarantees}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2025},
  doi = {10.1137/24m1708796},
}

Loading related content...

Figure