This paper presents a method for spectral grouping using the Nyström method, which significantly reduces the computational requirements of grouping algorithms based on spectral partitioning, making them feasible for large-scale problems. The approach is based on the Nyström method, a technique for solving eigenfunction problems. This method allows the complete grouping solution to be extrapolated using only a small number of samples, leveraging the fact that there are far fewer coherent groups in a scene than pixels. The paper discusses the application of the Nyström method to the Normalized Cut (NCut) grouping algorithm. The method involves solving the grouping problem for a small random subset of pixels and then extrapolating this solution to the full set of pixels in the image or image sequence. This provides the flexibility of pairwise grouping with a computational complexity comparable to that of central grouping. The approach is simple and has the appealing characteristic that for a given number of sample points, its complexity scales linearly with the resolution of the image. The paper also discusses the performance considerations of the Nyström method, including approximation properties and computational efficiency. It presents results on static images and video, demonstrating the effectiveness of the method in segmenting images and videos. The method is shown to be effective in color and texture segmentation, as well as in spatiotemporal segmentation. The Nyström method is particularly useful for large-scale problems due to its computational efficiency and ability to handle large datasets. The authors also discuss the application of the Nyström method to various types of data, including images, videos, and other high-dimensional data. The method is shown to be effective in capturing the salient groups in typical natural images with a relatively small number of samples. The paper concludes with a discussion of the potential of the Nyström method in extending powerful pairwise grouping methods to the domain of video. The method is shown to be computationally efficient and numerically stable, making it a promising approach for image and video segmentation.This paper presents a method for spectral grouping using the Nyström method, which significantly reduces the computational requirements of grouping algorithms based on spectral partitioning, making them feasible for large-scale problems. The approach is based on the Nyström method, a technique for solving eigenfunction problems. This method allows the complete grouping solution to be extrapolated using only a small number of samples, leveraging the fact that there are far fewer coherent groups in a scene than pixels. The paper discusses the application of the Nyström method to the Normalized Cut (NCut) grouping algorithm. The method involves solving the grouping problem for a small random subset of pixels and then extrapolating this solution to the full set of pixels in the image or image sequence. This provides the flexibility of pairwise grouping with a computational complexity comparable to that of central grouping. The approach is simple and has the appealing characteristic that for a given number of sample points, its complexity scales linearly with the resolution of the image. The paper also discusses the performance considerations of the Nyström method, including approximation properties and computational efficiency. It presents results on static images and video, demonstrating the effectiveness of the method in segmenting images and videos. The method is shown to be effective in color and texture segmentation, as well as in spatiotemporal segmentation. The Nyström method is particularly useful for large-scale problems due to its computational efficiency and ability to handle large datasets. The authors also discuss the application of the Nyström method to various types of data, including images, videos, and other high-dimensional data. The method is shown to be effective in capturing the salient groups in typical natural images with a relatively small number of samples. The paper concludes with a discussion of the potential of the Nyström method in extending powerful pairwise grouping methods to the domain of video. The method is shown to be computationally efficient and numerically stable, making it a promising approach for image and video segmentation.