2016/07/04 by Laurent Jacques, Jacques, Laurent, Valerio Cambareri +1 · 1 citation
Engineering · Mathematics · Physics and Astronomy · #FOS: Computer and information sciences #Information Theory (cs.IT) #Mathematical Analysis and Transform Methods #Random lasers and scattering media #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1607.00816
openalex publication_date 2016/07/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recently, many works have focused on the characterization of non-linear\ndimensionality reduction methods obtained by quantizing linear embeddings,≠.g., to reach fast processing time, efficient data compression procedures,\nnovel geometry-preserving embeddings or to estimate the information/bits stored\nin this reduced data representation. In this work, we prove that many linear\nmaps known to respect the restricted isometry property (RIP) can induce a\nquantized random embedding with controllable multiplicative and additive\ndistortions with respect to the pairwise distances of the data points beings\nconsidered. In other words, linear matrices having fast matrix-vector\nmultiplication algorithms (e.g., based on partial Fourier ensembles or on the\nadjacency matrix of unbalanced expanders) can be readily used in the definition\nof fast quantized embeddings with small distortions. This implication is made\npossible by applying right after the linear map an additive and random "dither"\nthat stabilizes the impact of the uniform scalar quantization operator applied\nafterwards. For different categories of RIP matrices, i.e., for different\nlinear embeddings of a metric space ( mathcal K \⊂ mathbb Rn, \ℓq)\nin ( mathbb Rm, \ℓp) with p,q \≥ 1, we derive upper bounds on the\nadditive distortion induced by quantization, showing that it decays either when\nthe embedding dimension m increases or when the distance of a pair of\nembedded vectors in mathcal K decreases. Finally, we develop a novel\n"bi-dithered" quantization scheme, which allows for a reduced distortion that\ndecreases when the embedding dimension grows and independently of the\nconsidered pair of vectors.\n