Spectral grouping using the Nystrom method

Charless C. FowlkesSerge J. BelongieFan ChungJitendra Malik

article2004TPAMI1,527 citations

Proposes using the Nyström method to extrapolate spectral clustering solutions from a small subset of sample points, scaling image and video segmentation linearly with resolution while drastically cutting computational and memory costs.

Listen

Grouping visual elements into meaningful regions and objects is a foundational challenge in computer vision. While spectral graph-partitioning techniques such as Normalized Cut offer major advantages over prototype-based clustering by capturing complex cluster shapes and flexible similarity measures, their quadratic memory and cubic computational demands prevent practical deployment on high-resolution images and multi-frame video sequences.

The article demonstrates an approximation technique based on the classical Nyström method to substantially reduce the computational requirements of spectral grouping. The objective is to evaluate whether computing pairwise affinities for only a small subset of randomly sampled elements allows accurate extrapolation to full-resolution image and video segmentations.

The authors evaluate the approach through synthetic clustering benchmarks, comparative solver runtime analyses, and cross-validation across 300 natural scene images from the Corel dataset. They also test the method on practical image and video segmentation tasks incorporating color, texture, and temporal motion cues.

The key findings show that sampling fewer than one percent of total pixels—roughly 100 randomly chosen samples—reliably captures the leading graph eigenvectors and segments complex natural images. For a fixed sample size, the computational complexity scales linearly with the total number of pixels, transforming an intractable calculation into an efficient operation. In contrast to sparse eigensolvers whose convergence times degrade sharply on difficult problem instances, the Nyström approximation delivers robust and predictable performance, segmenting a multi-frame video volume in under one minute on standard hardware.

These results establish that spectral partitioning can be applied to large-scale vision tasks without arbitrary distance cutoffs or loss of long-range affinities. Practitioners can choose between a fast, one-step formulation when using positive definite similarity measures and a stable two-step approach when using general measures.

Organizations seeking to implement large-scale clustering or video segmentation should adopt the sampling-based extrapolation scheme to cut processing time and infrastructure costs. Future operational work should focus on automating the selection of the number of target clusters, as this parameter was set manually in the study.

The primary operational limitation is the requirement for appropriate sample sizing relative to scene complexity; undersampling complex scenes could cause small distinct objects to be missed. However, given the empirical stability across hundreds of natural images, confidence in the methodology's practical efficiency and grouping accuracy remains high.

University of California Berkeley University of California, San Diego affinity matrix computer vision cross validation spectral grouping Nyström method spectral partitioning

Fowlkes et al (2004).pdf

Paper: Using the Nyström Method to Speed Up Kernel Machines, Christopher K. I. Williams et al. (2000). It provides the foundational framework for using the Nyström method to approximate large kernel matrices and speed up kernel computations, which directly enables the sampling-based spectral grouping method.
Paper: On Spectral Clustering: Analysis and an algorithm, Andrew Y. Ng et al. (2001). It establishes the canonical normalized spectral clustering algorithm and its mathematical foundations, providing the base graph-partitioning framework that the source paper accelerates.
Paper: Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering, Mikhail Belkin et al. (2001). It introduces graph Laplacian eigenmaps for spectral embedding and clustering, which underpins the eigenvector formulations used in visual grouping.
Paper: Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifold, L. Saul et al. (2003). It provides fundamental principles of preserving local neighborhood geometry and solving generalized eigenvalue problems for non-linear data manifolds.

Paper: A tutorial on spectral clustering, Ulrike von Luxburg (2007). This tutorial offers a comprehensive theoretical and practical survey of graph Laplacians and spectral clustering, consolidating the foundational concepts accelerated by Nyström-based approximations.
Paper: Self-Tuning Spectral Clustering, Lihi Zelnik-Manor et al. (2004). It extends spectral clustering methodology by introducing local scale estimation and automatic cluster count determination, addressing key operational limitations highlighted in the source paper.
Paper: Random Walks for Image Segmentation, Leo Grady (2006). It develops an alternative graph-based segmentation framework using discrete random walks and Dirichlet problems, offering a complementary linear-system perspective to spectral graph cuts.
Paper: Robust Subspace Segmentation by Low-Rank Representation, Guangcan Liu et al. (2010). It advances spectral segmentation to corrupted data by constructing affinity graphs via low-rank representation before applying spectral clustering.
Paper: Sparse Subspace Clustering: Algorithm, Theory, and Applications, Ehsan Elhamifar et al. (2012). It builds upon spectral clustering pipelines by applying l1-minimization self-expressiveness to form affinity graphs for high-dimensional subspace clustering.
Paper: Graph Regularized Nonnegative Matrix Factorization for Data Representation, Deng Cai et al. (2011). It combines graph Laplacian regularization with matrix factorization, generalizing manifold-preserving spectral concepts to parts-based representations.

