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/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

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

Zendy Tools

Zendy Open

Given an arbitrary set of high dimensional points in $\ell_1$, there areknown negative results that preclude the possibility of always mapping them toa low dimensional $\ell_1$ space while preserving distances with smallmultiplicative distortion. This is in stark contrast with dimension reductionin Euclidean space ($\ell_2$) where such mappings are always possible. Whilethe first non-trivial lower bounds for $\ell_1$ dimension reduction wereestablished almost 20 years ago, there has been limited progress inunderstanding what sets of points in $\ell_1$ are conducive to alow-dimensional mapping.  In this work, we study a new characterization of $\ell_1$ metrics that areconducive to dimension reduction in $\ell_1$. Our characterization focuses onmetrics that are defined by the disagreement of binary variables over aprobability distribution -- any $\ell_1$ metric can be represented in thisform. We show that, for configurations of $n$ points in $\ell_1$ obtained fromtree Ising models, we can reduce dimension to $\mathrm{polylog}(n)$ withconstant distortion. In doing so, we develop technical tools for embeddingtruncated metrics which have been studied because of their applications incomputer vision, and are objects of independent interest in metric geometry.Among other tools, we show how any $\ell_1$ metric can be truncated with $O(1)$distortion and $O(\log(n))$ blowup in dimension.

Embedding Probability Distributions into Low Dimensional $\ell_1$: Tree Ising Models via Truncated Metrics