Spectral partitioning with indefinite kernels using the nyström extension
Research output: Contribution to journal › Conference article › Research › peer-review
Standard
Spectral partitioning with indefinite kernels using the nyström extension. / Belongie, Serge; Fowlkes, Charless; Chung, Fan; Malik, Jitendra.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2002, p. 531-542.Research output: Contribution to journal › Conference article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Spectral partitioning with indefinite kernels using the nyström extension
AU - Belongie, Serge
AU - Fowlkes, Charless
AU - Chung, Fan
AU - Malik, Jitendra
N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - Fowlkes et al. [7] recently introduced an approximation to the Normalized Cut (NCut) grouping algorithm [18] based on random subsampling and the Nystr¨om extension. As presented, their method is restricted to the case where W, the weighted adjacency matrix, is positive definite. Although many common measures of image similarity (i.e. kernels) are positive definite, a popular example being Gaussianweighted distance, there are important cases that are not. In this work, we present a modification to Nystr¨om-NCut that does not require W to be positive definite. The modification only affects the orthogonalization step, and in doing so it necessitates one additional O(m3) operation, where m is the number of random samples used in the approximation. As such it is of interest to know which kernels are positive definite and which are indefinite. In addressing this issue, we further develop connections between NCut and related methods in the kernel machines literature. We provide a proof that the Gaussian-weighted chi-squared kernel is positive definite, which has thus far only been conjectured. We also explore the performance of the approximation algorithm on a variety of grouping cues including contour, color and texture.
AB - Fowlkes et al. [7] recently introduced an approximation to the Normalized Cut (NCut) grouping algorithm [18] based on random subsampling and the Nystr¨om extension. As presented, their method is restricted to the case where W, the weighted adjacency matrix, is positive definite. Although many common measures of image similarity (i.e. kernels) are positive definite, a popular example being Gaussianweighted distance, there are important cases that are not. In this work, we present a modification to Nystr¨om-NCut that does not require W to be positive definite. The modification only affects the orthogonalization step, and in doing so it necessitates one additional O(m3) operation, where m is the number of random samples used in the approximation. As such it is of interest to know which kernels are positive definite and which are indefinite. In addressing this issue, we further develop connections between NCut and related methods in the kernel machines literature. We provide a proof that the Gaussian-weighted chi-squared kernel is positive definite, which has thus far only been conjectured. We also explore the performance of the approximation algorithm on a variety of grouping cues including contour, color and texture.
UR - http://www.scopus.com/inward/record.url?scp=84949998208&partnerID=8YFLogxK
U2 - 10.1007/3-540-47977-5_35
DO - 10.1007/3-540-47977-5_35
M3 - Conference article
AN - SCOPUS:84949998208
SP - 531
EP - 542
JO - Lecture Notes in Computer Science
JF - Lecture Notes in Computer Science
SN - 0302-9743
T2 - 7th European Conference on Computer Vision, ECCV 2002
Y2 - 28 May 2002 through 31 May 2002
ER -
ID: 302056724