Papers › Small Width, Low Distortions: Quantized Random Embeddings of Low-complexity Sets
Small Width, Low Distortions: Quantized Random Embeddings of Low-complexity Sets
Laurent Jacques
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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 ℝᴹ of vectors in ℝᴺ, a random translation, or "dither", of the projected vectors and a uniform scalar quantizer of resolution δ>0 applied componentwise. Thanks to this quantized mapping we are first able to show that, with high probability, an embedding of a bounded set 𝒦 ⊂ℝᴺ in δℤᴹ can be achieved when distances in the quantized and in the original domains are measured with the ℓ₁- and ℓ₂-norm, respectively, and provided the number of quantized observations M is large before the square of the "Gaussian mean width" of 𝒦. 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 𝒦 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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections