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.
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.
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