Scalable kernel k-means clustering with Nyström approximation: relative-error bounds

zbMATH Open1483.62116arXiv1706.02803MaRDI QIDQ4633019FDOQ4633019

Authors: Shusen Wang, Alex Gittens, Michael W. Mahoney 

Publication date: 2 May 2019

Full work available at URL: https://arxiv.org/abs/1706.02803

Recommendations

• Fast spectral clustering via the Nyström method
• Approximating spectral clustering via sampling: a review
• Fast kernel \(k\)-means clustering using incomplete Cholesky factorization
• On the Nyström method for approximating a gram matrix for improved kernel-based learning
• Dimensionality reduction for \(k\)-means clustering and low rank approximation

zbMATH Keywords

randomized linear algebrakernel \(k\)-means clusteringNyström method

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Cites Work

• MLlib: machine learning in Apache Spark
• Title not available (Why is that?)
• Least squares quantization in PCM
• NP-hardness of Euclidean sum-of-squares clustering
• Extensions of Lipschitz mappings into a Hilbert space
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• 10.1162/153244303321897735
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Title not available (Why is that?)
• Low-Rank Approximation and Regression in Input Sparsity Time
• Relative-Error $CUR$ Matrix Decompositions
• Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering
• Faster least squares approximation
• Randomized Algorithms for Matrices and Data
• Title not available (Why is that?)
• Title not available (Why is that?)
• Improved analysis of the subsampled randomized Hadamard transform
• Title not available (Why is that?)
• The Littlewood-Offord problem and invertibility of random matrices
• The complexity of the generalized Lloyd - Max problem (Corresp.)
• Random matrices: The distribution of the smallest singular values
• Lower Bounds for the Partitioning of Graphs
• Spectral partitioning works: planar graphs and finite element meshes
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• Linear-time approximation schemes for clustering problems in any dimensions
• On approximate geometric \(k\)-clustering
• On coresets for k-means and k-median clustering
• The Planar k-Means Problem is NP-Hard
• A local search approximation algorithm for k-means clustering
• Title not available (Why is that?)
• On the Nyström method for approximating a gram matrix for improved kernel-based learning
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Title not available (Why is that?)
• Title not available (Why is that?)
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• Fast approximation of matrix coherence and statistical leverage
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
• SPSD matrix approximation vis column selection: theories, algorithms, and extensions
• Title not available (Why is that?)
• Sublinear randomized algorithms for skeleton decompositions
• Title not available (Why is that?)
• Near-optimal column-based matrix reconstruction
• Sketching as a tool for numerical linear algebra
• Title not available (Why is that?)
• Random Projection Trees for Vector Quantization
• Improving CUR matrix decomposition and the Nyström approximation via adaptive sampling
• Algorithms and Computation
• Title not available (Why is that?)
• Compression of motion capture databases
• Improved Bounds for the Nyström Method With Application to Kernel Classification
• Title not available (Why is that?)
• Practical Sketching Algorithms for Low-Rank Matrix Approximation
• Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling
• Title not available (Why is that?)

Cited In (15)

• Breaking the curse of dimensionality: hierarchical Bayesian network model for multi-view clustering
• Diversity Sampling is an Implicit Regularization for Kernel Methods
• Title not available (Why is that?)
• Randomized numerical linear algebra: Foundations and algorithms
• Perturbations of CUR Decompositions
• Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
• Fast kernel \(k\)-means clustering using incomplete Cholesky factorization
• Coresets for kernel clustering
• Constrained clustering and multiple kernel learning without pairwise constraint relaxation
• Fast spectral clustering via the Nyström method
• A new robust fuzzy clustering validity index for imbalanced data sets
• Title not available (Why is that?)
• Core-elements for large-scale least squares estimation
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• Energy-based sequential sampling for low-rank PSD-matrix approximation

This page was built for publication: Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4633019)