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 Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Recently, many works have focused on the characterization of non-lineardimensionality reduction methods obtained by quantizing linear embeddings,e.g., to reach fast processing time, efficient data compression procedures,novel geometry-preserving embeddings or to estimate the information/bits storedin this reduced data representation. In this work, we prove that many linearmaps known to respect the restricted isometry property (RIP) can induce aquantized random embedding with controllable multiplicative and additivedistortions with respect to the pairwise distances of the data points beingsconsidered. In other words, linear matrices having fast matrix-vectormultiplication algorithms (e.g., based on partial Fourier ensembles or on theadjacency matrix of unbalanced expanders) can be readily used in the definitionof fast quantized embeddings with small distortions. This implication is madepossible by applying right after the linear map an additive and random "dither"that stabilizes the impact of the uniform scalar quantization operator appliedafterwards. For different categories of RIP matrices, i.e., for differentlinear embeddings of a metric space $(\mathcal K \subset \mathbb R^n, \ell_q)$in $(\mathbb R^m, \ell_p)$ with $p,q \geq 1$, we derive upper bounds on theadditive distortion induced by quantization, showing that it decays either whenthe embedding dimension $m$ increases or when the distance of a pair ofembedded vectors in $\mathcal K$ decreases. Finally, we develop a novel"bi-dithered" quantization scheme, which allows for a reduced distortion thatdecreases when the embedding dimension grows and independently of theconsidered pair of vectors.

Time for dithering: fast and quantized random embeddings via the restricted isometry property