Search

The Nystrom method is an efficient approach to enabling large-scale kernel methods. The Nystrom method generates a fast approximation to any large-scale symmetric positive semidefinete (SPSD) matrix using only a few columns of the SPSD matrix. However, since the Nystrom approximation is low-rank, when the spectrum of the SPSD matrix decays slowly, the Nystrom approximation is of low accuracy. In this paper, we propose a variant of the Nystrom method called the modified Nystrom by spectral shifting (SS-Nystrom). The SS-Nystrom method works well no matter whether the spectrum of SPSD matrix decays fast or slow. We prove that our SS-Nystrom has a much stronger error bound than the standard and modified Nystrom methods, and that SS-Nystrom can be even more accurate than the truncated SVD of the same scale in some cases. We also devise an algorithm such that the SS-Nystrom approximation can be computed nearly as efficient as the modified Nystrom approximation. Finally, our SS-Nystrom method demonstrates significant improvements over the standard and modified Nystrom methods on several real-world datasets.

Kernel-based learning algorithms are well-known to poorly scale to large-scale applications. For such large tasks, a common solution is to use low-rank kernel approximation. While several algorithms and theoretical analyses have already been proposed in the literature, for low-rank Support Vector Machine or low-rank Kernel Ridge Regression, this work addresses the problem of scaling $\ell_p$-norm multiple kernel for large learning tasks using low-rank kernel approximations. Our contributions stand on proposing a novel optimization problem, which takes advantage of the low-rank kernel approximations and on introducing a proximal gradient algorithm for solving two different forms of that problem. We also provide theoretical results on the impact of the low-rank approximations over the kernel combination weights. Experimental evidences show that the proposed approaches scale better than the SMO-MKL algorithm for tasks involving about several hundred thousands of examples.

International audience; We consider the numerical approximation of a nonlinear integral operator equation by the Nyström method. We propose a new way of applying this method which leads to a major improvement: We can theoretically attain any desired accuracy while for the classical Nyström, the accuracy is limited by the quadrature error formula. The basic idea behind this new proposition is linearizing the nonlinear equation and discretizing the linearization process after, while the usual approach consists in the opposite.

Low rank approximation methods, e.g. the Nystrom method, are often used to speed up eigen-decomposition of kernel matrices. However, it cannot effectively update the extracted subspaces when datasets dynamically increase with time. In this paper, we propose an incremental Nystrom method for dynamic learning. Experimental results demonstrate the feasibility and effectiveness of the proposed method.

We have defined and established the superconvergence of the Sloan iterate obtained from a polynomial Galerkin approximation for solving the generalized airfoil equation. When all the integrals involved are evaluated by using Gaussian quadratures with the same number of nodes as basis elements, the resulting discrete Sloan iterate becomes the Nystrom approximation obtained by using the same rules. From this it follows that the discrete Sloan iterate v n and the discrete Galerkin approximation v n agree at the quadrature nodes. Thus v n converges no faster locally than v n . For practical purposes, computational superconvergence does not occur.

The purpose of this chapter is to compute at a low cost an approximate solution of a Fredholm integral equation at a given accuracy. Vainikko proposed to compute the Nystrom approximation of order n with quadrature two-grid iterations. We propose here to compute it with a two-grid method based on a projection method of a new type developed by Kulkarni. We will theoretically compare the absolute errors and the complexities of these two approximations.

We have developed a program, GENECUT, for analyzing datasets from gene expression profiling. GENECUT is based on a pairwise clustering method known as Normalized Cut [Shi and Malik, 1997]. GENECUT extracts global structures by progressively partitioning datasets into well-balanced groups, performing an intuitive k-way partitioning at each stage in contrast to commonly used 2-way partitioning schemes. By making use of the Nystrom approximation, it is possible to perform clustering on very large genomic datasets.

Spectral graph theoretic methods have recently shown great promise for the problem of image segmentation. However, due to the computational demands of these approaches, applications to large problems such as spatiotemporal data and high resolution imagery have been slow to appear. The contribution of this paper is a method that substantially reduces the computational requirements of grouping algorithms based on spectral partitioning making it feasible to apply them to very large grouping problems. Our approach is based on a technique for the numerical solution of eigenfunction problems known as the Nyström method. This method allows one to extrapolate the complete grouping solution using only a small number of samples. In doing so, we leverage the fact that there are far fewer coherent groups in a scene than pixels.

Segmentation of bony structures plays an important role in image-guided surgery of the spine. In this paper we give a first approach to the segmentation of vertebral bodies from 2D sagittal MR images of the spine using the normalized cuts (Ncut) segmentation technique [1], and the Nystrom approximation method [2].