{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T08:17:23Z","timestamp":1775463443609,"version":"3.50.1"},"reference-count":70,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-23-1-2729"],"award-info":[{"award-number":["N00014-23-1-2729"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2045590"],"award-info":[{"award-number":["2045590"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2427362"],"award-info":[{"award-number":["2427362"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2046235"],"award-info":[{"award-number":["2046235"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2427362"],"award-info":[{"award-number":["2427362"]}],"id":[{"id":"10.13039\/100000001","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\/25m1742710","type":"journal-article","created":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T07:35:45Z","timestamp":1775460945000},"page":"483-511","source":"Crossref","is-referenced-by-count":0,"title":["Fixed-Sparsity Matrix Approximation from Matrix-Vector Products"],"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":"Courant Institute of Mathematical Sciences, New York University, New York, NY 10012 USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tyler","family":"Chen","sequence":"additional","affiliation":[{"name":"Tandon School of Engineering, New York University, New York, NY 10012 USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feyza Duman","family":"Keles","sequence":"additional","affiliation":[{"name":"Tandon School of Engineering, New York University, New York, NY 10012 USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diana","family":"Halikias","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Cornell University, Ithaca, NY 14850 USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cameron","family":"Musco","sequence":"additional","affiliation":[{"name":"Manning College of Information and Computer Sciences, 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":"Tandon School of Engineering, New York University, New York, NY 10012 USA."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"351","published-online":{"date-parts":[[2026,4,6]]},"reference":[{"key":"ref1","unstructured":"N. Amsel, P. Avi, T. Chen, F. D. Keles, C. Hegde, C. Musco, C. Musco, and D. Persson, Query Efficient Structured Matrix Learning, https:\/\/arxiv.org\/abs\/2507.19290, 2025."},{"key":"ref2","unstructured":"N. Amsel, T. Chen, F. D. Keles, D. Halikias, C. Musco, C. Musco, and D. Persson, Quasi-optimal Hierarchically Semi-separable Matrix Approximation, https:\/\/arxiv.org\/abs\/2505.16937, 2025; SIAM J. Matrix Anal. Appl., to appear."},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"ref4","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, Association for Computing Machinery, 2022, pp. 1130\u20131143, https:\/\/doi.org\/10.1145\/3519935.3519988.","DOI":"10.1145\/3519935.3519988"},{"key":"ref5","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 Symposium on Foundations of Computer Science (FOCS), IEEE, 2023, pp. 2093\u20132101, https:\/\/doi.org\/10.1109\/focs57990.2023.00128.","DOI":"10.1109\/FOCS57990.2023.00128"},{"key":"ref6","unstructured":"R. A. Baston and Y. Nakatsukasa, Stochastic Diagonal Estimation: Probabilistic Bounds and an Improved Algorithm, preprint, https:\/\/arxiv.org\/abs\/2201.10684, 2022."},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.apnum.2007.01.003"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/100814019"},{"key":"ref9","first-page":"16","volume":"28","author":"Benzi M.","year":"2008","journal-title":"Electron. Trans. Numer. Anal."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/151006159"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(98)00118-4"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-022-08745-5"},{"key":"ref13","first-page":"1","volume":"25","author":"Boull\u00e9 N.","year":"2024","journal-title":"J. Mach. Learn. Res."},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2303904120"},{"key":"ref15","unstructured":"M. Braverman, E. Hazan, M. Simchowitz, and B. Woodworth, The gradient complexity of linear regression, in Proceedings of the 33rd Conference on Learning Theory, Proc. Mach. Learn. Res. 125, 2020, pp. 627\u2013647, http:\/\/proceedings.mlr.press\/v125\/braverman20a.html."},{"key":"ref16","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 Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2025, pp. 2656\u20132692.","DOI":"10.1137\/1.9781611978322.87"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"S. Chewi, J. De Dios Pont, J. Li, C. Lu, and S. Narayanan, Query lower bounds for log-concave sampling, in Proceedings of the\u00a064th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2023, pp. 2139\u20132148, https:\/\/doi.org\/10.1109\/focs57990.2023.00131.","DOI":"10.1109\/FOCS57990.2023.00131"},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson and D. P. Woodruff, Numerical linear algebra in the streaming model, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 205\u2013214.","DOI":"10.1145\/1536414.1536445"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/0607026"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/0720013"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/13.1.117"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2391251"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/0714041"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1984-0758197-9"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"P. Dharangutte and C. Musco, A tight analysis of Hutchinson\u2019s diagonal estimator, in Proceedings of the Symposium on Simplicity in Algorithms (SOSA), SIAM, 2023, pp. 353\u2013364, https:\/\/doi.org\/10.1137\/1.9781611977585.ch32.","DOI":"10.1137\/1.9781611977585.ch32"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"K. Do Ba, P. Indyk, E. Price, and D. P. Woodruff, Lower bounds for sparse recovery, in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2010, pp. 1190\u20131197.","DOI":"10.1137\/1.9781611973075.95"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511794308"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/23M1558537"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4948-7"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1137\/20M1364461"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/0913071"},{"key":"ref32","unstructured":"D. Girard, Un Algorithme Simple et Rapide pour la Validation Croisee G\u00e9en\u00e9ralis\u00e9e sur des Probl\u00e9mes de Grande Taille, Technical report, \u00c9cole Nationale Sup\u00e9rieure d\u2019Informatique et de Math\u00e9matiques Appliqu\u00e9es de Grenoble, 1987."},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"A. Greenbaum, Iterative Methods for Solving Linear Systems, SIAM, Philadelphia, 1997.","DOI":"10.1137\/1.9781611970937"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1002\/nla.2531"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1137\/22M1476277"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1088\/1361-6420\/acd719"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717778"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1080\/03610918908812806"},{"key":"ref41","first-page":"23741","volume-title":"Proceedings of Advances in Neural Information Processing Systems","author":"Jiang S.","year":"2021"},{"key":"ref42","volume-title":"Computed Tomography: Fundamentals, System Technology, Image Quality, Applications","author":"Kalender W. A.","year":"2011","edition":"3"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1038\/s42254-021-00314-5"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1137\/22M1528574"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2024.116044"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2011.02.033"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1137\/15M1016679"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492920000021"},{"key":"ref49","doi-asserted-by":"crossref","unstructured":"R. A. Meyer, C. Musco, C. Musco, and D. P. Woodruff, Hutch++: Optimal stochastic trace estimation, in Proceedings of the Symposium on Simplicity in Algorithms (SOSA), SIAM, Philadephia, 2021, pp. 142\u2013155, https:\/\/doi.org\/10.1137\/1.9781611976496.16.","DOI":"10.1137\/1.9781611976496.16"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316559"},{"key":"ref51","unstructured":"R. Murray, J. Demmel, M. W. Mahoney, N. B. Erichson, M. Melnichenko, O. A. Malik, L. Grigori, P. Luszczek, M. Derezinski, M. E. Lopes, T. Liang, H. Luo, and J. Dongarra, Randomized Numerical Linear Algebra: A Perspective on the Field with an Eye to Software, preprint, 2302.11474, 2023, https:\/\/doi.org\/10.48550\/arXiv.2302.11474."},{"key":"ref52","doi-asserted-by":"crossref","unstructured":"D. Needell, W. Swartworth, and D. P. Woodruff, Testing positive semidefiniteness using linear measurements, in Proceedings of the 63rd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2022, pp. 87\u201397, https:\/\/doi.org\/10.1109\/focs54457.2022.00016.","DOI":"10.1109\/FOCS54457.2022.00016"},{"key":"ref53","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":"ref54","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1994.6.1.147"},{"key":"ref55","doi-asserted-by":"crossref","unstructured":"E. Price and D. P. Woodruff, (1 + eps)-approximate sparse recovery, in Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, IEEE, 2011, pp. 295\u2013304, https:\/\/doi.org\/10.1109\/focs.2011.92.","DOI":"10.1109\/FOCS.2011.92"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1137\/20M1336254"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1137\/22M154226X"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316481"},{"key":"ref59","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 \u201918, ACM, 2018, pp. 1249\u20131259, https:\/\/doi.org\/10.1145\/3188745.3188796.","DOI":"10.1145\/3188745.3188796"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-7860-8_48"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1137\/120881452"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1145\/3470566"},{"key":"ref63","doi-asserted-by":"crossref","unstructured":"W. Swartworth and D. P. Woodruff, Optimal eigenvalue approximation via sketching, in Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC \u201923, ACM, 2023, pp. 145\u2013155, https:\/\/doi.org\/10.1145\/3564246.3585102.","DOI":"10.1145\/3564246.3585102"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1002\/nla.779"},{"key":"ref65","volume":"35","author":"Trefethen N.","year":"2002","journal-title":"SIAM News"},{"key":"ref66","unstructured":"J. A. Tropp and R. J. Webber, Randomized Algorithms for Low-Rank Matrix Approximation: Design, Analysis, and Applications, preprint, arXiv:2306.12418, 2023."},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"ref68","unstructured":"A. Waters, A. Sankaranarayanan, and R. Baraniuk, SpaRCS: Recovering low-rank and sparse matrices from compressive measurements, in Proceedings of Advances in Neural Information Processing Systems, Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Weinberger, eds. 2011; available online from https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2011\/file\/0ff8033cf9437c213ee13937b1c4c455-Paper.pdf."},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.78.275"},{"key":"ref70","unstructured":"T. Wimalajeewa, Y. C. Eldar, and P. K. Varshney, Recovery of Sparse Matrices via Matrix Sketching, preprint, 1311.2448, 2013, https:\/\/doi.org\/10.48550\/arXiv.1311.2448."}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T07:35:52Z","timestamp":1775460952000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M1742710"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,6]]},"references-count":70,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1137\/25M1742710"],"URL":"https:\/\/doi.org\/10.1137\/25m1742710","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,6]]}}}