Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

Quasi-optimal hierarchically semi-separable matrix approximation

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

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

Pith's one-line read This paper proves that a randomized matrix-vector algorithm can approximate any N×N matrix by a hierarchically semi-separable rank-k matrix with expected squared error within O(log(N/k)) of optimal, using O(k log(N/k)) matrix-vector…

desk verdict First provable quasi-optimal HSS approximation from matvecs, with a clean meta-theorem and a glaring-but-fixable typo: the factor p in Theorem 4.2 is spurious and should be removed. read the letter →

arxiv 2505.16937 v2 pith:RW4HAINF submitted 2025-05-22 math.NA cs.DScs.NA

Noah Amsel , Tyler Chen , Feyza Duman Keles , Diana Halikias , Cameron Musco , Christopher Musco , David Persson This is my paper
classification math.NAcs.DScs.NA MSC 65N2265N3815A2315A52
keywords randomizedapproximationofmatricesrank-structuredhierarchicallysemi-separablematrixblockseparableSVDmatrix-vectorquerymodelprojection-cost-preservingsketchesquasi-optimality
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

The paper establishes the first polynomial-time quasi-optimality guarantee for approximating a general N×N matrix by a hierarchically semi-separable (HSS) matrix, in both the explicit-entry access model and the black-box matrix-vector product model. Its main result is a randomized algorithm, a modified version of a method proposed in [43], that uses O(k log(N/k)) matrix-vector products with A and Aᵀ and O(N k² log(N/k)) additional runtime to return an HSS rank-k matrix B whose expected squared Frobenius error is within an O(log(N/k)) factor of the best HSS rank-k approximation. The proof works level by level: each level of the HSS hierarchy is treated as a sequentially semi-separable (SSS) approximation, and fresh random sketches per level keep the errors from different levels independent. A companion explicit-access result gives a 2 log₂(N/k)-factor guarantee in O(N² k) time. If correct, this makes HSS compression from matrix-vector queries a provably tractable primitive for fast solvers and operator learning.

What carries the argument

The argument is carried by a greedy level-by-level construction of the HSS telescoping factorization: at each level, the algorithm fits a sequentially semi-separable (SSS) matrix to the current compressed matrix, then compresses the residual. A lemma shows the best HSS error cannot increase under the projection used to pass to the next level, so the $L$ independent SSS fits accumulate only an $O(L)$ factor. In the matvec setting, block nullification simulates Gaussian sketches of block rows and columns from full-matrix matvecs with $A$ and $A^T$, and fresh random sketches per level keep the errors independent. A projection-cost-preserving sketch bound (Theorem 4.2) converts those sketches into near-optimal subspaces, and a robust diagonal-block estimator (Theorem 4.4) recovers the diagonal blocks without needing exact HSS structure.

What would settle it

Compute, for a tall matrix $B$ with a fixed number of rows and many columns $p$, the ratio $\mathbb{E}[\|B - UU^T B\|_F^2]/\|B - [B]_k\|_F^2$ where $U$ comes from a Gaussian sketch with $q$ columns, and compare it with the bound $1 + 2e q p/((q-k)^2 - 1)$. If the ratio grows with $p$, the proof of Theorem 4.2 is invalid as stated and the main theorem's level-by-level argument collapses; if it does not, the missing uniform bound is available.

Watch

Extended reading notes

Core claim

The central discovery is that quasi-optimal HSS approximation does not require exact recovery of each block's singular subspaces, nor reuse of sketches across levels. Theorem 4.1 states that for $s \geq 3k+2$, Algorithm 4.1 uses $O(sL)$ matvecs and $O(N k s L + N s^2)$ runtime to return $B \in \mathrm{HSS}(L,k)$ with $\mathbb{E}[\|A-B\|_F^2] \leq O(L) \min_{C \in \mathrm{HSS}(L,k)} \|A-C\|_F^2$; choosing $s=5k$ gives $O(k \log(N/k))$ matvecs and an $O(\log(N/k))$ quasi-optimality factor. The proof instantiates a general greedy meta-algorithm (Algorithm 3.1) by arguing that solving an SSS approximation at each level, using independent projection-cost-preserving sketches and block nullification, accumulates only one $O(1)$ error factor per level. The paper also proves the first relative-error guarantee for explicit-access HSS approximation (a $2 \log_2(N/k)$ factor) and explicit error bounds for projection-cost-preserving sketches that are of independent interest. It further shows the greedy method cannot be tuned to $(1+\varepsilon)$-optimality: a constructed matrix forces a factor arbitrarily close to 2.