Cover for Spectral grouping using the Nystrom method

Abstract

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.

1 INTRODUCTION
2 SPECTRAL METHODS FOR PAIRWISE CLUSTERING
3 THE NYSTRÖM EXTENSION
3.1 Background
3.2 Matrix Completion
3.3 Methods of Solution
3.4 Application to Normalized Cut
4 PERFORMANCE CONSIDERATIONS
4.1 Approximation Properties
4.2 Sampling
5 SEGMENTATION RESULTS
5.1 Color and Texture Segmentation
5.2 Spatio-Temporal Segmentation
6 CONCLUSION
APPENDIX A PROOF OF ONE-SHOT METHOD
APPENDIX B PROOF OF POSITIVE DEFINITENESS OF ε²ij
ACKNOWLEDGMENTS
REFERENCES

Knowls

Knowl 1 — Nyström Matrix Completion for Large Affinity Matrices
model/method
Let $W \in \mathbb{R}^{N \times N}$ be a symmetric pairwise affinity matrix defined over $N$ data points (such as pixels or voxels). Let $n \ll N$ sample points be chosen, and denote $m = N - n$ . When the rows and columns of $W$ are permuted so that the $n$ samples appear first, $W$ is partitioned into subblocks as:

$W = \begin{bmatrix} A & B \\ B^T & C \end{bmatrix}$

where $A \in \mathbb{R}^{n \times n}$ represents affinities among the sample points, $B \in \mathbb{R}^{n \times m}$ represents affinities between sample points and the remaining $m$ points, and $C \in \mathbb{R}^{m \times m}$ represents affinities among the unselected points.

The Nyström extension approximates the unobserved block $C$ by $B^T A^{-1} B$ , yielding the low-rank approximated matrix $\hat{W}$ :

$\hat{W} = \begin{bmatrix} A & B \\ B^T & B^T A^{-1} B \end{bmatrix} = \begin{bmatrix} A \\ B^T \end{bmatrix} A^{-1} \begin{bmatrix} A & B \end{bmatrix}$

When $A$ is rank-deficient or ill-conditioned due to sample redundancies, the Moore-Penrose pseudoinverse $A^+$ replaces $A^{-1}$ . The approximation error on the unobserved block is quantified by the Schur complement norm $\|C - B^T A^{-1} B\|$ , which measures how well the rows of $B$ span the pairwise interactions in $C$ .
Knowl 2 — One-Shot Orthonormal Eigendecomposition for Positive Definite Submatrices
theoretical result
When the sample affinity submatrix $A \in \mathbb{R}^{n \times n}$ of the partitioned affinity approximation $\hat{W} = \begin{bmatrix} A \\ B^T \end{bmatrix} A^{-1} \begin{bmatrix} A & B \end{bmatrix}$ is positive definite, the exact orthonormal eigendecomposition of $\hat{W} \in \mathbb{R}^{N \times N}$ satisfying $\hat{W} = V \Lambda_S V^T$ and $V^T V = I_n$ is computed in a single $n \times n$ diagonalization step.

Let $A^{1/2}$ be the symmetric positive definite square root of $A$ , and define the symmetric matrix $S \in \mathbb{R}^{n \times n}$ by:

$S = A + A^{-1/2} B B^T A^{-1/2}$

Let $S = U_S \Lambda_S U_S^T$ be the eigendecomposition of $S$ , where $U_S \in \mathbb{R}^{n \times n}$ is orthogonal ( $U_S^T U_S = I_n$ ) and $\Lambda_S \in \mathbb{R}^{n \times n}$ is the diagonal matrix of eigenvalues. The $N \times n$ matrix $V$ containing the leading orthonormal eigenvectors of $\hat{W}$ is:

$V = \begin{bmatrix} A \\ B^T \end{bmatrix} A^{-1/2} U_S \Lambda_S^{-1/2}$

