2016/06/26 by Rameshwar Pratap, Pratap, Rameshwar, Sandeep Sen +1
Computer Science · Engineering · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1606.07992
openalex publication_date 2016/06/26 · arxiv created 2018/07/16 · arxiv updated 2018/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work, we present a randomized coreset construction for projective clustering, which involves computing a set of k closest j-dimensional linear (affine) subspaces of a given set of n vectors in d dimensions. Let A ∈ ℝn× d be an input matrix. An earlier deterministic coreset construction of Feldman et. al. relied on computing the SVD of A. The best known algorithms for SVD require min\nd2, n2d\ time, which may not be feasible for large values of n and d. We present a coreset construction by projecting the rows of matrix A on some orthonormal vectors that closely approximate the right singular vectors of A. As a consequence, when the values of k and j are small, we are able to achieve a faster algorithm, as compared to the algorithm of Feldman et. al., while maintaining almost the same approximation. We also benefit in terms of space as well as exploit the sparsity of the input dataset. Another advantage of our approach is that it can be constructed in a streaming setting quite efficiently.