Small Width, Low Distortions: Quantized Random Embeddings of Low-complexity Sets

DOI10.1109/TIT.2017.2717583zbMATH Open1374.94520arXiv1504.06170OpenAlexW2962842041MaRDI QIDQ4589387FDOQ4589387

Authors: Laurent Jacques 

Publication date: 10 November 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Under which conditions and with which distortions can we preserve the pairwise-distances of low-complexity vectors, e.g., for structured sets such as the set of sparse vectors or the one of low-rank matrices, when these are mapped in a finite set of vectors? This work addresses this general question through the specific use of a quantized and dithered random linear mapping which combines, in the following order, a sub-Gaussian random projection in $mathbb{R}^M$ of vectors in $mathbb{R}^N$, a random translation, or "dither", of the projected vectors and a uniform scalar quantizer of resolution $delta>0$ applied componentwise. Thanks to this quantized mapping we are first able to show that, with high probability, an embedding of a bounded set $mathcalKsubsetmathbb{R}^N$ in $deltamathbb{Z}^M$ can be achieved when distances in the quantized and in the original domains are measured with the $el{l}_1$- and $el{l}_2$-norm, respectively, and provided the number of quantized observations $M$ is large before the square of the "Gaussian mean width" of $mathcalK$. In this case, we show that the embedding is actually "quasi-isometric" and only suffers of both multiplicative and additive distortions whose magnitudes decrease as $M^{-1/5}$ for general sets, and as $M^{-1/2}$ for structured set, when $M$ increases. Second, when one is only interested in characterizing the maximal distance separating two elements of $mathcalK$ mapped to the same quantized vector, i.e., the "consistency width" of the mapping, we show that for a similar number of measurements and with high probability this width decays as $M^{-1/4}$ for general sets and as $1/M$ for structured ones when $M$ increases. Finally, as an important aspect of our work, we also establish how the non-Gaussianity of the mapping impacts the class of vectors that can be embedded or whose consistency width provably decays when $M$ increases.

Full work available at URL: https://arxiv.org/abs/1504.06170

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (5)

• \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\)
• Fast Metric Embedding into the Hamming Cube
• Random embeddings with an almost Gaussian distortion
• Quantized compressed sensing: a survey
• Endpoint results for Fourier integral operators on noncompact symmetric spaces

This page was built for publication: Small Width, Low Distortions: Quantized Random Embeddings of Low-complexity Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4589387)