This construction satisfies both $V^T V = I_n$ and $V \Lambda_S V^T = \hat{W}$ without ever explicitly computing or materializing the $(N-n) \times (N-n)$ block $B^T A^{-1} B$ .
Knowl 3 — Implicit Degree Vector Computation for Nyström Normalized Cut
equation
In Normalized Cut spectral clustering, constructing the normalized affinity matrix $D^{-1/2} W D^{-1/2}$ requires the row-sum degree vector $d = W \mathbf{1}_N$ , where $D = \text{diag}(d)$ and $\mathbf{1}_k$ denotes a $k$ -dimensional column vector of all ones. For the Nyström-approximated affinity matrix $\hat{W} = \begin{bmatrix} A & B \\ B^T & B^T A^{-1} B \end{bmatrix}$ with $A \in \mathbb{R}^{n \times n}$ and $B \in \mathbb{R}^{n \times m}$ ( $m = N - n$ ), the approximated degree vector $\hat{d} = \hat{W} \mathbf{1}_N \in \mathbb{R}^N$ is computed directly without calculating $B^T A^{-1} B$ as:

$\hat{d} = \begin{bmatrix} A \mathbf{1}_n + B \mathbf{1}_m \\ B^T \mathbf{1}_n + B^T A^{-1} B \mathbf{1}_m \end{bmatrix} = \begin{bmatrix} a_r + b_r \\ b_c + B^T A^{-1} b_r \end{bmatrix}$

where $a_r = A \mathbf{1}_n \in \mathbb{R}^n$ and $b_r = B \mathbf{1}_m \in \mathbb{R}^n$ are the row sums of $A$ and $B$ , respectively, and $b_c = B^T \mathbf{1}_n \in \mathbb{R}^m$ is the column sum vector of $B$ .

Given $\hat{d}$ , the entries of the normalized subblocks $\bar{A} \in \mathbb{R}^{n \times n}$ and $\bar{B} \in \mathbb{R}^{n \times m}$ of $\hat{D}^{-1/2} \hat{W} \hat{D}^{-1/2}$ (where $\hat{D} = \text{diag}(\hat{d})$ ) are computed as:

$\bar{A}_{ij} = \frac{A_{ij}}{\sqrt{\hat{d}_i \hat{d}_j}}, \quad i, j \in \{1, \dots, n\}$

$\bar{B}_{ij} = \frac{B_{ij}}{\sqrt{\hat{d}_i \hat{d}_{j+n}}}, \quad i \in \{1, \dots, n\}, \; j \in \{1, \dots, m\}$
Knowl 4 — Nyström Normalized Cut Spectral Clustering Algorithm
algorithm
The Nyström Normalized Cut algorithm computes approximate leading spectral embedding coordinates for $N$ data points using affinities evaluated on $n$ randomly sampled points ( $n \ll N$ ) and partitions the dataset via $k$ -means.
Input: Unnormalized affinity submatrices $A \in \mathbb{R}^{n \times n}$ and $B \in \mathbb{R}^{n \times m}$ ( $m = N - n$ ), number of desired eigenvectors $N_E$ , number of clusters $k$
Output: Cluster assignment vector $c \in \{1, \dots, k\}^N$
$a_r \leftarrow A \mathbf{1}_n$
$b_r \leftarrow B \mathbf{1}_m$
$b_c \leftarrow B^T \mathbf{1}_n$
$d_1 \leftarrow a_r + b_r$
$d_2 \leftarrow b_c + B^T A^{-1} b_r$
$\hat{d} \leftarrow \begin{bmatrix} d_1 \\ d_2 \end{bmatrix}$
For $i = 1$ to $n$ , $j = 1$ to $n$ :
     $\bar{A}_{ij} \leftarrow A_{ij} / \sqrt{\hat{d}_i \hat{d}_j}$
For $i = 1$ to $n$ , $j = 1$ to $m$ :
     $\bar{B}_{ij} \leftarrow B_{ij} / \sqrt{\hat{d}_i \hat{d}_{j+n}}$
