The high dimensionality of data may be a barrier to algorithmic efficiency (Nelson, 2020), mainly because of the well known curse of dimensionality which imposes exponential time and/or memory complexity for algorithms, such as the nearest neighbour problem (Har-Peled, Indyk, and Motwani, 2012). It is natural then to search for ways to break the curse by relaxing the problem with approximate versions and by finding good ways to reduce the dimension of data. Our objective is to write a dissertation about a dimension reduction scheme for clustering under 2 2 metric, with a focus on an approximation scheme for a particular case of this problem, called projective clustering. The dimension reduction is achieved by combining randomized techniques, such as the Johnson and Lindenstrauss Lemma, and deterministic techniques, such as the singular value decomposition. The result is an (1 + )-approximation for projective clustering that is polynomial in the number of data points and the dimension of the space. This dissertation will have as main references four papers: Sarlós, 2006, Feldman, Schmidt, and Sohler, 2020, Pratap and Sen, 2018 and Deshpande, Rademacher, Vempala, and Wang, 2006. The results presented in the dissertation will be either the original or modified versions that incorporate current improvements.

A dimensão dos dados pode ser uma barreira para a eficiência de algoritmos (Nelson, 2020) principal- mente em razão da chamada maldição da dimensão, que impõe dependências exponenciais na dimensão para a complexidade de tempo e/ou espaço dos algoritmos para alguns problemas. Este é o caso, por exemplo, do problema do vizinho mais próximo (Har-Peled, Indyk e Motwani, 2012). É natural então estudar aproximações de soluções dos problemas e formas de reduzir a dimensão das instâncias para tentar quebrar essa maldição. Nosso objetivo é escrever uma dissertação sobre um esquema de redução de dimensão para clustering (agrupamento) sob a métrica 2 2, pondo foco em um esquema de aproximação para um caso particular do problema anterior, chamado projective clustering (agrupamento projetivo). A redução de dimensão é feita combinando técnicas aleatorizadas, como o Lema de Johnson e Lindenstrauss, e determinísticas, como a decomposição em valores singulares. Obtém-se uma (1 + )-aproximação para o problema do agrupamento projetivo, polinomial no número de pontos e na dimensão. Esta dissertação terá como referências principais quatro artigos: Sarlós, 2006, Feldman, Schmidt e Sohler, 2020, Pratap e Sen, 2018 e Deshpande, Rade- macher, Vempala e Wang, 2006. Os resultados apresentados na dissertação serão ou os originais ou versões modificadas, incorporando aprimoramentos recentes.