Pith. sign in

REVIEW 2 major objections 4 minor 67 references

A recursive butterfly factorization with optimality guarantees

T0 review · 2 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A recursive format for butterfly matrices yields quasi-optimal approximation algorithms for both entry and matvec access, providing the first error guarantee for the standard hybrid butterfly factorization.

desk verdict Solid, genuinely useful paper that gives the first quasi-optimality guarantee for the Liu et al. matvec butterfly factorization; the key caveat is that the central BF-out bound is imported from a companion paper and the memory-efficient appendix is under-proved. read the letter →

arxiv 2607.29361 v1 pith:ZBVTWA64 submitted 2026-07-31 math.NA cs.NA

David Persson , Paul G. Beckman , Tyler Chen , Diana Halikias , Christopher Musco This is my paper
classification math.NAcs.NA MSC 65F5565Y2068W20
keywords butterflymatrixrecursivefactorizationcomplementarylow-rankquasi-optimalapproximationmatrix-vectorproductqueriesrandomizedsketchinghierarchicalstructureFrobeniusnormerror
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes that every butterfly matrix—the low-rank-structured format behind fast transforms for oscillatory operators—can be represented recursively: after factoring out block-diagonal orthonormal bases, the remaining core splits into four blocks that are themselves butterfly matrices of half the level. This recursive format yields a simple greedy algorithm that, given the entries of an arbitrary N×N matrix, computes a butterfly approximation in O(N^2) time whose Frobenius error is at most an O(sqrt(log N)) factor from the best possible butterfly approximation. For access limited to matrix-vector products, the paper gives an algorithm using ~O(sqrt(N)) matvecs and ~O(N) memory that returns, with high probability, a butterfly approximation within an O(N^{1/4}) factor of optimal. This matvec method is shown to be a reformulation of a widely used hybrid butterfly factorization, which previously lacked any quasi-optimality guarantee. If correct, the work closes a gap between practice and theory for butterfly approximation.

What carries the argument

The central object is the recursive factorization of butterfly matrices (Theorem 4): a level-L butterfly matrix B equals U X V^T with U,V block-diagonal with orthonormal columns, and X a 2×2 block matrix whose four blocks are level-(L−2) butterfly matrices. This identity turns butterfly approximation into a recursion on smaller matrices: at each level one must find block-diagonal column/row bases that capture the extreme complementary low-rank blocks (the BF-out class), then recurse on the core X. Two tools carry the analysis: (i) a quasi-optimality bound for BF-out approximation imported from the BLR2 class (Theorem 9), which guarantees the one-level compression is within 2Γ of the best BF-

What would settle it

Take an exactly butterfly matrix A of rank k, apply Algorithm 2 with truncated SVD; since the optimal butterfly error is zero, the claimed guarantee demands the output B satisfies A=B exactly—any nonzero error at any size N falsifies the chain. Similarly, for Algorithm 3 on an exactly butterfly A with the specified oversampling, the recovered B must satisfy A=B up to floating-point rounding; a residual growing with N would refute the O(N^{1/4}) bound.

Watch

Extended reading notes

Core claim

The paper's central discovery is a recursive characterization of butterfly matrices (Theorem 4): B is a level-L butterfly matrix if and only if B = U X V^T, where U and V are block-diagonal with orthonormal k-column blocks, and X, partitioned into four equal blocks, has each block a level-(L−2) butterfly matrix. From this characterization the authors derive a greedy recursive meta-algorithm. At each level it computes near-optimal 'BF-out' approximations—matrices whose extreme complementary blocks are low-rank—and then recurses on the 2×2 blocks of the compressed core. The analysis shows the accumulated error is at most a factor Γ(L+2) times the optimal butterfly approximation error, with Γ=1

Load-bearing premise

The guarantees hinge on the imported BLR2 bound (Theorem 9) that near-optimal fits to each extreme block yield a near-optimal one-level approximation, together with the structural assumption that sketching errors stay additive and independent as they propagate through the recursion.

Editorial extensions

If this is right

  • With entry access, any N×N matrix can be compressed to butterfly form in O(N^2) operations within an O(sqrt(log N)) factor of the optimal butterfly approximation—a guarantee matching the only previous algorithm of this kind but via a simpler, recursive route.
  • With matvec-only access, a butterfly approximation within O(N^{1/4}) of optimal is achievable using ~O(sqrt(N)) matrix-vector products and ~O(N) working memory; this is the first quasi-optimality guarantee for the widely used hybrid butterfly factorization method.
  • Because the recursive format is a data structure rather than a product of sparse factors, it simplifies both implementation (an open-source Julia package is provided) and the analysis of butterfly algorithms.
  • Rank-adaptive and rectangular-matrix extensions follow from the same framework by using per-block rank selection and independent row/column trees, which the numerical experiments show works well on NUDFT and Hankel transform matrices.
  • The absolute-error bound (Theorem 15) gives implementable stopping criteria: if every complementary block is approximated to error ε (absolute or relative), the final butterfly has error bounded by a simple closed form—useful for practical accuracy control.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the O(N^{1/4}) factor can be improved to O(sqrt(log N)) while retaining O(N) memory, the matvec algorithm would match the entry-access guarantee; the authors' Theorem 17 (via BF-mid) already shows O(sqrt(L)) is possible at the cost of O(N^{3/2}) memory, suggesting a trade-off frontier worth exploring.
  • The recursive characterization may help in other butterfly-related problems, such as learning butterfly-structured neural-network layers or deriving lower bounds on matvec queries, since it exposes the hierarchical core in a form amenable to recursion arguments.
  • A testable extension: replace Gaussian sketches in Algorithm 3 with structured (e.g., subsampled random Fourier or sparse sign) sketches; Lemma 20's independence assumption might be relaxed, potentially reducing the oversampling polylog factors in practice.
  • The BLR2 connection (BF-out as a special case) suggests that quasi-optimal techniques for HSS and other hierarchical low-rank formats could be adapted to butterfly approximation, possibly leading to a family of provably near-optimal hierarchical compression algorithms.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper formalizes a recursive definition of butterfly matrices (Theorem 4) and uses it to design two approximation algorithms: an entry-access algorithm (Algorithm 2 / Corollary 13) that runs in O(N^2 k) time and achieves Frobenius error within O(√log N) of the best butterfly approximation, and a matvec algorithm (Algorithm 3) that uses O~(√N) matvec queries and achieves error within O(N^{1/4}) of optimal; a memory-efficient implementation (Algorithm 4, Appendix C) is claimed to reduce working memory to O~(N). The authors also identify their matvec algorithm as a reformulation of the hybrid butterfly factorization of Liu et al. and claim the first theoretical quasi-optimality guarantee for that method. Numerical experiments on noisy butterfly matrices, NUDFT, and Hankel transforms are reported, along with an open-source Julia implementation.

Significance. If the technical claims hold, this is a substantial contribution: it provides a clean recursive characterization of butterfly matrices, gives the first quasi-optimality guarantee for the widely used matvec-based hybrid butterfly factorization, and matches the best known entry-access guarantee with a simpler algorithm. The proof of Theorem 4 is detailed and self-contained, and the inductions in Theorems 10 and 12 and Lemma 20 are internally consistent. The randomized analysis is sophisticated and mostly rigorous, and the paper ships reproducible code and experiments that honestly separate worst-case bounds from observed behavior. The main caveats are the heavy reliance on an imported result from a companion paper for the central BF-out approximation bound, and the fact that the advertised O~(N)-memory variant is asserted without a formal proof.

major comments (2)
  1. [Section 3.1, Theorem 9] Theorem 9 is load-bearing: the upper bound ∥A−B∥² ≤ 2Γ min_{BF-out} is used in Theorem 12 and Lemma 19, and the lower-bound inequality is used in Lemma 19 and Theorem 15. The paper says the result follows 'immediately' from [3, Theorem C.3] via the identification BF-out(L,k)=BLR2(2L,2k,k,∅) in Remark 8, but neither the exact statement of [3, Theorem C.3] nor the verification of the parameter mapping is provided. The lower-bound part can be derived directly from Definition 7, but the upper-bound part is a genuine import. Please include a self-contained proof of the upper bound, or quote [3, Theorem C.3] in full and prove the mapping and the constant 2Γ.
  2. [Appendix C, Algorithms 4–5] The abstract's central claim of O~(N) working memory for the matrix-free variant rests on Appendix C, which states that the memory-efficient implementation has 'memory complexity improved to O(N k log(N/k))' and that 'the output and approximation guarantees remain unchanged.' No theorem or proof is given. The analysis in Section 4.2 and Theorem 22 applies to Algorithm 3, which stores all sketches upfront with O(αN√(N k)) memory. Please add a formal statement that Algorithm 4 produces the same output distribution (or the same error guarantee with the same probability) as Algorithm 3, together with a proof of the memory bound, or revise the advertised claims.