$A_{\text{si}} \leftarrow (\bar{A})^{-1/2}$
$Q \leftarrow \bar{A} + A_{\text{si}} \bar{B} \bar{B}^T A_{\text{si}}$
Compute eigendecomposition $Q = U_S \Lambda_S U_S^T$
$V \leftarrow \begin{bmatrix} \bar{A} \\ \bar{B}^T \end{bmatrix} A_{\text{si}} U_S \Lambda_S^{-1/2}$
Sort the columns of $V$ in ascending order according to the eigenvalues of $I - \Lambda_S$
For $i = 1$ to $N_E$ , $j = 1$ to $N$ :
     $E_{ij} \leftarrow V_{j, i+1} / V_{j, 1}$
Cluster the $N$ column vectors of $E \in \mathbb{R}^{N_E \times N}$ into $k$ groups using $k$ -means
return cluster assignments $c$
The algorithm operates in $O(n^3 + n^2 N)$ time, allowing pairwise spectral grouping to scale linearly with the total element count $N$ .
Knowl 5 — Positive Definiteness of the Exponential Chi-Square Histogram Kernel
theoretical result
Let $h_i, h_j \in \mathbb{R}^K$ be discrete probability histograms with positive bins ( $h_i(k) > 0$ for all $i$ and $k \in \{1, \dots, K\}$ ). The $\chi^2$ distance between $h_i$ and $h_j$ is given by:

$\chi_{ij}^2 = \frac{1}{2} \sum_{k=1}^K \frac{(h_i(k) - h_j(k))^2}{h_i(k) + h_j(k)} = 1 - 2 \sum_{k=1}^K \frac{h_i(k) h_j(k)}{h_i(k) + h_j(k)}$

The affinity kernel $W_{ij} = \exp(-\chi_{ij}^2 / \sigma)$ with scale $\sigma > 0$ is strictly positive definite. This holds because the matrix $Q$ with entries $Q_{ij} = 2 \sum_{k=1}^K \frac{h_i(k) h_j(k)}{h_i(k) + h_j(k)}$ is positive definite, as demonstrated by the integral identity $\frac{1}{a+b} = \int_0^1 x^{a+b-1} dx$ , which yields the quadratic form:

$c^T Q c = 2 \sum_{k=1}^K \int_0^1 \left( \sum_{i=1}^n c_i h_i(k) x^{h_i(k) - 1/2} \right)^2 dx > 0$

for any non-zero real vector $c$ . Since $W_{ij} = \exp(-1/\sigma) \exp(Q_{ij}/\sigma)$ and the exponential of a positive definite matrix is positive definite, $W$ is positive definite. This guarantees that affinity submatrices $A$ generated by Gaussian-weighted $\chi^2$ histogram comparisons are positive definite, ensuring the one-shot Nyström solution is applicable.
Knowl 6 — Two-Step Orthonormalization for Indefinite Sample Affinity Submatrices
model/method
When the sample affinity submatrix $A \in \mathbb{R}^{n \times n}$ is indefinite, the symmetric square root $A^{1/2}$ is undefined, preventing the one-shot method from being used. Instead, orthonormal eigenvectors of $\hat{W} = \begin{bmatrix} A & B \\ B^T & B^T A^{-1} B \end{bmatrix}$ are computed in two steps:
1. Diagonalize the sample submatrix $A = U_A \Lambda_A U_A^T$ , and evaluate the standard Nyström extension to form the non-orthogonal approximate eigenvector matrix $U \in \mathbb{R}^{N \times n}$ :
$U = \begin{bmatrix} U_A \\ B^T U_A \Lambda_A^{-1} \end{bmatrix}$
1. Define $Z = U \Lambda_A^{1/2} \in \mathbb{R}^{N \times n}$ such that $\hat{W} = Z Z^T$ . Compute the $n \times n$ inner product matrix $Z^T Z$ and its eigendecomposition $Z^T Z = F \Sigma F^T$ , where $F \in \mathbb{R}^{n \times n}$ is orthogonal and $\Sigma \in \mathbb{R}^{n \times n}$ contains the eigenvalues.
2. The leading orthonormal eigenvectors $V \in \mathbb{R}^{N \times n}$ and eigenvalues $\Lambda \in \mathbb{R}^{n \times n}$ of $\hat{W}$ are:
$V = Z F \Sigma^{-1/2}, \quad \Lambda = \Sigma$

