SCALABLE RIDGE LEVERAGE SCORE SAMPLING FOR THE NYSTR™M METHOD

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 O(n3) computation cost if n is the number of data, which is prohibitive when n is large. To tackle this problem, we here propose a O(n) divide-and-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 shows that the proposed approximate leverage score sampling scheme achieves a good trade-off between predictive performance and running time.