Dimension Reduction for Projective Clustering - Lima, Rafael Zuolo Coppini (Anais do Encontro de Teoria da Computação (ETC); 2022: Anais do VII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2022.223040, 2022)
The high dimensionality of data may be a barrier to algorithmic efficiency, mainly because of the well known “curse of dimensionality” that imposes exponential time and/or memory complexity for algorithms. It is natural then to search for ways to break this curse by relaxing the problem with approximate versions and by finding good ways to reduce the dimension of data. Our aim is to integrate and state slightly stronger results of approximation via dimension reduction for clustering under the l_2^2 metric. The dimension reduction is achieved by combining randomized techniques (the Johnson-Lindenstrauss Lemma) and deterministic techniques (the singular value decomposition).