Load-bearing premise

The main theorem depends on the projection-cost-preserving sketch bound in Theorem 4.2 being essentially independent of the width $p$ of a block row; if the factor $p$ in the stated bound is genuine, each level's basis degrades with the matrix dimension and the $O(L)$ quasi-optimality conclusion does not follow.

Editorial extensions

If this is right

  • HSS matrices can now be compressed from black-box matvec queries with a provable guarantee: $O(k \log(N/k))$ queries suffice for an $O(\log(N/k))$ approximation factor.
  • The same level-by-level greedy scheme with truncated SVDs on block rows and columns gives the first polynomial-time relative-error bound for explicit-access HSS approximation, at $O(N^2 k)$ cost.
  • Markov's inequality converts the expected-error bound into a high-probability guarantee: with probability $1-\delta$, the returned HSS matrix satisfies the desired relative-error bound with $\Gamma = O(\log(N/k)/\delta)$.
  • Because the diagonal-block estimator is tolerant of matrices that are only approximately HSS, the method applies to integral operators, inverse covariance matrices, and other nearly-HSS matrices, not just exactly HSS ones.
  • The fresh-sketch variant is less query-efficient than sketch reuse in practice, so the paper leaves open whether the logarithmic query factor can be removed while keeping a strong guarantee.

Reading between the lines

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

  • Inference: If the $p$-dependence in Theorem 4.2 is an artifact of the proof rather than a genuine phenomenon, the same machinery likely yields a $p$-independent constant and the $O(\log(N/k))$ factor in the main theorem might be improvable to a constant; checking that bound numerically on matrices with many columns would settle this.
  • Inference: The greedy level-by-level decomposition transfers naturally to other hierarchical formats with shared bases, such as H2 matrices; the paper's observation that shared-bases classes lack polynomial optimal approximation algorithms suggests fresh-sketch analyses could produce the first quasi-optimal guarantees there too.
  • Inference: The lower-bound example in Theorem 3.7 indicates the greedy strategy itself is limited to a factor of 2, so any hope of a $(1+\varepsilon)$-optimal HSS approximation would require a different algorithmic principle, not a sharper analysis of the greedy recursion.
  • Inference: Experiments showing sketch reuse beats fresh sketches at fixed query budget suggest the true query complexity of quasi-optimal HSS approximation may be $O(k)$ rather than $O(k \log(N/k))$; a refined analysis of reuse dependencies would be the natural test.
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 presents a randomized algorithm for computing a quasi-optimal hierarchically semi-separable (HSS) approximation to an N x N matrix A using only matrix-vector products with A and A^T. The main result, Theorem 4.1, claims that with O(k log(N/k)) matvecs and O(N k^2 log(N/k)) additional runtime, the algorithm returns an HSS(L,k) approximation B with E[||A-B||_F^2] at most O(log(N/k)) times the optimal HSS approximation error. The analysis proceeds through a greedy meta-algorithm (Algorithm 3.1), a theorem bounding its performance via level-wise SSS approximation (Theorem 3.1), a near-optimal SSS approximation result (Theorem 3.3), a monotonicity lemma for HSS optima (Lemma 3.4), an explicit projection-cost-preserving sketch bound (Theorem 4.2), a diagonal-block estimator (Theorem 4.4), and a construction showing that the explicit greedy algorithm cannot beat a factor arbitrarily close to 2 (Theorem 3.7). Numerical experiments compare the fresh-sketch variant with the sketch-reuse algorithm of Levitt and Martinsson.

Significance. If the corrections below are made, this is a substantial contribution: it appears to give the first polynomial-time quasi-optimality guarantee for HSS approximation in the explicit-access model and in the matrix-vector query model. The proof architecture is clean: the greedy level-by-level view, Lemma 3.4 connecting each level's optimum to the global HSS optimum, and the induction in Theorem 3.1 together provide a genuine O(L) bound. The explicit PCPS constants in Theorem 4.2 are of independent interest, the lower bound for greedy in Theorem 3.7 is a useful counterpoint to the upper bounds, and the experiments are reproducible with released code. The main issues are two formal errors in central theorem statements, both of which appear to be typos that the proofs themselves indicate how to fix.

major comments (2)
  1. [Theorem 3.1, Eq. (3.1)] The displayed bound is written as (Gamma_r + Gamma_c)(1 + Gamma_d)^L, but the proof does not establish an exponential factor. Combining Eq. (3.10) and Eq. (3.11) gives (Gamma_r + Gamma_c)(1 + Gamma_d) L, since the first term contributes the factor (1 + Gamma_d)(Gamma_r + Gamma_c) and the inductive second term contributes (1 + Gamma_d)(Gamma_r + Gamma_c)(L - 1). With the exponential form as written, the choice s = 5k in Theorem 4.1 gives Gamma_d roughly 2/3 and the claimed Gamma = O(L) would be false for fixed constants. Eq. (3.1) should be corrected to the linear-in-L bound, and all subsequent citations of this factor should be updated accordingly.
  2. [Theorem 4.2 and Theorem 4.1, Eqs. (4.6)-(4.7); Theorem C.4] The factor p in the numerator of the PCPS bound is not supported by the proof. The two probabilistic estimates E||Sigma_2 Omega_2||_F^2 = q||Sigma_2||_F^2 and E||Omega_1^dagger||_2^2 <= e^2 q/((q-k)^2 - 1) contain no p, so the inequality should be dimension-free in the column count p. As stated, the p is load-bearing: in Theorem 4.1 the matrix B is a block row with p = 2^{ell+1} k - 2k, so a genuine p factor would make Gamma_r and Gamma_c grow with N and would invalidate the claimed O(L) quasi-optimality factor. The p should be removed from Theorem 4.2, from the Gamma_r/Gamma_c formulas in Theorem 4.1, from Eqs. (4.6)-(4.7), and from the analogous formula in Theorem C.4.
minor comments (4)
  1. [Theorem 3.1, assumption statement] The conditioning in the three expectation assumptions is written as conditional on A_i^{(ell+1)}, which is a block entry rather than a sigma-algebra; it should be conditional on A^{(ell+1)} (or on the algorithmic history up to that level). The proof's use of the law of total expectation appears consistent with the intended conditioning, but the notation should be clarified.
  2. [Proof of Theorem 3.7] The displayed ratio after the construction is garbled; the reasoning uses the ratio (2^{2L+1} - 2^{L+2})/(2^{2L} + delta 2^{L+1}), which tends to 2 as L grows. Please correct the displayed simplification so the limiting factor 2 - epsilon is transparent.
  3. [Appendix D] The closed-set characterization is written as HSS(L,k) = {B : f(A) = 0}; it should be f(B) = 0.
  4. [Algorithm C.1, lines 5 and 7] The indices in the basis computations appear to be swapped: the row basis U_i should be computed from Y_{R_i} P_{R_i} and the column basis V_j from Z_{C_j} Q_{C_j}, rather than from the blocks named YRj PCj and ZCj QRi in the current text.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the quasi-optimality guarantee follows from in-paper explicit bounds, and the self-citations to prior PCPS work are not load-bearing.

full rationale

The derivation chain is self-contained. Theorem 4.1 instantiates Theorem 3.1 with the basis-quality estimate of Theorem 4.2 and the diagonal estimate of Theorem 4.4, both proved in the paper from standard Gaussian matrix facts (Eckart-Young truncation, pseudo-inverse moment bounds); neither assumes the HSS quasi-optimality it helps establish. Theorem 3.1 is proved by induction using Theorem 3.3 and Lemma 3.4, with the existence of an optimal HSS approximation supplied by Appendix D, so no step defines the target error as an input or fits a parameter and then reports it as a prediction. The cited PCPS framework [26,58] is prior work by two of the authors, but the explicit bound actually used (Theorem 4.2) is derived in this paper, so the self-citation is motivational rather than load-bearing. The lower bound in Theorem 3.7 is an explicit construction. The only substantive issue found is a mathematical typo, not a circularity: Theorem 4.2's displayed constant contains a factor p that its own proof does not produce, since the proof uses a k by q matrix Omega_1 and the identity E ||Sigma_2 Omega_2||_F^2 = q ||Sigma_2||_F^2, which gives a q/sqrt((q-k)^2-1) dependence rather than q p. If the p were genuine, Theorem 4.1's constants would depend on block width, but that is a correctness or typo concern, not a reduction of the result to its inputs.

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

The central claim rests on standard randomized linear algebra tools and the HSS definition. No free parameters are fitted to data; the sketch size s and rank k are user inputs. No new physical or mathematical entities are introduced.

