{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:34:57Z","timestamp":1787333697581,"version":"build-2736575974"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006754","name":"U.S. Army Research Laboratory","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006754","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\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>Kernel methods are widespread in machine learning; however, they are limited by the quadratic complexity of the construction, application, and storage of kernel matrices. Low-rank matrix approximation algorithms are widely used to address this problem and reduce the arithmetic and storage cost. However, we observed that for some datasets with wide intraclass variability, the optimal kernel parameter for smaller classes yields a matrix that is less well-approximated by low-rank methods. In this paper, we propose an efficient structured low-rank approximation method---the block basis factorization (BBF)---and its fast construction algorithm to approximate radial basis function kernel matrices. Our approach has linear memory cost and floating point operations for many machine learning kernels. BBF works for a wide range of kernel bandwidth parameters and extends the domain of applicability of low-rank approximation methods significantly. Our empirical results demonstrate the stability and superiority over the state-of-the-art kernel approximation algorithms.<\/jats:p>","DOI":"10.1137\/18m1212586","type":"journal-article","created":{"date-parts":[[2019,12,6]],"date-time":"2019-12-06T19:18:08Z","timestamp":1575659888000},"page":"1497-1526","source":"Crossref","is-referenced-by-count":7,"title":["Block Basis Factorization for Scalable Kernel Evaluation"],"prefix":"10.1137","volume":"40","author":[{"given":"Ruoxi","family":"Wang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1852-3750","authenticated-orcid":true,"given":"Yingzhou","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael W.","family":"Mahoney","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eric","family":"Darve","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,12,3]]},"reference":[{"key":"atypb1","first-page":"775","author":"Alaoui A. E.","year":"2015","journal-title":"MA"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/120903476"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/120903476"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2015.10.012"},{"key":"atypb5","unstructured":"F. Bach,\n                      Sharp analysis of low-rank kernel matrix approximations\n                      , in Proceedings of the 26th Annual Conference on Learning Theory, 2013, pp. 185-209."},{"key":"atypb6","unstructured":"K. Bache and M. Lichman,\n                      UCI Machine Learning Repository\n                      ,http:\/\/archive.ics.uci.edu\/ml(2013)."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/14096815X"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479803436652"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199"},{"key":"atypb10","first-page":"2214","volume":"18","author":"Chen J.","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/030602678"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142999330379"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.2000.6451"},{"key":"atypb14","first-page":"3475","volume":"13","author":"Drineas P.","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"atypb15","first-page":"2153","volume":"6","author":"Drineas P.","year":"2005","journal-title":"J. Mach. Learn. Res."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.4310\/CMS.2009.v7.n2.a3"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2009.08.031"},{"key":"atypb18","first-page":"3977","volume":"17","author":"Gittens A.","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"atypb19","unstructured":"G. H. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , Vol. 3, John Hopkins University Press, Baltimore, MD, 2012."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(87)90140-9"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492900002725"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/0912004"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/0917055"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s006070050015"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-002-1450-4"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/PL00021408"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"M. R. Hestenes and E. Stiefel,\n                      Methods of Conjugate Gradients for Solving Linear Systems\n                      , Vol. 49, NBS, Washington, DC, 1952.","DOI":"10.6028\/jres.049.044"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/15M1007173"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2017.04.002"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0709640104"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1561\/2200000035"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/0712047"},{"key":"atypb34","first-page":"143","author":"Sarlos T.","year":"2006","journal-title":"New York"},{"key":"atypb35","first-page":"164","author":"Savas B.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb36","first-page":"682","volume":"18","author":"Si S.","year":"2017","journal-title":"J. Mach. Learn."},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/j.spasta.2013.06.003"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/j.spasta.2013.06.003"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/17M1135803"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1002\/nla.691"},{"key":"atypb41","first-page":"664","author":"Yang C.","year":"2003","journal-title":"New York"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2003.11.021"},{"key":"atypb43","unstructured":"J. Zhang, A. May, T. Dao, and C. R\u00e9,\n                      Low-Precision Random Fourier Features for Memory-Constrained Kernel Approximation\n                      ,http:\/\/arxiv.org\/abs\/1811.00155, 2019."},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2010.2064786"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1212586","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:18:29Z","timestamp":1787332709000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1212586"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M1212586"],"URL":"https:\/\/doi.org\/10.1137\/18m1212586","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}