minor comments (4)
  1. [Definitions 1–2 and throughout] The text repeatedly says 'as in Theorem 1' and 'by Theorem 2' when referring to Definition 1 and Definition 2 (e.g., Definition 2, Definition 7, Lemma 23). Please fix the cross-references.
  2. [Lemma 20 and Theorem 22] The probability expression '1− L+2/2 δ' is ambiguous; it should be written as 1−((L+2)/2)δ. Similarly, in the proof of Theorem 22, 'eδ= 2/L+2 δ' should be 'eδ = 2δ/(L+2)'.
  3. [Section 4, notation] The text says O~(·) suppresses polynomial factors in L=O(log N); these are polylogarithmic factors in N. The terminology is understandable but could be clarified.
  4. [Corollary 13] The complexity statement O(N²k) is correct for fixed k, but the abstract says O(N²); please state the k-dependence explicitly in the abstract or introduction.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the quasi-optimality results are derived from a recursive characterization plus an imported BLR2 bound that constitutes independent support, not a fit or a self-justifying definition.

full rationale

The paper's central claims do not reduce to their inputs by construction. Theorem 4 gives a recursive characterization of butterfly matrices and is proved in Appendix A via the leftfold/side/halving bookkeeping; it is not assumed as the definition. The entry-access guarantee (Theorem 12) follows by induction from Theorem 9, Theorem 10, and an exact Pythagorean decomposition; no parameter is fitted to make the conclusion hold. The matvec guarantee (Theorem 22) is derived from randomized sketching lemmas (Lemma 18, Lemma 19, Lemma 20, Lemma 21) with explicit oversampling and failure-probability dependencies; the error propagation is analyzed, not assumed by renaming. The one load-bearing external input is Theorem 9, imported from [3, Theorem C.3 and Remark 3.6] via the identification BF-out(L,k)=BLR2(2L,2k,k,∅). This is a citation to prior work with overlapping authors, but it is an independently stated theorem about a different matrix class (BLR2/HSS), with assumptions that do not include the target butterfly-optimality result. Under the provided review rules, such a citation counts as real evidence and does not by itself raise the circularity score. The lower-bound half of Theorem 9 is also a direct consequence of the extreme-block rank constraints, not a fitted input. If [3]'s constants or the BF-out/BLR2 identification were wrong, that would be a correctness risk, not circularity. The numerical experiments against known transforms provide additional external sanity checks. Overall, I find no step where a 'prediction' is equivalent by construction to a fitted quantity or to a self-citation chain.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical entities, forces, or fitted constants. The main algorithm parameters are the rank k and oversampling \alpha, both chosen by the user or by the analysis rather than fitted to data. The central derivation relies on standard randomized linear algebra and on one external BLR2 theorem from the authors’ companion paper.

assumptions (4)
  • domain assumption Complementary low-rank property is assumed to hold exactly, not approximately, for the recursive characterization to be an equivalence.
    Stated after Definition 2: the authors assume blocks are exactly low-rank, which is necessary for the equivalence between complementary low-rank and the recursive factorization.
  • domain assumption Matrix dimension is restricted to N=2^{L+1}k with even L and a perfect dyadic partition tree.
    Remark 3 and Theorem 1; extensions to rectangular matrices and arbitrary trees are described but not analyzed in the main theorems.
  • standard math Random Gaussian sketch matrices provide the subspace-embedding and low-rank recovery guarantees used in Lemma 18 and Lemma 21.
    The proofs invoke established randomized linear algebra bounds from [24, 34, 17].
  • domain assumption Theorem 9, imported from [3, Theorem C.3], correctly bounds the error of greedy BF-out approximation.
    Section 3.1 uses this external BLR2 result as the engine for all subsequent quasi-optimality guarantees; the paper does not prove it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A recursive butterfly factorization with optimality guarantees." pith.science (2026). https://pith.science/paper/ZBVTWA64

