A recursive butterfly factorization with optimality guarantees

David Persson, Paul G. Beckman, Tyler Chen, Diana Halikias, Christopher Musco

arXivarxiv/2607.29361Jul 31, 2026math.NAscore 0

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})$…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2607.29361
curl -X POST /api/v1/records/arxiv/2607.29361/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.29361/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'