{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T23:45:57Z","timestamp":1776815157406,"version":"3.51.2"},"reference-count":67,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,8,1]],"date-time":"2020-08-01T00:00:00Z","timestamp":1596240000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,8,1]],"date-time":"2020-08-01T00:00:00Z","timestamp":1596240000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100008628","name":"Ministry of Electronics and Information technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100008628","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Artif Intell Rev"],"published-print":{"date-parts":[[2021,2]]},"DOI":"10.1007\/s10462-020-09880-z","type":"journal-article","created":{"date-parts":[[2020,8,1]],"date-time":"2020-08-01T09:13:51Z","timestamp":1596273231000},"page":"843-876","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Major advancements in kernel function approximation"],"prefix":"10.1007","volume":"54","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3848-1028","authenticated-orcid":false,"given":"Deena P.","family":"Francis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kumudha","family":"Raimond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,8,1]]},"reference":[{"key":"9880_CR1","doi-asserted-by":"crossref","unstructured":"Ailon N, Chazelle B (2006) Approximate nearest neighbors and the fast Johnson\u2013Lindenstrauss transform. In: Proceedings of the thirty-eighth annual ACM symposium on theory of computing, pp 557\u2013563","DOI":"10.1145\/1132516.1132597"},{"issue":"3","key":"9880_CR2","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1090\/S0002-9947-1950-0051437-7","volume":"68","author":"N Aronszajn","year":"1950","unstructured":"Aronszajn N (1950) Theory of reproducing kernels. Trans Am Math Soc 68(3):337\u2013404","journal-title":"Trans Am Math Soc"},{"issue":"1","key":"9880_CR3","first-page":"4096","volume":"17","author":"H Avron","year":"2016","unstructured":"Avron H, Sindhwani V, Yang J, Mahoney MW (2016) Quasi-Monte Carlo feature maps for shift-invariant kernels. J Mach Learn Res 17(1):4096\u20134133","journal-title":"J Mach Learn Res"},{"key":"9880_CR4","unstructured":"Avron H, Kapralov M, Musco C, Musco C, Velingker A, Zandieh A (2017) Random Fourier features for kernel ridge regression: approximation bounds and statistical guarantees. In: Proceedings of the 34th international conference on machine learning, PMLR, Proceedings of machine learning research, vol\u00a070, pp 253\u2013262, http:\/\/proceedings.mlr.press\/v70\/avron17a.html"},{"key":"9880_CR5","unstructured":"Bach F (2013) Sharp analysis of low-rank kernel matrix approximations. In: Conference on learning theory, pp 185\u2013209"},{"issue":"21","key":"9880_CR6","first-page":"1","volume":"18","author":"F Bach","year":"2017","unstructured":"Bach F (2017) On the equivalence between kernel quadrature rules and random feature expansions. J Mach Learn Res 18(21):1\u201338","journal-title":"J Mach Learn Res"},{"issue":"7","key":"9880_CR7","doi-asserted-by":"publisher","first-page":"1920","DOI":"10.1109\/TSP.2017.2781640","volume":"66","author":"P Bouboulis","year":"2017","unstructured":"Bouboulis P, Chouvardas S, Theodoridis S (2017) Online distributed learning over networks in RKH spaces using random Fourier features. IEEE Trans Signal Process 66(7):1920\u20131932","journal-title":"IEEE Trans Signal Process"},{"key":"9880_CR8","unstructured":"Carratino L, Rudi A, Rosasco L (2018) Learning with SGD and random features. In: Advances in neural information processing systems, pp 10192\u201310203"},{"issue":"9","key":"9880_CR9","doi-asserted-by":"publisher","first-page":"2050","DOI":"10.1109\/TIT.2004.833339","volume":"50","author":"N Cesa-Bianchi","year":"2004","unstructured":"Cesa-Bianchi N, Conconi A, Gentile C (2004) On the generalization ability of on-line learning algorithms. IEEE Trans Inf Theory 50(9):2050\u20132057","journal-title":"IEEE Trans Inf Theory"},{"issue":"5","key":"9880_CR10","first-page":"1393","volume":"19","author":"PC Chang","year":"2015","unstructured":"Chang PC, Wu JL (2015) A critical feature extraction by kernel PCA in stock trading model. Soft Comput Fusion Found Methodol Appl 19(5):1393\u20131408","journal-title":"Soft Comput Fusion Found Methodol Appl"},{"key":"9880_CR11","doi-asserted-by":"crossref","unstructured":"Charikar M, Chen K, Farach-Colton M (2002) Finding frequent items in data streams. In: International colloquium on automata, languages, and programming. Springer, pp 693\u2013703","DOI":"10.1007\/3-540-45465-9_59"},{"issue":"Mar","key":"9880_CR12","first-page":"1069","volume":"12","author":"K Chaudhuri","year":"2011","unstructured":"Chaudhuri K, Monteleoni C, Sarwate AD (2011) Differentially private empirical risk minimization. J Mach Learn Res 12(Mar):1069\u20131109","journal-title":"J Mach Learn Res"},{"key":"9880_CR13","doi-asserted-by":"crossref","unstructured":"Chitta R, Jin R, Jain AK (2012) Efficient kernel clustering using random Fourier features. In: 2012 IEEE 12th international conference on data mining (ICDM). IEEE, pp 161\u2013170","DOI":"10.1109\/ICDM.2012.61"},{"key":"9880_CR14","unstructured":"Choromanski K, Sindhwani V (2016) Recycling randomness with structure for sublinear time kernel expansions. In: Proceedings of the 33rd international conference on international conference on machine learning, vol 48, JMLR.org, pp 2502\u20132510"},{"key":"9880_CR15","unstructured":"Choromanski KM, Rowland M, Weller A (2017) The unreasonable effectiveness of structured random orthogonal embeddings. In: Advances in neural information processing systems, pp 219\u2013228"},{"key":"9880_CR16","unstructured":"Cohen MB, Musco C, Musco C (2015) Ridge leverage scores for low-rank approximation. arXiv preprint arXiv:1511.07263 6"},{"key":"9880_CR17","unstructured":"Cutajar K, Bonilla EV, Michiardi P, Filippone M (2016) Practical learning of deep Gaussian processes via random Fourier features. arXiv preprint arXiv:1610.04386"},{"key":"9880_CR18","unstructured":"Damianou A, Lawrence N (2013) Deep Gaussian processes. In: Artificial intelligence and statistics, pp 207\u2013215"},{"key":"9880_CR19","unstructured":"Damodaran BB, Courty N, Gosselin PH (2017) Data dependent kernel approximation using pseudo random Fourier features. arXiv preprint arXiv:1711.09783"},{"key":"9880_CR20","unstructured":"Dao T, De\u00a0Sa CM, R\u00e9 C (2017) Gaussian quadrature for kernel features. In: Advances in neural information processing systems, pp 6109\u20136119"},{"issue":"Dec","key":"9880_CR21","first-page":"2153","volume":"6","author":"P Drineas","year":"2005","unstructured":"Drineas P, Mahoney MW (2005) On the Nystr\u00f6m method for approximating a gram matrix for improved kernel-based learning. J Mach Learn Res 6(Dec):2153\u20132175","journal-title":"J Mach Learn Res"},{"key":"9880_CR22","unstructured":"Felix XY, Suresh AT, Choromanski KM, Holtmann-Rice DN, Kumar S (2016) Orthogonal random features. In: Advances in neural information processing systems, pp 1975\u20131983"},{"key":"9880_CR23","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-981-10-0251-9_25","volume-title":"Computational intelligence, cyber security and computational models","author":"DP Francis","year":"2016","unstructured":"Francis DP, Raimond K (2016) Comparison of machine learning techniques for the identification of the stages of Parkinson\u2019s disease. In: Senthilkumar M, Ramasamy V, Sheen S, Veeramani C, Bonato A, Batten L (eds) Computational intelligence, cyber security and computational models. Springer, Singapore, pp 247\u2013259. https:\/\/doi.org\/10.1007\/978-981-10-0251-9_25"},{"key":"9880_CR24","unstructured":"Francis DP, Raimond K (2017) Empirical evaluation of kernel PCA approximation methods in classification tasks. arXiv preprint arXiv:1712.04196"},{"issue":"2","key":"9880_CR25","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s10618-017-0542-x","volume":"32","author":"DP Francis","year":"2018","unstructured":"Francis DP, Raimond K (2018a) An improvement of the parameterized frequent directions algorithm. Data Min Knowl Discov 32(2):453\u2013482","journal-title":"Data Min Knowl Discov"},{"key":"9880_CR26","doi-asserted-by":"crossref","unstructured":"Francis DP, Raimond K (2018b) A random Fourier features based streaming algorithm for anomaly detection in large datasets. In: Advances in big data and cloud computing. Springer, pp 209\u2013217","DOI":"10.1007\/978-981-10-7200-0_18"},{"issue":"3","key":"9880_CR27","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/s10489-019-01538-w","volume":"50","author":"DP Francis","year":"2020","unstructured":"Francis DP, Raimond K (2020) A fast and accurate explicit kernel map. Appl Intell 50(3):647\u2013662","journal-title":"Appl Intell"},{"key":"9880_CR28","doi-asserted-by":"crossref","unstructured":"Ghashami M, Desai A, Phillips JM (2014) Improved practical matrix sketching with guarantees. In: European symposium on algorithms. Springer, pp 467\u2013479","DOI":"10.1007\/978-3-662-44777-2_39"},{"key":"9880_CR29","unstructured":"Ghashami M, Perry DJ, Phillips J (2016) Streaming kernel principal component analysis. In: Proceedings of the 19th international conference on artificial intelligence and statistics, pp 1365\u20131374"},{"issue":"2","key":"9880_CR30","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1137\/090771806","volume":"53","author":"N Halko","year":"2011","unstructured":"Halko N, Martinsson PG, Tropp JA (2011) Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev 53(2):217\u2013288","journal-title":"SIAM Rev"},{"key":"9880_CR31","unstructured":"Hamid R, Xiao Y, Gittens A, DeCoste D (2014) Compact random feature maps. In: International conference on machine learning, pp 19\u201327"},{"issue":"7","key":"9880_CR32","doi-asserted-by":"publisher","first-page":"272","DOI":"10.3390\/sym10070272","volume":"10","author":"L He","year":"2018","unstructured":"He L, Li Y, Zhang X, Chen C, Zhu L, Leng C (2018) Incremental spectral clustering via fastfood features and its application to stream image segmentation. Symmetry 10(7):272","journal-title":"Symmetry"},{"issue":"10","key":"9880_CR33","doi-asserted-by":"publisher","first-page":"2464","DOI":"10.1109\/TNNLS.2014.2387313","volume":"26","author":"Z Hu","year":"2015","unstructured":"Hu Z, Lin M, Zhang C (2015) Dependent online kernel learning with constant number of random Fourier features. IEEE Trans Neural Netw Learn Syst 26(10):2464\u20132476","journal-title":"IEEE Trans Neural Netw Learn Syst"},{"key":"9880_CR34","doi-asserted-by":"crossref","unstructured":"Huang PS, Deng L, Hasegawa-Johnson M, He X (2013) Random features for kernel deep convex network. In: 2013 IEEE international conference on acoustics, speech and signal processing (ICASSP). IEEE, pp 3143\u20133147","DOI":"10.1109\/ICASSP.2013.6638237"},{"key":"9880_CR35","doi-asserted-by":"crossref","unstructured":"Huang PS, Avron H, Sainath TN, Sindhwani V, Ramabhadran B (2014) Kernel methods match deep neural networks on timit. In: ICASSP, pp 205\u2013209","DOI":"10.1109\/ICASSP.2014.6853587"},{"key":"9880_CR36","first-page":"583","volume":"22","author":"P Kar","year":"2012","unstructured":"Kar P, Karnick H (2012) Random feature maps for dot product kernels. AISTATS 22:583\u2013591","journal-title":"AISTATS"},{"issue":"6","key":"9880_CR37","doi-asserted-by":"publisher","first-page":"1092","DOI":"10.1109\/TPAMI.2011.219","volume":"34","author":"B Kulis","year":"2012","unstructured":"Kulis B, Grauman K (2012) Kernelized locality-sensitive hashing. IEEE Trans Pattern Anal Mach Intell 34(6):1092\u20131104","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"9880_CR38","unstructured":"Le Q, Sarl\u00f3s T, Smola A (2013) Fastfood-approximating kernel expansions in loglinear time. In: Proceedings of the international conference on machine learning"},{"issue":"1","key":"9880_CR39","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.ces.2003.09.012","volume":"59","author":"JM Lee","year":"2004","unstructured":"Lee JM, Yoo C, Choi SW, Vanrolleghem PA, Lee IB (2004) Nonlinear process monitoring using kernel principal component analysis. Chem Eng Sci 59(1):223\u2013234","journal-title":"Chem Eng Sci"},{"key":"9880_CR40","doi-asserted-by":"crossref","unstructured":"Liberty E (2013) Simple and deterministic matrix sketching. In: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 581\u2013588","DOI":"10.1145\/2487575.2487623"},{"issue":"3","key":"9880_CR41","first-page":"13","volume":"8","author":"M Lin","year":"2014","unstructured":"Lin M, Weng S, Zhang C (2014) On the sample complexity of random Fourier features for online learning: How many random Fourier features do we need? ACM Trans Knowl Discov Data (TKDD) 8(3):13","journal-title":"ACM Trans Knowl Discov Data (TKDD)"},{"key":"9880_CR42","unstructured":"Lopez-Paz D, Sra S, Smola AJ, Ghahramani Z, Sch\u00f6lkopf B (2014) Randomized nonlinear component analysis. In: ICML, pp 1359\u20131367"},{"issue":"1","key":"9880_CR43","first-page":"1613","volume":"17","author":"J Lu","year":"2016","unstructured":"Lu J, Hoi SC, Wang J, Zhao P, Liu ZY (2016) Large scale online kernel learning. J Mach Learn Res 17(1):1613\u20131655","journal-title":"J Mach Learn Res"},{"issue":"3","key":"9880_CR44","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1214\/13-AOP892","volume":"42","author":"L Mackey","year":"2014","unstructured":"Mackey L, Jordan MI, Chen RY, Farrell B, Tropp JA et al (2014) Matrix concentration inequalities via the method of exchangeable pairs. Ann Probab 42(3):906\u2013945","journal-title":"Ann Probab"},{"issue":"2","key":"9880_CR45","first-page":"123","volume":"3","author":"MW Mahoney","year":"2011","unstructured":"Mahoney MW (2011) Randomized algorithms for matrices and data. Found Trends\u00ae Mach Learn 3(2):123\u2013224","journal-title":"Found Trends\u00ae Mach Learn"},{"issue":"4","key":"9880_CR46","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1016\/j.pneurobio.2011.09.005","volume":"95","author":"K Marek","year":"2011","unstructured":"Marek K, Jennings D, Lasch S, Siderowf A, Tanner C, Simuni T, Coffey C, Kieburtz K, Flagg E, Chowdhury S et al (2011) The Parkinson progression marker initiative (PPMI). Prog Neurobiol 95(4):629\u2013635","journal-title":"Prog Neurobiol"},{"key":"9880_CR47","unstructured":"May A, Garakani AB, Lu Z, Guo D, Liu K, Bellet A, Fan L, Collins M, Hsu D, Kingsbury B, et al (2017) Kernel approximation methods for speech recognition. arXiv preprint arXiv:1701.03577"},{"key":"9880_CR48","doi-asserted-by":"crossref","unstructured":"Mehrkanoon S, Suykens JA (2016) Scalable semi-supervised kernel spectral learning using random Fourier features. In: 2016 IEEE symposium series on computational intelligence (SSCI). IEEE, pp 1\u20138","DOI":"10.1109\/SSCI.2016.7849934"},{"key":"9880_CR49","unstructured":"Munkhoeva M, Kapushev Y, Burnaev E, Oseledets I (2018) Quadrature-based features for kernel approximation. In: Advances in neural information processing systems, pp 9147\u20139156"},{"key":"9880_CR50","unstructured":"Musco C, Musco C (2016) Provably useful kernel matrix approximation in linear time. arXiv preprint arXiv:1605.07583"},{"key":"9880_CR51","doi-asserted-by":"crossref","unstructured":"Nelson J, Price E, Wootters M (2014) New constructions of RIP matrices with fast multiplication and fewer rows. In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms. SIAM, pp 1515\u20131528","DOI":"10.1137\/1.9781611973402.111"},{"key":"9880_CR52","unstructured":"Pennington J, Felix XY, Kumar S (2015) Spherical random features for polynomial kernels. In: Advances in neural information processing systems, pp 1846\u20131854"},{"key":"9880_CR53","doi-asserted-by":"crossref","unstructured":"Pham N, Pagh R (2013) Fast and scalable polynomial kernels via explicit feature maps. In: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 239\u2013247","DOI":"10.1145\/2487575.2487591"},{"key":"9880_CR54","unstructured":"Rahimi A, Recht B (2009) Weighted sums of random kitchen sinks: replacing minimization with randomization in learning. In: Advances in neural information processing systems, pp 1313\u20131320"},{"key":"9880_CR55","unstructured":"Rahimi A, Recht B, et\u00a0al. (2007) Random features for large-scale kernel machines. In: NIPS, vol 3, p 5"},{"key":"9880_CR56","unstructured":"Rudi A, Rosasco L (2017) Generalization properties of learning with random features. In: Advances in neural information processing systems, pp 3218\u20133228"},{"key":"9880_CR57","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.patcog.2017.06.003","volume":"71","author":"FM Schleif","year":"2017","unstructured":"Schleif FM, Tino P (2017) Indefinite core vector machine. Pattern Recognit 71:187\u2013195","journal-title":"Pattern Recognit"},{"key":"9880_CR58","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.patrec.2019.10.024","volume":"129","author":"FM Schleif","year":"2020","unstructured":"Schleif FM, Raab C, Tino P (2020) Sparsification of core set models in non-metric supervised learning. Pattern Recognit Lett 129:1\u20137","journal-title":"Pattern Recognit Lett"},{"key":"9880_CR59","doi-asserted-by":"publisher","first-page":"811","DOI":"10.2307\/1968466","volume":"39","author":"IJ Schoenberg","year":"1938","unstructured":"Schoenberg IJ (1938) Metric spaces and completely monotone functions. Ann Math 39:811\u2013841","journal-title":"Ann Math"},{"key":"9880_CR60","unstructured":"Shahrampour S, Beirami A, Tarokh V (2017) On data-dependent random features for improved generalization in supervised learning. arXiv preprint arXiv:1712.07102"},{"key":"9880_CR61","doi-asserted-by":"crossref","unstructured":"Shahrampour S, Beirami A, Tarokh V (2018) Supervised learning using data-dependent random features with application to seizure detection. In: 2018 IEEE conference on decision and control (CDC). IEEE, pp 1168\u20131173","DOI":"10.1109\/CDC.2018.8619558"},{"key":"9880_CR62","unstructured":"Sinha A, Duchi JC (2016) Learning kernels with random features. In: Advances in neural information processing systems, pp 1298\u20131306"},{"key":"9880_CR63","unstructured":"Sriperumbudur B, Szab\u00f3 Z (2015) Optimal rates for random Fourier features. In: Advances in neural information processing systems, pp 1144\u20131152"},{"key":"9880_CR64","unstructured":"Sutherland DJ, Schneider J (2015) On the error of random Fourier features. In: Proceedings of the thirty-first conference on uncertainty in artificial intelligence. AUAI Press, pp 862\u2013871"},{"issue":"1","key":"9880_CR65","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1186\/1471-2105-7-173","volume":"7","author":"AV Uzilov","year":"2006","unstructured":"Uzilov AV, Keegan JM, Mathews DH (2006) Detection of non-coding RNAs on the basis of predicted secondary structure formation free energy change. BMC Bioinform 7(1):143\u2013173","journal-title":"BMC Bioinform"},{"key":"9880_CR66","unstructured":"Wang Q (2012) Kernel principal component analysis and its applications in face recognition and active shape models. arXiv preprint arXiv:1207.3538"},{"key":"9880_CR67","unstructured":"Williams CK, Seeger M (2000) Using the Nystr\u00f6m method to speed up kernel machines. In: Proceedings of the 13th international conference on neural information processing systems. MIT press, pp 661\u2013667"}],"container-title":["Artificial Intelligence Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10462-020-09880-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10462-020-09880-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10462-020-09880-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,31]],"date-time":"2021-07-31T23:17:17Z","timestamp":1627773437000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10462-020-09880-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,1]]},"references-count":67,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["9880"],"URL":"https:\/\/doi.org\/10.1007\/s10462-020-09880-z","relation":{},"ISSN":["0269-2821","1573-7462"],"issn-type":[{"value":"0269-2821","type":"print"},{"value":"1573-7462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,1]]},"assertion":[{"value":"1 August 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}