Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation
In all state-of-the-art sketching and coreset techniques for clustering, as well as in the best known fixed-parameter tractable approximation algorithms, randomness plays a key role. For the classic $k$-median and $k$-means problems, there are no known deterministic dimensionality reduction procedur...
Sábháilte in:
| Príomhchruthaitheoirí: | , , |
|---|---|
| Formáid: | Alt |
| Foilsithe / Cruthaithe: |
2023
|
| Ábhair: | |
| Rochtain ar líne: | https://arxiv.org/abs/2310.04076 http://arxiv.org/abs/2310.04076 |
| Clibeanna: |
Níl clibeanna ann, Bí ar an gcéad duine le clib a chur leis an taifead seo!
|
| _version_ | 1879174988390465536 |
|---|---|
| author | Cohen-Addad, Vincent Saulpic, David Schwiegelshohn, Chris |
| author_browse | Cohen-Addad, Vincent Saulpic, David Schwiegelshohn, Chris |
| author_facet | Cohen-Addad, Vincent Saulpic, David Schwiegelshohn, Chris |
| author_sort | Cohen-Addad, Vincent |
| building | arXiv |
| collection | Acceso abierto |
| description | In all state-of-the-art sketching and coreset techniques for clustering, as well as in the best known fixed-parameter tractable approximation algorithms, randomness plays a key role. For the classic $k$-median and $k$-means problems, there are no known deterministic dimensionality reduction procedure or coreset construction that avoid an exponential dependency on the input dimension $d$, the precision parameter $\varepsilon^{-1}$ or $k$. Furthermore, there is no coreset construction that succeeds with probability $1-1/n$ and whose size does not depend on the number of input points, $n$. This has led researchers in the area to ask what is the power of randomness for clustering sketches [Feldman, WIREs Data Mining Knowl. Discov'20]. Similarly, the best approximation ratio achievable deterministically without a complexity exponential in the dimension are $Ω(1)$ for both $k$-median and $k$-means, even when allowing a complexity FPT in the number of clusters $k$. This stands in sharp contrast with the $(1+\varepsilon)$-approximation achievable in that case, when allowing randomization.
In this paper, we provide deterministic sketches constructions for clustering, whose size bounds are close to the best-known randomized ones. We also construct a deterministic algorithm for computing $(1+\varepsilon)$-approximation to $k$-median and $k$-means in high dimensional Euclidean spaces in time $2^{k^2/\varepsilon^{O(1)}} poly(nd)$, close to the best randomized complexity.
Furthermore, our new insights on sketches also yield a randomized coreset construction that uses uniform sampling, that immediately improves over the recent results of [Braverman et al. FOCS '22] by a factor $k$. |
| first_indexed | 2026-10-16T00:21:51Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-2310.04076</identifier><datestamp>2023-10-09</datestamp>
<dc:title>Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation</dc:title>
<dc:creator>Cohen-Addad, Vincent</dc:creator>
<dc:creator>Saulpic, David</dc:creator>
<dc:creator>Schwiegelshohn, Chris</dc:creator>
<dc:subject>Data Structures and Algorithms</dc:subject>
<dc:description>In all state-of-the-art sketching and coreset techniques for clustering, as well as in the best known fixed-parameter tractable approximation algorithms, randomness plays a key role. For the classic $k$-median and $k$-means problems, there are no known deterministic dimensionality reduction procedure or coreset construction that avoid an exponential dependency on the input dimension $d$, the precision parameter $\varepsilon^{-1}$ or $k$. Furthermore, there is no coreset construction that succeeds with probability $1-1/n$ and whose size does not depend on the number of input points, $n$. This has led researchers in the area to ask what is the power of randomness for clustering sketches [Feldman, WIREs Data Mining Knowl. Discov'20]. Similarly, the best approximation ratio achievable deterministically without a complexity exponential in the dimension are $Ω(1)$ for both $k$-median and $k$-means, even when allowing a complexity FPT in the number of clusters $k$. This stands in sharp contrast with the $(1+\varepsilon)$-approximation achievable in that case, when allowing randomization.
In this paper, we provide deterministic sketches constructions for clustering, whose size bounds are close to the best-known randomized ones. We also construct a deterministic algorithm for computing $(1+\varepsilon)$-approximation to $k$-median and $k$-means in high dimensional Euclidean spaces in time $2^{k^2/\varepsilon^{O(1)}} poly(nd)$, close to the best randomized complexity.
Furthermore, our new insights on sketches also yield a randomized coreset construction that uses uniform sampling, that immediately improves over the recent results of [Braverman et al. FOCS '22] by a factor $k$. </dc:description>
<dc:description>FOCS 2023. Abstract reduced for arxiv requirements</dc:description>
<dc:date>2023-10-06</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2310.04076</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2310.04076</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2310.04076 |
| institution | arXiv |
| last_indexed | 2026-10-16T00:21:51Z |
| publishDate | 2023 |
| publishDateRange | 2023 |
| publishDateSort | 2023 |
| record_format | oai_dc |
| spelling | arxiv-2310.040762023-10-09 Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation Cohen-Addad, Vincent Saulpic, David Schwiegelshohn, Chris Data Structures and Algorithms In all state-of-the-art sketching and coreset techniques for clustering, as well as in the best known fixed-parameter tractable approximation algorithms, randomness plays a key role. For the classic $k$-median and $k$-means problems, there are no known deterministic dimensionality reduction procedure or coreset construction that avoid an exponential dependency on the input dimension $d$, the precision parameter $\varepsilon^{-1}$ or $k$. Furthermore, there is no coreset construction that succeeds with probability $1-1/n$ and whose size does not depend on the number of input points, $n$. This has led researchers in the area to ask what is the power of randomness for clustering sketches [Feldman, WIREs Data Mining Knowl. Discov'20]. Similarly, the best approximation ratio achievable deterministically without a complexity exponential in the dimension are $Ω(1)$ for both $k$-median and $k$-means, even when allowing a complexity FPT in the number of clusters $k$. This stands in sharp contrast with the $(1+\varepsilon)$-approximation achievable in that case, when allowing randomization. In this paper, we provide deterministic sketches constructions for clustering, whose size bounds are close to the best-known randomized ones. We also construct a deterministic algorithm for computing $(1+\varepsilon)$-approximation to $k$-median and $k$-means in high dimensional Euclidean spaces in time $2^{k^2/\varepsilon^{O(1)}} poly(nd)$, close to the best randomized complexity. Furthermore, our new insights on sketches also yield a randomized coreset construction that uses uniform sampling, that immediately improves over the recent results of [Braverman et al. FOCS '22] by a factor $k$. FOCS 2023. Abstract reduced for arxiv requirements 2023-10-06 text https://arxiv.org/abs/2310.04076 http://arxiv.org/abs/2310.04076 |
| spellingShingle | Data Structures and Algorithms Cohen-Addad, Vincent Saulpic, David Schwiegelshohn, Chris Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation |
| title | Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation |
| title_full | Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation |
| title_fullStr | Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation |
| title_full_unstemmed | Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation |
| title_short | Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation |
| title_sort | deterministic clustering in high dimensional spaces sketches and approximation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2310.04076 http://arxiv.org/abs/2310.04076 |
| work_keys_str_mv | AT cohenaddadvincent deterministicclusteringinhighdimensionalspacessketchesandapproximation AT saulpicdavid deterministicclusteringinhighdimensionalspacessketchesandapproximation AT schwiegelshohnchris deterministicclusteringinhighdimensionalspacessketchesandapproximation |