assumptions (3)
  • standard math Standard properties of Gaussian random matrices and Eckart-Young theorem
    Used throughout Sections 3 and 4, e.g., E||Sigma Omega||_F^2 = q||Sigma||_F^2 and the pseudoinverse bound in Theorem 4.2.
  • domain assumption HSS matrices admit a telescoping factorization (Definition 2.3) and an optimal HSS approximation exists (Appendix D)
    The paper proves existence in Appendix D, but relies on the definition to set up the approximation problem.
  • ad hoc to paper The matrix is square of size N = 2^{L+1}k with a perfect binary partition and leaf blocks of size 2k
    Remark 2.4 acknowledges this simplifies notation and claims extension to arbitrary N.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quasi-optimal hierarchically semi-separable matrix approximation." pith.science (2026). https://pith.science/paper/RW4HAINF

@misc{pith2026250516937,
  author       = {Pith},
  title        = {Pith review of: Quasi-optimal hierarchically semi-separable matrix approximation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RW4HAINF}},
  note         = {Machine review of arXiv:2505.16937}
}
abstract

We present a randomized algorithm for producing a quasi-optimal hierarchically semi-separable (HSS) approximation to an $N\times N$ matrix $A$ using only matrix-vector products with $A$ and $A^T$. We prove that, using $O(k \log(N/k))$ matrix-vector products and ${O}(N k^2 \log(N/k))$ additional runtime, the algorithm returns an HSS matrix $B$ with rank-$k$ blocks whose expected Frobenius norm error $\mathbb{E}[\|A - B\|_F^2]$ is at most $O(\log(N/k))$ times worse than the best possible approximation error by an HSS rank-$k$ matrix. In fact, the algorithm we analyze in a simple modification of an empirically effective method proposed by [Levitt & Martinsson, SISC 2024]. As a stepping stone towards our main result, we prove two results that are of independent interest: a similar guarantee for a variant of the algorithm which accesses $A$'s entries directly, and explicit error bounds for near-optimal subspace approximation using projection-cost-preserving sketches. To the best of our knowledge, our analysis constitutes the first polynomial-time quasi-optimality result for HSS matrix approximation, both in the explicit access model and the matrix-vector product query model.

Figures

Figures reproduced from arXiv: 2505.16937 by the authors.

Figure 1
Figure 1. N × 51 grid graph used for the second model problem, following the numerical experiments in [43]. N = 10 is pictured. random symmetric banded M and approximate A with a matrix B ∈ HSS(L, k) (i.e., smaller rank than needed to achieve zero error). Matrix-vector products with A are performed using a sparse Cholesky factorization of M. In our experiments, we set b = 17, N = 4096, L = 9, and k = 8. Schur complement of gr… view at source ↗
Figure 2
Figure 2. Domain D used for the boundary integral equation model problem in (5.1). 5.1. Results. We implement and run both [43, Algorithm 3.1] and Algorithm 4.1 on the test problems described above. To isolate the effect of the reuse of random sketches, we also address another implementation difference between the algorithms. Specifically, [43] computes the bases U(ℓ) and V (ℓ) using a pivoted QR decomposition, while Algorith… view at source ↗
Figure 3
Figure 3. Experimental results of HSS approximation on four model problems. Each line shows a different algorithm: Algorithm 4.1 (fresh sketches at each level; requires 4sL matvec queries), [43, Algorithm 3.1] (reused sketches across levels; basis found by pivoted QR; requires 4s matvec queries), reused sketches with the basis found by SVD (requires 4s matvec queries), the version of Algorithm 3.1 for explicit matrices (page … view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Categorization of hierarchical/rank-structured matrix classes. Arrows indicate a matrix-class becoming more restrictive; i.e. A → B means B ⊆ A. The orientation of the arrows indicates the additional property that defines the subset. In this paper we discuss algorithms…

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A recursive butterfly factorization with optimality guarantees

    math.NA 2026-07 conditional novelty 7.0 of 10

    A recursive butterfly representation leads to entry-access and matrix-free butterfly approximations with provably near-optimal error guarantees.

Reference graph

Works this paper leans on

76 extracted references · 68 canonical work pages · cited by 1 Pith paper

  1. [1]

    Ambartsumyan, W

    I. Ambartsumyan, W. Boukaram, T. Bui-Thanh, O. Ghattas, D. Keyes, G. Stadler, G. Turkiyyah, and S. Zampini , Hierarchical matrix approximations of Hessians arising in inverse problems governed by PDEs , SIAM J. Sci. Comput., 42 (2020), pp. A3397– A3426

    work page 2020

  2. [2]

    Ambikasaran, D

    S. Ambikasaran, D. Foreman-Mackey, L. Greengard, D. W. Hogg, and M. O’Neil , Fast direct methods for Gaussian processes , IEEE Transactions on Pattern Analysis and Machine Intelligence, 38 (2016), pp. 252–265

    work page 2016

  3. [3]

    Amsel, T

    N. Amsel, T. Chen, F. D. Keles, D. Halikias, C. Musco, and C. Musco, Fixed-sparsity ma- trix approximation from matrix-vector products , arXiv preprint arXiv:2402.09379, (2024)

    arXiv 2024

  4. [4]

    Ashcraft, A

    C. Ashcraft, A. Buttari, and T. Mary, Block low-rank matrices with shared bases: potential and limitations of the BLR2 format, SIAM J. Matrix Anal. Appl., 42 (2021), pp. 990–1010

    work page 2021

  5. [5]

    Askham, M

    T. Askham, M. Rachh, M. O’Neil, J. Hoskins, D. Fortunato, S. Jiang, F. Fryklund, T. Goodwill, H. Yang W ang, and H. Zhu , chunkIE: a MATLAB integral equation toolbox

    work page

  6. [6]

    Bakshi, K

    A. Bakshi, K. L. Clarkson, and D. P. Woodruff , Low-rank approximation with 1/ϵ1/3 matrix-vector products, in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2022, pp. 1130–1143

    work page 2022

  7. [7]

    Bakshi and S

    A. Bakshi and S. Narayanan, Krylov methods are (nearly) optimal for low-rank approxima- tion, in Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2023, pp. 2093–2101

    work page 2023

  8. [8]

    Ballani and D

    J. Ballani and D. Kressner , Matrices with hierarchical low-rank structures , in Exploiting hidden structure in matrix computations: algorithms and applications, vol. 2173 of Lecture Notes in Math., Springer, Cham, 2016, pp. 161–209

    work page 2016

Show all 76 references
  1. [9]

    Barnes and P

    J. Barnes and P. Hut , A hierarchical O(N log N ) force-calculation algorithm, Nature, 324 (1986), pp. 446–449

    1986

  2. [10]

    R. A. Baston and Y. Nakatsukasa, Stochastic diagonal estimation: probabilistic bounds and an improved algorithm , arXiv preprint arXiv:2201.10684, (2022)

    2022 arXiv

  3. [11]

    Bebendorf and W

    M. Bebendorf and W. Hackbusch , Existence of H-matrix approximants to the inverse FE- matrix of elliptic operators with L∞-coefficients, Numer. Math., 95 (2003), pp. 1–28

    2003

  4. [12]

    Bekas, E

    C. Bekas, E. Kokiopoulou, and Y. Saad , An estimator for the diagonal of a matrix , Appl. Numer. Math., 57 (2007), pp. 1214–1229

    2007

  5. [13]

    D. P. Bertsekas , Nonlinear programming, Athena Scientific Optimization and Computation Series, Athena Scientific, Belmont, MA, second ed., 1999

    1999

  6. [14]

    Bhatia, Matrix analysis, vol

    R. Bhatia, Matrix analysis, vol. 169 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1997

    1997

  7. [15]

    B¨orm, Efficient numerical methods for non-local operators , vol

    S. B¨orm, Efficient numerical methods for non-local operators , vol. 14 of EMS Tracts in Math- ematics, European Mathematical Society (EMS), Z¨ urich, 2010. H2-matrix compression, algorithms and analysis. QUASI-OPTIMAL HSS MATRIX APPROXIMATION 25

    2010

  8. [16]

    B ¨orm and K

    S. B ¨orm and K. Reimer , Efficient arithmetic operations for rank-structured matrices based on hierarchical low-rank updates, Comput. Vis. Sci., 16 (2013), pp. 247–258

    2013

  9. [17]

    Boukaram, G

    W. Boukaram, G. Turkiyyah, and D. Keyes , Hierarchical matrix operations on GPUs: matrix-vector multiplication and compression , ACM Trans. Math. Software, 45 (2019), pp. Art. 3, 28

    2019

  10. [18]

    Boull´e, C

    N. Boull´e, C. J. Earls, and A. Townsend , Data-driven discovery of Green ’s functions with human-understandable deep learning , Sci. Rep., 12 (2022), p. 4824

    2022

  11. [19]

    Boull´e, D

    N. Boull´e, D. Halikias, and A. Townsend , Elliptic PDE learning is provably data-efficient , Proc. Natl. Acad. Sci. USA, 120 (2023), pp. Paper No. e2303904120, 3

    2023

  12. [20]

    Boull´e and A

    N. Boull´e and A. Townsend, Learning elliptic partial differential equations with randomized linear algebra, Foundations of Computational Mathematics, 23 (2022), p. 709–739

    2022

  13. [21]

    Boull ´e and A

    N. Boull ´e and A. Townsend , Chapter 3 - a mathematical guide to operator learning , in Numerical Analysis Meets Machine Learning, vol. 25 of Handbook of Numerical Analysis, Elsevier, 2024, pp. 83–125

    2024

  14. [22]

    D. Cai, H. Huang, E. Chow, and Y. Xi , Data-driven construction of hierarchical matrices with nested bases , SIAM J. Sci. Comput., 46 (2024), pp. S24–S50

    2024

  15. [23]

    A. A. Casulli, D. Kressner, and L. Robol, Computing functions of symmetric hierarchically semiseparable matrices, SIAM J. Matrix Anal. Appl., 45 (2024), pp. 2314–2338

    2024

  16. [24]

    Chandrasekaran, P

    S. Chandrasekaran, P. Dewilde, M. Gu, T. Pals, and A. J. van der Veen , Fast Sta- ble Solver for Sequentially Semi-separable Linear Systems of Equations , Springer Berlin Heidelberg, 2002, p. 545–554

    2002

  17. [25]

    T. Chen, F. D. Keles, D. Halikias, C. Musco, C. Musco, and D. Persson , Near-optimal hierarchical matrix approximation from matrix-vector products, in Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, PA, 2025, pp. 2656–2692

    2025

  18. [26]

    Cohen, S

    M. Cohen, S. Elder, C. Musco, C. Musco, and M. Persu , Dimensionality reduction for k-means clustering and low rank approximation , in Proceedings of the 47th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2015, pp. 163–172

    2015

  19. [27]

    T. F. Coleman and J.-Y. Cai , The cyclic coloring problem and estimation of sparse Hessian matrices, SIAM J. Algebraic Discrete Methods, 7 (1986), pp. 221–235

    1986

  20. [28]

    T. F. Coleman and J. J. Mor ´e, Estimation of sparse Jacobian matrices and graph coloring blems, SIAM J. Numer. Anal., 20 (1983), p. 187–209

    1983

  21. [29]

    A. R. Curtis, M. J. D. Powell, and J. K. Reid , On the estimation of sparse Jacobian matrices, J. Inst. Math. Appl., 13 (1974), p. 117–119

    1974

  22. [30]

    Dasarathy, P

    G. Dasarathy, P. Shah, B. N. Bhaskar, and R. D. Nowak , Sketching sparse matrices, covariances, and graphs via tensor products , IEEE Trans. Inform. Theory, 61 (2015), pp. 1373–1388

    2015

  23. [31]

    Dharangutte and C

    P. Dharangutte and C. Musco, A tight analysis of Hutchinson ’s diagonal estimator, in 2023 Symposium on Simplicity in Algorithms (SOSA), SIAM, Philadelphia, PA, 2023, pp. 353– 364

    2023

  24. [32]

    C. J. Geoga, M. Anitescu, and M. L. Stein , Scalable Gaussian process computations using hierarchical matrices, J. Comput. Graph. Statist., 29 (2020), pp. 227–237

    2020

  25. [33]

    Gillman, P

    A. Gillman, P. M. Young, and P.-G. Martinsson, A direct solver with O(N ) complexity for integral equations on one-dimensional domains, Front. Math. China, 7 (2012), pp. 217–247

    2012

  26. [34]

    Gorman, G

    C. Gorman, G. Ch ´avez, P. Ghysels, T. Mary, F.-H. Rouet, and X. S. Li , Robust and accurate stopping criteria for adaptive randomized sampling in matrix-free hierarchically semiseparable construction, SIAM J. Sci. Comput., 41 (2019), pp. S61–S85

    2019

  27. [35]

    Greengard and V

    L. Greengard and V. Rokhlin , A fast algorithm for particle simulations , J. Comput. Phys., 73 (1987), pp. 325–348

    1987

  28. [36]

    Hackbusch, Hierarchical matrices: algorithms and analysis , vol

    W. Hackbusch, Hierarchical matrices: algorithms and analysis , vol. 49 of Springer Series in Computational Mathematics, Springer, Heidelberg, 2015

    2015

  29. [37]

    Halikias and A

    D. Halikias and A. Townsend , Structured matrix recovery from matrix-vector products, Nu- mer. Linear Algebra Appl., 31 (2024), pp. Paper No. e2531, 27

    2024

  30. [38]

    Halko, P

    N. Halko, P. G. Martinsson, and J. A. Tropp , Finding structure with randomness: prob- abilistic algorithms for constructing approximate matrix decompositions , SIAM Rev., 53 (2011), pp. 217–288

    2011

  31. [39]

    Kapralov, H

    M. Kapralov, H. Lawrence, M. Makarov, C. Musco, and K. Sheth , Toeplitz low-rank approximation with sublinear query complexity , in Proceedings of the 2023 Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2023, pp. 4127–4158

    2023

  32. [40]

    Kaye and D

    J. Kaye and D. Goleˇz, Low rank compression in the numerical solution of the nonequilibrium Dyson equation, SciPost Phys., 10 (2021), pp. Paper No. 091, 29

    2021

  33. [41]

    N. B. Kovachki, S. Lanthaler, and A. M. Stuart , Operator learning: Algorithms and 26 AMSEL, CHEN, DUMAN KELES, HALIKIAS, MUSCO, MUSCO, PERSSON analysis, arXiv preprint arXiv:2402.15715, (2024)

    2024 arXiv

  34. [42]

    Kressner, S

    D. Kressner, S. Massei, and L. Robol , Low-rank updates and a divide-and-conquer method for linear matrix equations , SIAM J. Sci. Comput., 41 (2019), pp. A848–A876

    2019

  35. [43]

    Levitt and P.-G

    J. Levitt and P.-G. Martinsson , Linear-complexity black-box randomized compression of rank-structured matrices, SIAM J. Sci. Comput., 46 (2024), pp. A1747–A1763

    2024

  36. [44]

    , Randomized compression of rank-structured matrices accelerated with graph coloring , J. Comput. Appl. Math., 451 (2024), pp. Paper No. 116044, 22

    2024

  37. [45]

    Li and H

    Y. Li and H. Yang , Interpolative butterfly factorization , SIAM J. Sci. Comput., 39 (2017), pp. A503–A531

    2017

  38. [46]

    Z. Li, N. B. Kovachki, K. Azizzadenesheli, B. liu, K. Bhattacharya, A. Stuart, and A. Anandkumar, Fourier neural operator for parametric partial differential equations , in International Conference on Learning Representations, 2021

    2021

  39. [47]

    L. Lin, J. Lu, and L. Ying , Fast construction of hierarchical matrix representation from matrix-vector multiplication, J. Comput. Phys., 230 (2011), pp. 4071–4087

    2011

  40. [48]

    Litvinenko, Y

    A. Litvinenko, Y. Sun, M. G. Genton, and D. E. Keyes , Likelihood approximation with hierarchical matrices for large spatial datasets , Comput. Statist. Data Anal., 137 (2019), pp. 115–132

    2019

  41. [49]

    Y. Liu, X. Xing, H. Guo, E. Michielssen, P. Ghysels, and X. S. Li , Butterfly factorization via randomized matrix-vector multiplications, SIAM J. Sci. Comput., 43 (2021), pp. A883– A907

    2021

  42. [50]

    L. Lu, P. Jin, G. Pang, Z. Zhang, and G. Karniadakis , Learning nonlinear operators via deeponet based on the universal approximation theorem of operators , Nat. Mach. Intell., 3 (2021), pp. 218–229

    2021

  43. [51]

    Martinsson, Rapid factorization of structured matrices via randomized sampling , arXiv preprint arXiv:0806.2339, (2008)

    P.-G. Martinsson, Rapid factorization of structured matrices via randomized sampling , arXiv preprint arXiv:0806.2339, (2008)

    2008 arXiv

  44. [52]

    P. G. Martinsson, A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix , SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1251–1274

    2011

  45. [53]

    Martinsson, Compressing rank-structured matrices via randomized sampling , SIAM J

    P.-G. Martinsson, Compressing rank-structured matrices via randomized sampling , SIAM J. Sci. Comput., 38 (2016), pp. A1959–A1986

    2016

  46. [54]

    96 of CBMS-NSF Regional Conference Se- ries in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2020

    , Fast direct solvers for elliptic PDEs , vol. 96 of CBMS-NSF Regional Conference Se- ries in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2020

    2020

  47. [55]

    P. G. Martinsson and V. Rokhlin , A fast direct solver for boundary integral equations in two dimensions , J. Comput. Phys., 205 (2005), pp. 1–23

    2005

  48. [56]

    Massei, M

    S. Massei, M. Mazza, and L. Robol , Fast solvers for two-dimensional fractional diffusion equations using rank structured matrices , SIAM J. Sci. Comput., 41 (2019), pp. A2627– A2656

    2019

  49. [57]

    Massei, L

    S. Massei, L. Robol, and D. Kressner , hm-toolbox: MATLAB software for HODLR and HSS matrices, SIAM J. Sci. Comput., 42 (2020), pp. C43–C68

    2020

  50. [58]

    Musco and C

    C. Musco and C. Musco , Projection-cost-preserving sketches: Proof strategies and construc- tions, arXiv preprint arXiv:2004.08434, (2020)

    2020 arXiv

  51. [59]

    Nakatsukasa, Fast and stable randomized low-rank matrix approximation , arXiv preprint arXiv:2009.11392, (2020)

    Y. Nakatsukasa, Fast and stable randomized low-rank matrix approximation , arXiv preprint arXiv:2009.11392, (2020)

    2020 arXiv

  52. [60]

    Park and Y

    T. Park and Y. Nakatsukasa , Approximating sparse matrices and their functions using matrix-vector products, arXiv preprint arXiv:2310.05625, (2023)

    2023

  53. [61]

    K. J. Pearce, A. Yesypenko, J. Levitt, and P.-G. Martinsson, Randomized rank-structured matrix compression by tagging , arXiv preprint arXiv:2501.05528, (2025)

    2025

  54. [62]

    Pouransari, P

    H. Pouransari, P. Coulier, and E. Darve, Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation , SIAM J. Sci. Comput., 39 (2017), pp. A797–A830

    2017

  55. [63]

    Sarlos, Improved approximation algorithms for large matrices via random projections , in 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp

    T. Sarlos, Improved approximation algorithms for large matrices via random projections , in 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 143–152

    2006

  56. [64]

    Sch¨afer, M

    F. Sch¨afer, M. Katzfuss, and H. Owhadi, Sparse Cholesky factorization by Kullback-Leibler minimization, SIAM J. Sci. Comput., 43 (2021), pp. A2019–A2046

    2021

  57. [65]

    Simchowitz, A

    M. Simchowitz, A. El Alaoui, and B. Recht, Tight query complexity lower bounds for PCA via finite sample deformed Wigner law , in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2018, pp. 1249–1259

    2018

  58. [66]

    D. C. Sorensen and M. Embree , A deim induced cur factorization , SIAM J. Sci. Comput., 38 (2016), pp. A1454–A1482

    2016

  59. [67]

    J. M. Tang and Y. Saad , A probing method for computing the diagonal of a matrix inverse , Numer. Linear Algebra Appl., 19 (2012), pp. 485–501. QUASI-OPTIMAL HSS MATRIX APPROXIMATION 27

    2012

  60. [68]

    J. A. Tropp and R. J. Webber , Randomized algorithms for low-rank matrix approximation: Design, analysis, and applications , arXiv preprint arXiv:2306.12418, (2023)

    2023 arXiv

  61. [69]

    J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher , Practical sketching algorithms for low-rank matrix approximation , SIAM J. Matrix Anal. Appl., 38 (2017), pp. 1454–1485

    2017

  62. [70]

    W ang and A

    C. W ang and A. Townsend, Operator learning for hyperbolic partial differential equations , arXiv preprint arXiv:2312.17489, (2023)

    2023

  63. [71]

    W aters, A

    A. W aters, A. Sankaranarayanan, and R. Baraniuk , SpaRCS: Recovering low-rank and sparse matrices from compressive measurements, in Advances in Neural Information Pro- cessing Systems, vol. 24, 2011

    2011

  64. [72]

    Wimalajeewa, Y

    T. Wimalajeewa, Y. C. Eldar, and P. K. V arshney, Recovery of sparse matrices via matrix sketching, arXiv preprint arXiv:1311.2448, (2013)

    2013 arXiv

  65. [73]

    Y. Xi, J. Xia, S. Cauley, and V. Balakrishnan , Superfast and stable structured solvers for Toeplitz least squares via randomized sampling , SIAM J. Matrix Anal. Appl., 35 (2014), pp. 44–72

    2014

  66. [74]

    J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li , Superfast multifrontal method for large structured linear systems of equations , SIAM J. Matrix Anal. Appl., 31 (2009), pp. 1382– 1411

    2009

  67. [75]

    Linear Algebra Appl., 17 (2010), pp

    , Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl., 17 (2010), pp. 953–976

    2010

  68. [76]

    eR1 eR2 # , . . . ,

    Y. Yaniv, P. Ghysels, O. A. Malik, H. A. Boateng, and X. S. Li , Construction of hi- erarchically semiseparable matrix representation using adaptive Johnson–Lindenstrauss sketching, Commun. Appl. Math. Comput. Sci., 20 (2025), pp. 67–117. Disclaimer. This paper was prepared fo...

    2025

Pith tools

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