English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the effect of Johnson-Lindenstrauss transforms in various projectiveclustering problems, generalizing recent results which only applied tocenter-based clustering [MMR19]. We ask the general question: for a Euclideanoptimization problem and an accuracy parameter $\epsilon \in (0, 1)$, what isthe smallest target dimension $t \in \mathbb{N}$ such that aJohnson-Lindenstrauss transform $\Pi \colon \mathbb{R}^d \to \mathbb{R}^t$preserves the cost of the optimal solution up to a $(1+\epsilon)$-factor. Wegive a new technique which uses coreset constructions to analyze the effect ofthe Johnson-Lindenstrauss transform. Our technique, in addition applying tocenter-based clustering, improves on (or is the first to address) otherEuclidean optimization problems, including:  $\bullet$ For $(k,z)$-subspace approximation: we show that $t =\tilde{O}(zk^2 / \epsilon^3)$ suffices, whereas the prior best bound, of$O(k/\epsilon^2)$, only applied to the case $z = 2$ [CEMMP15].  $\bullet$ For $(k,z)$-flat approximation: we show $t =\tilde{O}(zk^2/\epsilon^3)$ suffices, completely removing the dependence on $n$from the prior bound $\tilde{O}(zk^2 \log n/\epsilon^3)$ of [KR15].  $\bullet$ For $(k,z)$-line approximation: we show $t = O((k \log \log n + z +\log(1/\epsilon)) / \epsilon^3)$ suffices, and ours is the first to give anydimension reduction result.

The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction