Id: arxiv/2607.29361 Url: https://arxiv.org/abs/2607.29361 Tags: math.NA Score: 0 Title: A recursive butterfly factorization with optimality guarantees Domain: math.NA Source: arxiv Authors: David Persson, Paul G. Beckman, Tyler Chen, Diana Halikias, Christopher Musco Reviews: 0 Subject: math.NA Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-31 Page: https://delphi.science/r/arxiv/2607.29361 We formalize a recursive format for representing a butterfly matrix. This new format naturally leads to a simple recursive algorithm for computing a quasi-optimal butterfly approximation to an arbitrary $N \times N$ matrix $A$. When the entries of $A$ are explicitly available, we show that the algorithm computes a butterfly matrix $B$ in $O(N^2)$ operations with approximation error $\|A - B\|_F$ at most a $O(\sqrt{\log(N)})$ factor away from that of the best possible approximation by a butterfly matrix. We also develop a matrix-free variant of the method, which uses $\widetilde{O}(\sqrt{N})$…