Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering

DOI10.1137/1.9781611973105.103zbMath1421.68219OpenAlexW2949910245MaRDI QIDQ5741812

Melanie Schmidt, Dan Feldman, Christian Sohler

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973105.103

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (32)

Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering ⋮ On the \(k\)-means/median cost function ⋮ Structural conditions for projection-cost preservation via randomized matrix multiplication ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ Unnamed Item ⋮ Optimal sampling designs for multidimensional streaming time series with application to power grid sensor data ⋮ Heuristic Ranking Classification Method for Complex Large-Scale Survival Data ⋮ Practical Sketching Algorithms for Low-Rank Matrix Approximation ⋮ Turning Grain Maps into Diagrams ⋮ Parameterized \(k\)-clustering: tractability island ⋮ Core-Sets: Updated Survey ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems ⋮ Improved Algorithms for Time Decay Streams ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ A quasi-Monte Carlo data compression algorithm for machine learning ⋮ Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics ⋮ Communication-Efficient Distributed Eigenspace Estimation ⋮ An improved Bregman \(k\)-means++ algorithm via local search ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Consensus and complementarity based maximum entropy discrimination for multi-view classification ⋮ The spherical \(k\)-means++ algorithm via local search ⋮ Random projections for Bayesian regression ⋮ Frequent Directions: Simple and Deterministic Matrix Sketching ⋮ Coresets for Fuzzy K-Means with Applications ⋮ Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering