HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Scalable ridge Leverage score sampling for the Nyström method

Abstract : The Nyström method, known as an efficient technique for approximating Gram matrices, builds upon a small subset of the data called landmarks, whose choice impacts the quality of the approximated Gram matrix. Various sampling methods have been proposed in the literature to choose such a subset, among which some based on ridge Leverage scores, which come with good theoretical and practical results. Nevertheless, direct computation of ridge leverage scores has an Θ(n 3) computation cost if n is the number of data, which is prohibitive when n is large. To tackle this problem, we here propose a Θ(n) divideand-conquer (DAC) method to approximate ridge leverage scores and we provide theoretical guarantees and empirical results regarding their ability to blend with the Nyström approximation strategy. Our experimental results show that the proposed approximate leverage score sampling scheme achieves a good trade-off between predictive performance and running time. Ridge leverage scores, Nyström approximation, kernel methods.
Document type :
Conference papers
Complete list of metadata

Contributor : Farah Cherfaoui Connect in order to contact the contributor
Submitted on : Friday, March 4, 2022 - 10:13:07 AM
Last modification on : Wednesday, April 27, 2022 - 3:34:35 AM


Files produced by the author(s)


  • HAL Id : hal-03597111, version 1



Farah Cherfaoui, Hachem Kadri, Liva Ralaivola. Scalable ridge Leverage score sampling for the Nyström method. ICASSP, May 2022, Singapour, Singapore. ⟨hal-03597111⟩



Record views


Files downloads