Spectral grouping using the Nystrom method

By Charless C. Fowlkes, Serge J. Belongie, Fan Chung Graham, Jitendra Malik. 2004

1,518 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Media Technology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

In Media Technology

Citations in the corpus

Set Transformer (2018, methodology): “…is loosely based on the inducing point methods used in sparse Gaussian processes (Snelson & Ghahramani, 2005) and the Nystr¨om method for matrix decomposition (Fowlkes et al., 2004). m trainable inducing points can also be seen as m independent memory cells accessed with an attention mechanism.”
Spectral segmentation with multiscale graph decomposition (2005, methodology): “Both algorithms require correct initial graph coarsening [3].”
On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning (2005, methodology): “A second motivation was to clarify the relationships between our randomized SVD algorithms [16], our randomized CUR algorithms [17], and the Nyström-based methods of [40, 38, 21].”
Large-Scale Multi-View Spectral Clustering via Bipartite Graph (2015, methodology): “To address this problem, several methods have been proposed, e.g. (Passerini, Pontil, and Frasconi 2004; Fowlkes et al. 2004; Alzate and Suykens 2010; Bengio et al. 2004; Nie et al. 2011).”
Graph Neural Networks with Learnable Structural and Positional Representations (2021, methodology): “The complexity for computing this full factorization is O(E3/2) and O(n) with approximate Nystrom method (Fowlkes et al., 2004).”
Efficient Multilevel Eigensolvers with Applications to Data Analysis Tasks (2010, methodology): “An important difference is that the coarse set is chosen suchthattheremaining datapoints arestronglyconnectedto thechosencoarseset,thussuggestingamoreaccuratecoarseto-fine interpolation than the one suggested in [ 11 ].”
Deep clustering: Discriminative embeddings for segmentation and separation (2015, background): “This low-rank formulation also relates to spectral clustering in that the latter typically requires the Nyström low-rank approximation to the affinity matrix [22] for efficiency.”
Natural Image Statistics for Natural Image Segmentation (2003, neutral): “The results roughly resemble those of the level set implementation and could further be improved by integrating a smoothing term in the similarity measure and by implementing a more sophisticated approximation method (Fowlkes et al., 2004) to reduce block-artifacts.”
Spectral Hashing (2008, methodology): “This is the problem of out-of-sample extension of spectral methods which is often solved using the Nystrom method [13, 14].”
Benchmarking Graph Neural Networks (2023, background): “[28] Charless Fowlkes, Serge Belongie, Fan Chung, and Jitendra Malik.”
Fast multiscale clustering and manifold identification (2006, methodology): “The Nyström approximation [9] is used to decompose the similarity matrix W efficiently by choosing a random sample of the data, so that the complexity of decomposing W to its eigenvectors is of O(nN) where n is the size of the sample, and N is the size of the data set.”
Compressive Spectral Clustering (2016, methodology): “…Cohen, 2010), via a careful optimisation of diagonalisa-tion algorithms in the context of SC (Liu et al., 2007), or via matrix column-subsampling such as in the Nystr¨om method (Fowlkes et al., 2004), the nSPEC and cSPEC methods of (Wang et al., 2009), or in (Chen & Cai, 2011; Sakai & Imiya, 2009).”
Streaming Hierarchical Video Segmentation (2012, neutral): “To evaluate this progress and these methods’ comparative suitability for early video oversegmentation into supervoxels, Xu and Corso [10] study five methods, with varying characteristics (segmentation by weighted aggregation (SWA) [11, 12], graph-based (GB) [13], hierarchical graph-based (GBH) [3], ”
Fuzzy C-Means Clustering With Local Information and Kernel Metric for Image Segmentation (2013, methodology): “In addition, we test and compare the efficiency and the robustness of the proposed method (KWFLICM) with spectral graph grouping using Nystr öm method (NNcut) [25] and its predecessors, FLICM [1], RFLICM [12] and WFLICM (only introduce the trade-off weighted fuzzy factor into FLICM algorithm, here t”