mlsanityData to 7 Oct 2026

New Coresets for Projective Clustering and Applications

arXiv 2203.04370 ↗First posted 8 Mar 2022cs.LGcited by 16

Not on the map. Why?

Abstract (arXiv)

(j,k)-projective clustering is the natural generalization of the family of k-clustering and j-subspace clustering problems. Given a set of points P in ℝd, the goal is to find k flats of dimension j, i.e., affine subspaces, that best fit P under a given distance measure. In this paper, we propose the first algorithm that returns an L_∞ coreset of size polynomial in d. Moreover, we give the first strong coreset construction for general M-estimator regression. Specifically, we show that our construction provides efficient coreset constructions for Cauchy, Welsch, Huber, Geman-McClure, Tukey, L1-L2, and Fair regression, as well as general concave and power-bounded loss functions. Finally, we provide experimental results based on real-world datasets, showing the efficacy of our approach.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Builds on 19 of its 56 references that are in the map. First posted on arXiv 8 Mar 2022.

Builds on

19 of 56 references.

References · 19

  1. 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
  2. 2018On Coresets for Logistic Regressioncited by 65
  3. 2020Coresets for Near-Convex Functionscited by 38
  4. 2019Data-Independent Neural Pruning via Coresetscited by 35
  5. 2020Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimalcited by 31
  6. 2018Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimensioncited by 27
  7. 2015Improved and Simplified Inapproximability for k-meanscited by 22
  8. 2018varepsilon-Coresets for Clustering (with Outliers) in Doubling Metricscited by 19
  9. 2018Near Optimal Linear Algebra in the Online and Sliding Window Modelscited by 19
  10. 2020On Coresets for Support Vector Machinescited by 19
  11. 2020Sets Clusteringcited by 19
  12. 2015Input Sparsity and Hardness for Robust Subspace Approximationcited by 12
7 more
  1. 2019Dimensionality Reduction for Tukey Regressioncited by 12
  2. 2019Tight Sensitivity Bounds For Smaller Coresetscited by 11
  3. 2019Fast and Accurate Least-Mean-Squares Solverscited by 10
  4. 2017Improved Coresets for Kernel Density Estimatescited by 8
  5. 2019Improved Algorithms for Time Decay Streamscited by 5
  6. 2014Approximation and Streaming Algorithms for Projective Clustering via Random Projectionscited by 4
  7. 2017Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 5; 2023: 7; 2024: 0; 2025: 2; 2026: 2.

16 papers.

Sort:

  1. 2022Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptionscited by 20
  2. 2023Provable Data Subset Selection For Efficient Neural Network Trainingcited by 14
  3. 2022Hardness and Algorithms for Robust and Sparse Optimizationcited by 8
  4. 2023Dataset Distillation Meets Provable Subset Selectioncited by 7
  5. 2023ORBSLAM3-Enhanced Autonomous Toy Drones: Pioneering Indoor Explorationcited by 5
  6. 2023AutoCoreset: An Automatic Practical Coreset Construction Frameworkcited by 4
  7. 2023On the Size and Approximation Error of Distilled Setscited by 3
  8. 2022Adaptive Sketches for Robust Regression with Importance Samplingcited by 2
  9. 2022Socially Fair Center-based and Linear Subspace Clusteringcited by 1
  10. 2025Improving Model Classification by Optimizing the Training Datasetcited by 1
  11. 2025Compress to Impress: Efficient LLM Adaptation Using a Single Gradient Step on 100 Samplescited by 1
  12. 2022Efficient NTK using Dimensionality Reductioncited by 0
4 more
  1. 2023Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streamingcited by 0
  2. 2023Computing Approximate ℓp Sensitivitiescited by 0
  3. 2026Deterministic Coreset for Lp Subspacecited by 0
  4. 2026Active Learning with Low-Rank Structure for Data Selectioncited by 0