@misc{pith2026260729361,
  author       = {Pith},
  title        = {Pith review of: A recursive butterfly factorization with optimality guarantees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZBVTWA64}},
  note         = {Machine review of arXiv:2607.29361}
}
abstract

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})$ matrix-vector products and $\widetilde{O}(N)$ working memory and, with high probability, returns a butterfly approximation with Frobenius norm error within a $O(N^{1/4})$-factor of the optimal error. We show that the algorithm is a reformulation of the hybrid butterfly factorization approach presented in [Liu et. al.; SISC, 43 (2021)]. Our paper therefore provides the first theoretical quasi-optimality guarantee for that algorithm.

Figures

Figures reproduced from arXiv: 2607.29361 by the authors.

Figure 1
Figure 1. A perfect dyadic partition tree corresponding to the index sets defined in Theorem 1 for L = 3. Also related to our work is [38], which describes a random access butterfly algorithm based on the inter￾polative decomposition. This algorithm runs in O(N log(N)) time, but cannot be guaranteed to obtain a good approximation in the worst-case, even when the input A is itself a butterfly matrix. Notably however, like our … view at source ↗
Figure 2
Figure 2. Illustration of the submatrices B(Ii,ℓ, Ij,L−ℓ) from Theorem 2. The complementary low-rank property asserts these submatrices are all of rank at most k. Here L = 4, and the boxes in the light grey grid are of size 2k × 2k. 2.3 Butterfly matrices We define butterfly matrices using the so-called complementary low-rank property; see for example [28]. Definition 2 (Butterfly matrix). Let L, k ∈ N be fixed, and assume th… view at source ↗
Figure 3
Figure 3. Let B ∈ BF(L, k). The complementary low-rank property (Theorem 2) at the extreme levels (ℓ = 0 and ℓ = L) implies B ∈ BF-out(L, k) (see Theorem 7), and hence gives a factorization B = UXV T, where U and V are block-diagonal matrices with orthonormal columns. Theorem 4 asserts that X is a 2×2 block-matrix, where each block is in BF(L − 2, k). That is, each block in the 2 × 2 structure of X satisfies the complementary… view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Visualization of the nonzero entries of the sketch matrices Ω(ℓ) defined in (4) for L = 4. On the right, we illustrate the partitioning of Ω(ℓ) into Ω (ℓ) [1] and Ω (ℓ) [2] for ℓ = 4. The same block-diagonal structure is also used for the other ℓ. almost surely. With t…
Figure 5
Figure 5. Figure 5: Performance of Algorithm 2 (labeled “entry eval”) and Algorithm 3 (labeled “matvec”) for random butterfly matrices with k = 8 and additive noise σ = 10−4 . (a) Example random noisy butterfly matrix A with L = 4. (b) Log-log plot of recovery error of Algorithm 3 for var…
Figure 6
Figure 6. Figure 6: Performance of Algorithm 2 (labeled “entry eval”) and Algorithm 3 (labeled “matvec”) for NUDFT matrices using tolerance ϵ = 10−4 and 40 sketch vectors to recover each basis. (a) Example NUDFT matrix with N = 256. (b) Log-log plot of runtime of both algorithms as well a…
Figure 7
Figure 7. Figure 7: Performance of Algorithm 2 (labeled “entry eval”) and Algorithm 3 (labeled “matvec”) for Hankel transform matrices using tolerance ϵ = 10−4 and 20 sketch vectors to recover each basis. (a) Example Hankel transform matrix with N = 256. (b) Log-log plot of runtime of bot…
Figure 8
Figure 8. Figure 8: Visualization of leftfold and side operations for ℓ = 3. and the following operations leftfold : domain(leftfold) → range(leftfold) ⊂ T , leftfold(Ii,ℓ) = ( Ii,ℓ if i ≤ 2 ℓ−1 , Ii−2 ℓ−1,ℓ otherwise, side : domain(leftfold) → {1, 2}, side(Ii,ℓ) = ( 1 if i ≤ 2 ℓ−1 , 2 ot…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

67 extracted references · 22 canonical work pages

  1. [3]

    and Ho, Kenneth L

    Li, Yingzhou and Yang, Haizhao and Martin, Eileen R. and Ho, Kenneth L. and Ying, Lexing , title =. Multiscale Modeling & Simulation , volume =. 2015 , doi =

    2015

  2. [1]

    arXiv preprint arXiv:2505.16937 , year=

    Quasi-optimal hierarchically semi-separable matrix approximation , author=. arXiv preprint arXiv:2505.16937 , year=

    arXiv

  3. [2]

    Amsel, Noah and Chen, Tyler and Keles, Feyza Duman and Halikias, Diana and Musco, Cameron and Musco, Christopher and Persson, David , TITLE =. SIAM J. Matrix Anal. Appl. , FJOURNAL =. 2026 , NUMBER =. doi:10.1137/25M176622X , URL =

    work page doi:10.1137/25m176622x 2026

  4. [4]

    and Ho, Kenneth L

    Li, Yingzhou and Yang, Haizhao and Martin, Eileen R. and Ho, Kenneth L. and Ying, Lexing , TITLE =. Multiscale Model. Simul. , FJOURNAL =. 2015 , NUMBER =. doi:10.1137/15M1007173 , URL =

    work page doi:10.1137/15m1007173 2015

  5. [5]

    Proceedings of the 2025

    Chen, Tyler and Keles, Feyza Duman and Halikias, Diana and Musco, Cameron and Musco, Christopher and Persson, David , TITLE =. Proceedings of the 2025. 2025 , ISBN =. doi:10.1137/1.9781611978322.87 , URL =

    work page doi:10.1137/1.9781611978322.87 2025

  6. [6]

    On randomized trace estimates for indefinite matrices with an application to determinants , author=. Found. Comput. Math. , fjournal=. 2021 , url =

    2021

  7. [7]

    Cortinovis, Alice and Kressner, Daniel , TITLE =. Found. Comput. Math. , FJOURNAL =. 2022 , NUMBER =. doi:10.1007/s10208-021-09525-9 , URL =

    doi:10.1007/s10208-021-09525-9 2022

  8. [8]

    and Martinsson, P

    Halko, N. and Martinsson, P. G. and Tropp, J. A. , TITLE =. SIAM Rev. , FJOURNAL =. 2011 , NUMBER =. doi:10.1137/090771806 , URL =

    doi:10.1137/090771806 2011

Show all 67 references
  1. [10]

    and Yang, Haizhao , TITLE =

    Pang, Qiyuan and Ho, Kenneth L. and Yang, Haizhao , TITLE =. SIAM J. Sci. Comput. , FJOURNAL =. 2020 , NUMBER =. doi:10.1137/19M1294873 , URL =

    2020 doi

  2. [11]

    and Dewilde, P

    Chandrasekaran, S. and Dewilde, P. and Gu, M. and Pals, T. and van der Veen, A. J. , year =. Fast Stable Solver for Sequentially Semi-separable Linear Systems of Equations , ISBN =. doi:10.1007/3-540-36265-7_51 , booktitle =

    doi

  3. [12]

    Ashcraft, Cleve and Buttari, Alfredo and Mary, Theo , TITLE =. SIAM J. Matrix Anal. Appl. , FJOURNAL =. 2021 , NUMBER =. doi:10.1137/20M1386451 , URL =

    2021 doi

  4. [13]

    and Martinsson, Per-Gunnar , TITLE =

    Gillman, Adrianna and Young, Patrick M. and Martinsson, Per-Gunnar , TITLE =. Front. Math. China , FJOURNAL =. 2012 , NUMBER =. doi:10.1007/s11464-012-0188-3 , URL =

    2012 doi

  5. [14]

    Martinsson, P. G. and Rokhlin, V. , TITLE =. J. Comput. Phys. , FJOURNAL =. 2005 , NUMBER =. doi:10.1016/j.jcp.2004.10.033 , URL =

    2005 doi

  6. [15]

    arXiv preprint arXiv:2507.19290 , year=

    Query Efficient Structured Matrix Learning , author=. arXiv preprint arXiv:2507.19290 , year=

    arXiv

  7. [17]

    Le, Quoc-Tung and Zheng, L\'eon and Riccietti, Elisa and Gribonval, R\'emi , TITLE =. SIAM J. Matrix Anal. Appl. , FJOURNAL =. 2025 , NUMBER =. doi:10.1137/24M1708796 , URL =

    2025 doi

  8. [18]

    arXiv preprint arXiv:2009.11392 , year=

    Fast and stable randomized low-rank matrix approximation , author=. arXiv preprint arXiv:2009.11392 , year=

    2009 arXiv

  9. [19]

    arXiv preprint arXiv:2004.08434 , year=

    Projection-cost-preserving sketches: Proof strategies and constructions , author=. arXiv preprint arXiv:2004.08434 , year=

    2004 arXiv

  10. [20]

    and Woodruff, David P

    Bakshi, Ainesh and Clarkson, Kenneth L. and Woodruff, David P. , booktitle =. Low-rank approximation with

  11. [21]

    Krylov Methods are (nearly) Optimal for Low-Rank Approximation , url =

    Bakshi, Ainesh and Narayanan, Shyam , year =. Krylov Methods are (nearly) Optimal for Low-Rank Approximation , url =. doi:10.1109/focs57990.2023.00128 , booktitle =

    2023

  12. [22]

    2018 , ISBN =

    Simchowitz, Max and El Alaoui, Ahmed and Recht, Benjamin , TITLE =. 2018 , ISBN =. doi:10.1145/3188745.3188796 , URL =

    2018

  13. [23]

    2026 , eprint=

    Nearly Instance Optimal Sparse Matrix Approximation from Matrix-Vector Products , author=. 2026 , eprint=

    2026

  14. [24]

    arXiv preprint arXiv:2606.12179 , year=

    Nearly Instance Optimal Sparse Matrix Approximation from Matrix-Vector Products , author=. arXiv preprint arXiv:2606.12179 , year=

    arXiv

  15. [25]

    SIAM Journal on Matrix Analysis and Applications , volume =

    Amsel, Noah and Chen, Tyler and Keles, Feyza Duman and Halikias, Diana and Musco, Cameron and Musco, Christopher , title =. SIAM Journal on Matrix Analysis and Applications , volume =. 2026 , doi =

    2026

  16. [26]

    Amsel, Noah and Chen, Tyler and Keles, Feyza Duman and Halikias, Diana and Musco, Cameron and Musco, Christopher , TITLE =. SIAM J. Matrix Anal. Appl. , FJOURNAL =. 2026 , NUMBER =. doi:10.1137/25M1742710 , URL =

    2026 doi

  17. [28]

    Park, Taejun and Nakatsukasa, Yuji , TITLE =. Appl. Comput. Harmon. Anal. , FJOURNAL =. 2026 , PAGES =. doi:10.1016/j.acha.2026.101869 , URL =

    2026

  18. [29]

    , TITLE =

    Dasarathy, Gautam and Shah, Parikshit and Bhaskar, Badri Narayan and Nowak, Robert D. , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 2015 , NUMBER =. doi:10.1109/TIT.2015.2391251 , URL =

    2015

  19. [30]

    arXiv preprint arXiv:1311.2448 , year=

    Recovery of sparse matrices via matrix sketching , author=. arXiv preprint arXiv:1311.2448 , year=

    arXiv

  20. [31]

    Curtis, A. R. and Powell, M. J. D. and Reid, J. K. , year =. On the Estimation of Sparse. J. Inst. Math. Appl. , fjournal =. doi:10.1093/imamat/13.1.117 , number =

    doi

  21. [33]

    and Mor\'e, Jorge J

    Coleman, Thomas F. and Mor\'e, Jorge J. , TITLE =. SIAM J. Numer. Anal. , FJOURNAL =. 1983 , NUMBER =. doi:10.1137/0720013 , URL =

    1983 doi

  22. [34]

    and Cai, Jin-Yi , TITLE =

    Coleman, Thomas F. and Cai, Jin-Yi , TITLE =. SIAM J. Algebraic Discrete Methods , FJOURNAL =. 1986 , NUMBER =. doi:10.1137/0607026 , URL =

    1986 doi

  23. [35]

    Dharangutte, Prathamesh and Musco, Christopher , TITLE =. 2023. 2023 , ISBN =. doi:10.1137/1.9781611977585.ch32 , URL =

    2023 doi

  24. [36]

    arXiv preprint arXiv:2201.10684 , year=

    Stochastic diagonal estimation: probabilistic bounds and an improved algorithm , author=. arXiv preprint arXiv:2201.10684 , year=

    arXiv

  25. [37]

    and Saad, Yousef , TITLE =

    Tang, Jok M. and Saad, Yousef , TITLE =. Numer. Linear Algebra Appl. , FJOURNAL =. 2012 , NUMBER =. doi:10.1002/nla.779 , URL =

    2012 doi

  26. [38]

    and Kokiopoulou, E

    Bekas, C. and Kokiopoulou, E. and Saad, Y. , TITLE =. Appl. Numer. Math. , FJOURNAL =. 2007 , NUMBER =. doi:10.1016/j.apnum.2007.01.003 , URL =

    2007 doi

  27. [39]

    Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Toeplitz low-rank approximation with sublinear query complexity , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  28. [40]

    Proceedings of the 2023

    Kapralov, Michael and Lawrence, Hannah and Makarov, Mikhail and Musco, Cameron and Sheth, Kshiteej , TITLE =. Proceedings of the 2023. 2023 , ISBN =. doi:10.1137/1.9781611977554.ch159 , URL =

    2023 doi

  29. [41]

    A Butterfly-Based Direct Integral-Equation Solver Using Hierarchical

    Guo, Han and Liu, Yang and Hu, Jun and Michielssen, Eric , year =. A Butterfly-Based Direct Integral-Equation Solver Using Hierarchical. IEEE Transactions on Antennas and Propagation , publisher =. doi:10.1109/tap.2017.2727511 , number =

    2017

  30. [42]

    Liu, Yang and Xing, Xin and Guo, Han and Michielssen, Eric and Ghysels, Pieter and Li, Xiaoye Sherry , TITLE =. SIAM J. Sci. Comput. , FJOURNAL =. 2021 , NUMBER =. doi:10.1137/20M1315853 , URL =

    2021 doi

  31. [43]

    Sch\"afer, Florian and Katzfuss, Matthias and Owhadi, Houman , TITLE =. SIAM J. Sci. Comput. , FJOURNAL =. 2021 , NUMBER =. doi:10.1137/20M1336254 , URL =

    2021 doi

  32. [44]

    Waters, Andrew and Sankaranarayanan, Aswin and Baraniuk, Richard , booktitle =. Spa

  33. [45]

    arXiv preprint arXiv:2605.21828 , year=

    A Butterfly-Accelerated Manifold Harmonic Transform , author=. arXiv preprint arXiv:2605.21828 , year=

    arXiv

  34. [46]

    An algorithm for the rapid evaluation of special function transforms , author=. Appl. Comput. Harm. Anal. , volume=. 2010 , publisher=

    2010

  35. [47]

    O'Neil, Michael and Woolfe, Franco and Rokhlin, Vladimir , TITLE =. Appl. Comput. Harmon. Anal. , FJOURNAL =. 2010 , NUMBER =. doi:10.1016/j.acha.2009.08.005 , URL =

    2010 doi

  36. [48]

    Interpolative butterfly factorization , author=. SIAM J. Sci. Comput. , volume=. 2017 , publisher=

    2017

  37. [49]

    Li, Yingzhou and Yang, Haizhao , TITLE =. SIAM J. Sci. Comput. , FJOURNAL =. 2017 , NUMBER =. doi:10.1137/16M1074941 , URL =

    2017 doi

  38. [50]

    2009 , publisher=

    Candes, Emmanuel and Demanet, Laurent and Ying, Lexing , journal=. 2009 , publisher=

    2009

  39. [51]

    Multiscale Model

    Cand\`es, Emmanuel and Demanet, Laurent and Ying, Lexing , TITLE =. Multiscale Model. Simul. , FJOURNAL =. 2009 , NUMBER =. doi:10.1137/080734339 , URL =

    2009 doi

  40. [52]

    2010 , publisher=

    Tygert, Mark , journal=. 2010 , publisher=

    2010

  41. [53]

    Tygert, Mark , TITLE =. J. Comput. Phys. , FJOURNAL =. 2010 , NUMBER =. doi:10.1016/j.jcp.2010.05.004 , URL =

    2010 doi

  42. [54]

    2012 , publisher=

    Seljebotn, DS , journal=. 2012 , publisher=

    2012

  43. [55]

    Seljebotn, D. S. , title =. 2012 , month =. doi:10.1088/0067-0049/199/1/5 , url =

    2012 doi

  44. [56]

    A butterfly algorithm for synthetic aperture radar imaging , author=. SIAM J. Imag. Sci. , volume=. 2012 , publisher=

    2012

  45. [57]

    IEEE Transactions on Antennas and Propagation , volume=

    A multilevel matrix decomposition algorithm for analyzing scattering from large structures , author=. IEEE Transactions on Antennas and Propagation , volume=. 1996 , publisher=

    1996

  46. [58]

    and Boag, A

    Michielssen, E. and Boag, A. , journal=. A multilevel matrix decomposition algorithm for analyzing scattering from large structures , year=

  47. [59]

    International conference on machine learning , pages=

    Learning fast algorithms for linear transforms using butterfly factorizations , author=. International conference on machine learning , pages=. 2019 , organization=

    2019

  48. [60]

    Proceedings of the 36th International Conference on Machine Learning , pages =

    Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations , author =. Proceedings of the 36th International Conference on Machine Learning , pages =. 2019 , volume =

    2019

  49. [61]

    International Conference on Learning Representations , volume=

    Parameter-efficient orthogonal finetuning via butterfly factorization , author=. International Conference on Learning Representations , volume=

  50. [62]

    Parameter-Efficient Orthogonal Finetuning via Butterfly Factorization , url =

    Liu, Weiyang and Qiu, Zeju and Feng, Yao and Xiu, Yuliang and Xue, Yuxuan and Yu, Longhui and Feng, Haiwen and Liu, Zhen and Heo, Juyeon and Peng, Songyou and Wen, Yandong and Black, Michael J and Weller, Adrian and Ha, David , booktitle =. Parameter-Efficient Orthogonal Finet...

  51. [63]

    SIAM Journal on Mathematics of Data Science , volume=

    Efficient identification of butterfly sparse matrix factorizations , author=. SIAM Journal on Mathematics of Data Science , volume=. 2023 , publisher=

    2023

  52. [64]

    Zheng, L\'eon and Riccietti, Elisa and Gribonval, R\'emi , TITLE =. SIAM J. Math. Data Sci. , FJOURNAL =. 2023 , NUMBER =. doi:10.1137/22M1488727 , URL =

    2023 doi

  53. [65]

    SIAM Journal on Scientific Computing , volume=

    Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations , author=. SIAM Journal on Scientific Computing , volume=. 2021 , publisher=

    2021

  54. [66]

    Liu, Yang and Ghysels, Pieter and Claus, Lisa and Li, Xiaoye Sherry , TITLE =. SIAM J. Sci. Comput. , FJOURNAL =. 2021 , NUMBER =. doi:10.1137/20M1349667 , URL =

    2021 doi

  55. [67]

    A parallel nonuniform fast

    Barnett, Alexander H and Magland, Jeremy and af Klinteberg, Ludvig , journal=. A parallel nonuniform fast. 2019 , publisher=

    2019

  56. [68]

    and Magland, Jeremy and af Klinteberg, Ludvig , TITLE =

    Barnett, Alexander H. and Magland, Jeremy and af Klinteberg, Ludvig , TITLE =. SIAM J. Sci. Comput. , FJOURNAL =. 2019 , NUMBER =. doi:10.1137/18M120885X , URL =

    2019 doi

  57. [69]

    A Nonuniform Fast

    Beckman, Paul G and O’Neil, Michael , journal=. A Nonuniform Fast. 2026 , publisher=

    2026

  58. [70]

    and O'Neil, Michael , TITLE =

    Beckman, Paul G. and O'Neil, Michael , TITLE =. SIAM J. Sci. Comput. , FJOURNAL =. 2026 , NUMBER =. doi:10.1137/25M1796758 , URL =

    2026 doi

  59. [71]

    Proceedings of Thirty Ninth Conference on Learning Theory , pages =

    Query Efficient Structured Matrix Learning , author =. Proceedings of Thirty Ninth Conference on Learning Theory , pages =. 2026 , editor =

    2026

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.