which satisfy $V^T V = I_n$ and $\hat{W} = V \Sigma V^T$ . This two-step process requires an additional $O(n^3)$ operations and introduces greater loss of numerical precision than the one-shot method.
Knowl 7 — Computational Complexity of Nyström Spectral Partitioning
theoretical result
For an image or dataset of $N$ pixels and $n$ randomly selected sample points ( $n \ll N$ ):
1. Affinity computations: Evaluates only $n N - n(n-1)/2$ entries (blocks $A$ and $B$ ) instead of all $N(N-1)/2$ entries of the dense affinity matrix, reducing storage requirements from $O(N^2)$ to $O(n N)$ .
2. Implicit degree vector computation: Requires $O(n^2 + n(N-n)) = O(n N)$ operations.
3. Inner matrix diagonalization ( $S$ or $Z^T Z$ ): Requires $O(n^3)$ operations.
4. Eigenvector extrapolation: Forming the full $N \times n$ matrix $V$ takes $O(n^2 N)$ operations.
The overall computational complexity is $O(n^3 + n^2 N)$ , which scales linearly with image size $N$ for a fixed sample size $n$ . In comparison, exact dense eigensolvers require $O(N^3)$ operations and $O(N^2)$ memory, while sparse iterative solvers (e.g., Lanczos) require $O(n_{\text{iter}} \cdot n \cdot N)$ operations, where the iteration count $n_{\text{iter}}$ to convergence varies widely and can degrade significantly on ill-conditioned affinity matrices.
Knowl 8 — Eigenvector Subspace Repeatability and Sample Efficiency on Natural Images
empirical result
The stability and sample efficiency of the Nyström Normalized Cut approximation was evaluated on 300 natural scene images from the Corel dataset (image size $240 \times 160 = 38,400$ pixels). Repeatability between two sets of leading $N_E = 4$ eigenvectors $U, V \in \mathbb{R}^{N \times N_E}$ computed from different, independent random sample subsets was evaluated using the normalized subspace projection metric:

$\frac{1}{N_E} \|U^T V\|_F^2 = 1 - \frac{1}{2 N_E} \|U U^T - V V^T\|_F^2$

which is invariant to internal orthogonal rotations of the eigensubspaces and yields $1.0$ for identical spans.

Across 190 unique pairwise comparisons over 20 random trials per image, the agreement metric increased monotonically from $\approx 0.72$ at $n = 20$ samples to $> 0.93$ at $n = 400$ samples. This demonstrates that drawing $n = 100$ to $400$ random samples—less than $1\%$ of total image pixels—is sufficient to capture the leading eigensubspace of natural image affinity matrices with high numerical repeatability.
Knowl 9 — Spatiotemporal Video Segmentation via Space-Time Nyström Embedding
model/method
Spatiotemporal video segmentation represents an entire video sequence of dimensions $X \times Y \times T$ as a single three-dimensional space-time volume graph of $N = X \cdot Y \cdot T$ voxels. Pairwise affinities combine local appearance cues (brightness, color, texture) and motion cues across space and time.

By drawing $n$ samples across the sequence (e.g., $n = 100$ voxels drawn uniformly from the first, middle, and last frames), the Nyström approximation computes only an $n \times N$ affinity matrix and obtains the leading $k$ eigenvectors of the normalized Laplacian in $O(n^3 + n^2 N)$ time.

Clustering the leading eigenvector coordinates with $k$ -means segments the full 3D volume simultaneously. This automatically establishes segment correspondence across video frames without requiring separate frame-to-frame optical flow tracking, motion layer models, or explicit boundary initialization. For a video sequence of $120 \times 120 \times 5$ voxels ( $N = 72,000$ ), segmentation with $n = 100$ completes in under one minute.

Coverage note — Specific qualitative image segmentation outputs (tiger image, flowerbed/garden video, jumping leap video) and standard texton/halftoning filterbank construction details from cited prior work were omitted in favor of the core mathematical principles, algorithms, complexity analyses, and quantitative findings.

References

