Butterfly Factorization with Error Guarantees
- 10 October 2025
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 46 (4) , 2253-2309
Abstract
In this paper, we investigate the butterfly factorization problem, i.e., the problem of approximating a matrix by a product of sparse and structured factors. We propose a new formal mathematical description of such factors, that encompasses many different variations of butterfly factorization with different choices of the prescribed sparsity patterns. Among these choices we identify those that ensure that the factorization problem admits an optimum, thanks to a new property called “chainability”. For those supports we propose a new butterfly algorithm that yields an approximate solution to the butterfly factorization problem and that is supported by stronger theoretical guarantees than existing factorization methods. Specifically, we show that the ratio of the approximation error by the minimum value is bounded by a constant, independent of the target matrix. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SIMAX and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://inria.hal.science/hal-04720713v1 . [Formula: see text]Keywords
All Related Versions
Funding Information
- Toulouse School of Economics
- CIFRE (N°2020/1643)
- Agence Nationale de la Recherche (ANR-19-CHIA-0009, ANR-23-PEIA-0008)
- Agence Nationale de la Recherche (ANR-19-PI3A0004)
- Air Force Office of Scientific Research (FA8655-22-1-7012)
This publication has 29 references indexed in Scilit:
- Multidimensional butterfly factorizationApplied and Computational Harmonic Analysis, 2018
- Hierarchical Matrices: Algorithms and Analysis2015
- Fast algorithms for spherical harmonic expansions, IIIJournal of Computational Physics, 2010
- An algorithm for the rapid evaluation of special function transformsApplied and Computational Harmonic Analysis, 2010
- Randomized algorithms for the low-rank approximation of matricesProceedings of the National Academy of Sciences, 2007
- Convex Optimization2004
- Multilevel evaluation of electromagnetic fields for the rapid solution of scattering problemsMicrowave and Optical Technology Letters, 1994
- Fast fourier transforms: A tutorial review and a state of the artSignal Processing, 1990
- On the limited memory BFGS method for large scale optimizationMathematical Programming, 1989
- The Approximation of One Matrix by Another of Lower RankPsychometrika, 1936