{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:13:54Z","timestamp":1778228034796,"version":"3.51.4"},"reference-count":76,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CFF-2046235"],"award-info":[{"award-number":["CFF-2046235"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-2427363"],"award-info":[{"award-number":["CCF-2427363"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000082","name":"Division of Graduate Education","doi-asserted-by":"publisher","award":["DGE-2139899"],"award-info":[{"award-number":["DGE-2139899"]}],"id":[{"id":"10.13039\/100000082","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2026,6,30]]},"DOI":"10.1137\/25m176622x","type":"journal-article","created":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:00:27Z","timestamp":1778227227000},"page":"586-621","source":"Crossref","is-referenced-by-count":0,"title":["Quasi-optimal Hierarchically Semi-separable Matrix Approximation"],"prefix":"10.1137","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9241-8284","authenticated-orcid":true,"given":"Noah","family":"Amsel","sequence":"first","affiliation":[{"name":"New York University, New York, NY 10012 USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tyler","family":"Chen","sequence":"additional","affiliation":[{"name":"JP Morgan Chase, New York, NY 10017 USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feyza","family":"Duman Keles","sequence":"additional","affiliation":[{"name":"New York University, New York, NY 10012 USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diana","family":"Halikias","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY 14850 USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cameron","family":"Musco","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA 01003 USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3118-4848","authenticated-orcid":true,"given":"Christopher","family":"Musco","sequence":"additional","affiliation":[{"name":"New York University, New York, NY 10012 USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-9980-5854","authenticated-orcid":true,"given":"David","family":"Persson","sequence":"additional","affiliation":[{"name":"New York University, New York, NY 10012 USA."},{"name":"Flatiron Institute."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"351","published-online":{"date-parts":[[2026,5,8]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1270367"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2015.2448083"},{"key":"ref3","unstructured":"N. Amsel, T. Chen, F. D. Keles, D. Halikias, C. Musco, and C. Musco, Fixed-sparsity Matrix Approximation From Matrix-vector Products, preprint, https:\/\/arxiv.org\/abs\/2402.09379, 2024."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/20M1386451"},{"key":"ref5","unstructured":"T. Askham, M. Rachh, M. O\u2019Neil, J. Hoskins, D. Fortunato, S. Jiang, F. Fryklund, T. Goodwill, H. Yang Wang, and H. Zhu, chunkIE: a MATLAB integral equation toolbox, 2024, https:\/\/chunkie.readthedocs.io\/."},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"A. Bakshi, K. L. Clarkson, and D. P. Woodruff, Low-rank approximation with \\(1\/\\epsilon^{1\/3}\\) matrix-vector products, in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2022, pp. 1130\u20131143.","DOI":"10.1145\/3519935.3519988"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"A. Bakshi and S. Narayanan, Krylov methods are (nearly) optimal for low-rank approximation, in Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2023, pp. 2093\u20132101, https:\/\/doi.org\/10.1109\/FOCS57990.2023.00128.","DOI":"10.1109\/FOCS57990.2023.00128"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49887-4_3"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1038\/324446a0"},{"key":"ref10","unstructured":"R. A. Baston and Y. Nakatsukasa, Stochastic Diagonal Estimation: Probabilistic Bounds and an Improved Algorithm, preprint, https:\/\/arxiv.org\/abs\/2201.10684,\u00a02022."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-002-0445-6"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.apnum.2007.01.003"},{"key":"ref13","series-title":"Athena Scientific Optimization and Computation Series","volume-title":"Nonlinear Programming","author":"Bertsekas D. P.","year":"1999","edition":"2"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0653-8"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.4171\/091"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00791-015-0233-3"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1145\/3232850"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-022-08745-5"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2303904120"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-022-09556-w"},{"key":"ref21","series-title":"Handbook of Numerical Analysis 25","first-page":"83","volume-title":"Numerical Analysis Meets Machine Learning","author":"Boull\u00e9 N.","year":"2024"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/22M1500848"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/24M1642354"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36265-7_51"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"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, 2025, pp. 2656\u20132692, https:\/\/doi.org\/10.1137\/1.9781611978322.87.","DOI":"10.1137\/1.9781611978322.87"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"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\u2013172.","DOI":"10.1145\/2746539.2746569"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1137\/0607026"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/0720013"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/13.1.117"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2391251"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"P. Dharangutte and C. Musco, A tight analysis of Hutchinson\u2019s diagonal estimator, in 2023 Symposium on Simplicity in Algorithms (SOSA), SIAM, Philadelphia, 2023, pp. 353\u2013364, https:\/\/doi.org\/10.1137\/1.9781611977585.ch32.","DOI":"10.1137\/1.9781611977585.ch32"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2019.1652616"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/s11464-012-0188-3"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1137\/18M1194961"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(87)90140-9"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47324-5"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1002\/nla.2531"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"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, Philadelphia, 2023, pp. 4127\u20134158.","DOI":"10.1137\/1.9781611977554.ch159"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.21468\/SciPostPhys.10.4.091"},{"key":"ref41","unstructured":"N. B. Kovachki, S. Lanthaler, and A. M. Stuart, Operator Learning: Algorithms and Analysis, preprint, https:\/\/arxiv.org\/abs\/2402.15715,\u00a02024."},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1137\/17M1161038"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1137\/22M1528574"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2024.116044"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1137\/16M1074941"},{"key":"ref46","unstructured":"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, https:\/\/openreview.net\/forum?id=c8P9NQVtmnO."},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2011.02.033"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2019.02.002"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1137\/20M1315853"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1038\/s42256-021-00302-5"},{"key":"ref51","unstructured":"P.G. Martinsson, Rapid Factorization of Structured Matrices Via Randomized Sampling, preprint, https:\/\/arxiv.org\/abs\/0806.2339, 2008."},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1137\/100786617"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1137\/15M1016679"},{"key":"ref54","doi-asserted-by":"crossref","unstructured":"P.G. Martinsson, Fast Direct Solvers for Elliptic PDEs, CBMS-NSF Regional Conf. Ser. in Appl. Math. 96, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 2020, https:\/\/doi.org\/10.1137\/1.9781611976045.","DOI":"10.1137\/1.9781611976045"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2004.10.033"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1137\/18M1180803"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1137\/19M1288048"},{"key":"ref58","unstructured":"C. Musco and C. Musco, Projection-cost-preserving Sketches: Proof Strategies and Constructions, preprint, https:\/\/arxiv.org\/abs\/2004.08434, 2020."},{"key":"ref59","unstructured":"Y. Nakatsukasa, Fast and Stable Randomized Low-Rank Matrix Approximation, preprint, https:\/\/arxiv.org\/abs\/2009.11392, 2020."},{"key":"ref60","unstructured":"T. Park and Y. Nakatsukasa, Approximating Sparse Matrices and Their Functions Using Matrix-Vector Products, preprint, https:\/\/arxiv.org\/abs\/2310.05625, 2023."},{"key":"ref61","unstructured":"K. J. Pearce, A. Yesypenko, J. Levitt, and P.G. Martinsson, Randomized Block Low-Rank Matrix Compression by Tagging, preprint, https:\/\/arxiv.org\/abs\/2501.05528, 2025."},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1137\/15M1046939"},{"key":"ref63","doi-asserted-by":"crossref","unstructured":"T. Sarlos, Improved approximation algorithms for large matrices via random projections, in Proceedings of the 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 143\u2013152, https:\/\/doi.org\/10.1109\/FOCS.2006.37.","DOI":"10.1109\/FOCS.2006.37"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1137\/20M1336254"},{"key":"ref65","doi-asserted-by":"crossref","unstructured":"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\u20131259, https:\/\/doi.org\/10.1145\/3188745.3188796.","DOI":"10.1145\/3188745.3188796"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1137\/140978430"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1002\/nla.779"},{"key":"ref68","unstructured":"J. A. Tropp and R. J. Webber, Randomized Algorithms for Low-Rank Matrix Approximation: Design, Analysis, and Applications, preprint, https:\/\/arxiv.org\/abs\/2306.12418,\u00a02023."},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1137\/17M1111590"},{"key":"ref70","unstructured":"C. Wang and A. Townsend, Operator Learning for Hyperbolic Partial Differential Equations, preprint, https:\/\/arxiv.org\/abs\/2312.17489, 2023."},{"key":"ref71","volume-title":"Advances in Neural Information Processing Systems","volume":"24","author":"Waters A.","year":"2011"},{"key":"ref72","unstructured":"T. Wimalajeewa, Y. C. Eldar, and P. K. Varshney, Recovery of Sparse Matrices via Matrix Sketching, preprint, https:\/\/arxiv.org\/abs\/1311.2448, 2013."},{"key":"ref73","doi-asserted-by":"publisher","DOI":"10.1137\/120895755"},{"key":"ref74","doi-asserted-by":"publisher","DOI":"10.1137\/09074543X"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1002\/nla.691"},{"key":"ref76","doi-asserted-by":"publisher","DOI":"10.2140\/camcos.2025.20.67"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:00:54Z","timestamp":1778227254000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M176622X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,8]]},"references-count":76,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1137\/25M176622X"],"URL":"https:\/\/doi.org\/10.1137\/25m176622x","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,8]]}}}