1.D. Achlioptas, F. McSherry, and B. Schölkopf, ‘Sampling Techniques for Kernel Methods,’ Proc. Neural Information Processing Systems Conf., pp. 335-342, 2002.
2.E.H. Adelson and J.R. Bergen, ‘Spatiotemporal Energy Models for the Perception of Motion,’ J. Optical Society Am. A, vol. 2, no. 2, pp. 284-299, 1985.
3.C.T.H. Baker, The Numerical Treatment of Integral Equations. Oxford: Clarendon Press, 1977.
4.S. Belongie, C. Fowlkes, F. Chung, and J. Malik, ‘Spectral Partitioning with Indefinite Kernels Using the Nyström Extension,’ Proc. European Conf. Computer Vision, 2002.
5.C. Berg, J.P.R. Christensen, and P. Ressel, Harmonic Analysis on Semigroups. Springer-Verlag, 1984.
6.C.M. Bishop, Neural Networks for Pattern Recognition. Oxford Univ. Press, 1995.
7.R.C. Bolles, H.H. Baker, and D.H. Marimont, ‘Epipolar-Plane Image Analysis: An Approach to Determining Structure from Motion,’ Int’l. J. Computer Vision, vol. 1, pp. 7-55, 1987.
8.K. Boyer, D. Fagerström, M. Kubovy, P. Johansen, and S. Sarkar, ‘POCV99 Breakout Session Report: Spatiotemporal Grouping,’ Perceptual Organization for Artificial Vision Systems, S. Sarkar and K.L. Boyer, eds., 2000.
9.J.M. Buhmann, ‘Data Clustering and Learning,’ The Handbook of Brain Theory and Neural Networks, M.A. Arbib, ed., pp. 278-281, 1995.
10.O. Chapelle, P. Haffner, and V. Vapnik, ‘SVMs for Histogram Based Image Classification,’ IEEE Trans. Neural Networks, vol. 10, no. 5, pp. 1055-1064, Sept. 1999.
11.F.R.K. Chung, Spectral Graph Theory. Am. Math. Soc., 1997.
12.C. Fowlkes, S. Belongie, and J. Malik, ‘Efficient Spatiotemporal Grouping Using the Nyström Method,’ Proc. IEEE Conf. Computer Vision and Pattern Recognition, Dec. 2001.
13.A. Frieze and R. Kannan, ‘Quick Approximation to Matricies and Applications,’ Combinatorica, vol. 19, pp. 175-220, 1999.
14.A. Frieze, R. Kannan, and S. Vempala, ‘Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations,’ Proc. IEEE Symp. Foundations of Computer Science, pp. 370-378, 1998.
15.Y. Gdalyahu, D. Weinshall, and M. Werman, ‘Stochastic Image Segmentation by Typical Cuts,’ Proc. Conf. Computer Vision and Pattern Recognition, 1999.
16.S. Gepshtein and M. Kubovy, ‘The emergence of visual objects in space-time,’ Nat’l Academy of Science USA, vol. 97, no. 14, pp. 8186-8191, 2000.
17.D. Haussler, ‘Convolution Kernels on Discrete Structure,’ technical report, Univ. of California at Santa Cruz, 1999.
18.J. Malik, S. Belongie, T. Leung, and J. Shi, ‘Contour and Texture Analysis for Image Segmentation,’ Int’l. J. Computer Vision, vol. 43, no. 1, pp. 7-27, June 2001.
19.S. Mika, B. Schölkopf, A.J. Smola, K.-R. Müller, M. Scholz, and G. Rätsch, ‘Kernel PCA and De-Noising in Feature Spaces,’ Advances in Neural Information Processing Systems 11, pp. 536-542, 1999.
20.A.Y. Ng, M.I. Jordan, and Y. Weiss, ‘On Spectral Clustering: Analysis and an Algorithm,’ Proc. Neural Information Processing Systems Conf., 2002.
21.E.J. Nyström, ‘Über die Praktische Auflösung von Linearen Integralgleichungen mit Anwendungen auf Randwertaufgaben der Potentialtheorie,’ Commentationes Physico-Mathematicae, vol. 4, no. 15, pp. 1-52, 1928.
22.P. Perona and W.T. Freeman, ‘A Factorization Approach to Grouping,’ Proc. Fifth European Conf. Computer Vision, 1998.
23.W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery, Numerical Recipies in C, second ed. Cambridge Univ. Press, 1992.
24.J. Puzicha and S. Belongie, ‘Model-Based Halftoning for Color Image Segmentation,’ Proc. Int’l Conf. Pattern Recognition, vol. 3, pp. 629-632, 2000.
25.J. Puzicha, T. Hofmann, and J. Buhmann, ‘Non-Parametric Similarity Measures for Unsupervised Texture Segmentation and Image Retrieval,’ Computer Vision and Pattern Recognition, 1997.
26.S. Sarkar and K.L. Boyer, ‘Quantitative Measures of Change Based on Feature Organization: Eigenvalues and Eigenvectors,’ Proc. Conf. Computer Vision and Pattern Recognition, 1996.
27.B. Schölkopf, A. Smola, and K.-R. Müller, ‘Nonlinear Component Analysis as a Kernel Eigenvalue Problem,’ Neural Computation, vol. 10, pp. 1299-1319, 1998.
28.G.L. Scott and H.C. Longuet-Higgins, ‘An Algorithm for Associating the Features of Two Images,’ Proc. Royal Soc. London, vol. B-244, pp. 21-26, 1991.
29.J. Shi and J. Malik, ‘Motion Segmentation and Tracking Using Normalized Cuts,’ Proc. Int’l Conf. Computer Vision, Jan. 1998.
30.J. Shi and J. Malik, ‘Normalized Cuts and Image Segmentation,’ IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888-905, Aug. 2000.
31.Y. Weiss, ‘Smoothness in Layers: Motion Segmentation Using Nonparametric Mixture Estimation,’ Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 520-526, 1997.
32.Y. Weiss, ‘Segmentation Using Eigenvectors: A Unifying View,’ Proc. Seventh Int’l. Conf. Computer Vision, pp. 975-982, 1999.
33.Y. Weiss and E. Adelson, ‘A Unified Mixture Framework for Motion Segmentation: Incorporating Spatial Coherence and Estimating the Number of Models,’ Proc Conf. Computer Vision and Pattern Recognition, pp. 321-326, June 1996.
34.C. Williams and M. Seeger, ‘Using the Nyström Method to Speed Up Kernel Machines,’ Advances in Neural Information Processing Systems 13: Proc. 2000 Conf., T.K. Leen, T.G. Dietterich, and V. Tresp, eds., pp. 682-688, 2001.

