2015/04/23 by Laurent Jacques, Jacques, Laurent
Computer Science · Engineering · Medicine · #FOS: Computer and information sciences #Image and Signal Denoising Methods #Information Theory (cs.IT) #Medical Imaging Techniques and Applications #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1504.06170
openalex publication_date 2015/04/23 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
Under which conditions and with which distortions can we preserve the\npairwise-distances of low-complexity vectors, e.g., for structured sets such as\nthe set of sparse vectors or the one of low-rank matrices, when these are\nmapped in a finite set of vectors? This work addresses this general question\nthrough the specific use of a quantized and dithered random linear mapping\nwhich combines, in the following order, a sub-Gaussian random projection in\n mathbb RM of vectors in mathbb RN, a random translation, or "dither",\nof the projected vectors and a uniform scalar quantizer of resolution\n\δ>0 applied componentwise. Thanks to this quantized mapping we are first\nable to show that, with high probability, an embedding of a bounded set\n mathcal K \⊂ mathbb RN in \δ mathbb ZM can be achieved when\ndistances in the quantized and in the original domains are measured with the\n\ℓ1- and \ℓ2-norm, respectively, and provided the number of quantized\nobservations M is large before the square of the "Gaussian mean width" of\n mathcal K. In this case, we show that the embedding is actually\n"quasi-isometric" and only suffers of both multiplicative and additive\ndistortions whose magnitudes decrease as M-1/5 for general sets, and as\nM-1/2 for structured set, when M increases. Second, when one is only\ninterested in characterizing the maximal distance separating two elements of\n mathcal K mapped to the same quantized vector, i.e., the "consistency width"\nof the mapping, we show that for a similar number of measurements and with high\nprobability this width decays as M-1/4 for general sets and as 1/M for\nstructured ones when M increases. Finally, as an important aspect of our\nwork, we also establish how the non-Gaussianity of the mapping impacts the\nclass of vectors that can be embedded or whose consistency width provably\ndecays when M increases.\n