Affordable Access

deepdyve-link
Publisher Website

Kernel K-Means Sampling for Nyström Approximation.

Authors
  • He, Li
  • Zhang, Hong
Type
Published Article
Journal
IEEE Transactions on Image Processing
Publisher
Institute of Electrical and Electronics Engineers
Publication Date
May 01, 2018
Volume
27
Issue
5
Pages
2108–2120
Identifiers
DOI: 10.1109/TIP.2018.2796860
PMID: 29432094
Source
Medline
License
Unknown

Abstract

A fundamental problem in Nyström-based kernel matrix approximation is the sampling method by which training set is built. In this paper, we suggest to use kernel -means sampling, which is shown in our works to minimize the upper bound of a matrix approximation error. We first propose a unified kernel matrix approximation framework, which is able to describe most existing Nyström approximations under many popular kernels, including Gaussian kernel and polynomial kernel. We then show that, the matrix approximation error upper bound, in terms of the Frobenius norm, is equal to the -means error of data points in kernel space plus a constant. Thus, the -means centers of data in kernel space, or the kernel -means centers, are the optimal representative points with respect to the Frobenius norm error upper bound. Experimental results, with both Gaussian kernel and polynomial kernel, on real-world data sets and image segmentation tasks show the superiority of the proposed method over the state-of-the-art methods.

Report this publication

Statistics

Seen <100 times