{"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","summary":"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})$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-31","reactions":{}}