Citation

MLA

Fowlkes, C., et al. “Spectral Grouping Using the Nystrom Method”. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 2, 2004, pp. 214–25, https://doi.org/10.1109/TPAMI.2004.1262185.

APA

Fowlkes, C., Belongie, S., Fan Chung, & Malik, J. (2004). Spectral grouping using the nystrom method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2), 214–225. https://doi.org/10.1109/TPAMI.2004.1262185

Chicago

Fowlkes, C., S. Belongie, Fan Chung, and J. Malik. 2004. “Spectral Grouping Using the Nystrom Method”. IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (2): 214–25. https://doi.org/10.1109/TPAMI.2004.1262185.

Harvard

Fowlkes, C. et al. (2004) “Spectral grouping using the nystrom method”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2), pp. 214–225. Available at: https://doi.org/10.1109/TPAMI.2004.1262185.

Vancouver

1. Fowlkes C, Belongie S, Fan Chung, Malik J (2004) Spectral grouping using the nystrom method. IEEE Transactions on Pattern Analysis and Machine Intelligence 26:214–225

BibTeX

@article{Fowlkes_2004, title={Spectral grouping using the nystrom method}, volume={26}, ISSN={0162-8828}, url={http://dx.doi.org/10.1109/TPAMI.2004.1262185}, DOI={10.1109/tpami.2004.1262185}, number={2}, journal={IEEE Transactions on Pattern Analysis and Machine Intelligence}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Fowlkes, C. and Belongie, S. and Fan Chung and Malik, J.}, year={2004}, month=Feb, pages={214–225} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Spectral grouping using the Nystrom method

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Nyström Matrix Completion for Large Affinity Matrices

Knowl 2 — One-Shot Orthonormal Eigendecomposition for Positive Definite Submatrices

Knowl 3 — Implicit Degree Vector Computation for Nyström Normalized Cut

Knowl 4 — Nyström Normalized Cut Spectral Clustering Algorithm

Knowl 5 — Positive Definiteness of the Exponential Chi-Square Histogram Kernel

Knowl 6 — Two-Step Orthonormalization for Indefinite Sample Affinity Submatrices

Knowl 7 — Computational Complexity of Nyström Spectral Partitioning

Knowl 8 — Eigenvector Subspace Repeatability and Sample Efficiency on Natural Images

Knowl 9 — Spatiotemporal Video Segmentation via Space-Time Nyström Embedding

References

Citation

BibTeX

Access the Paper