Time for dithering: fast and quantized random embeddings via the restricted isometry property
- 24 April 2017
- journal article
- research article
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 6 (4) , 441-476
Abstract
Recently, many works have focused on the characterization of nonlinear dimensionality 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 stored in this reduced data representation. In this work, we prove that many linear maps known to respect the restricted isometry property (RIP) can induce a quantized random embedding with controllable multiplicative and additive distortions with respect to the pairwise distances of the data points beings considered. In other words, linear matrices having fast matrix–vector multiplication algorithms (e.g. based on partial Fourier ensembles or on the adjacency matrix of unbalanced expanders) can be readily used in the definition of fast quantized embeddings with small distortions. This implication is made possible by applying right after the linear map an additive and random dither that stabilizes the impact of the uniform scalar quantization operator applied afterwards. For different categories of RIP matrices, i.e. for different linear embeddings of a metric space |$({\mathscr K} \subset \mathbb R^n, \ell_q)$| in |$(\mathbb R^m, \ell_p)$| with |$p,q \geqslant 1$|, we derive upper bounds on the additive distortion induced by quantization, showing that it decays either when the embedding dimension |$m$| increases or when the distance of a pair of embedded vectors in |${\mathscr K}$| decreases. Finally, we develop a novel bi-dithered quantization scheme, which allows for a reduced distortion that decreases when the embedding dimension grows and independently of the considered pair of vectors.Keywords
All Related Versions
This publication has 40 references indexed in Scilit:
- Restricted isometries for partial random circulant matricesApplied and Computational Harmonic Analysis, 2012
- Compressed sensing with coherent and redundant dictionariesApplied and Computational Harmonic Analysis, 2011
- Compressive Sensing by Random ConvolutionSIAM Journal on Imaging Sciences, 2009
- On sparse reconstruction from Fourier and Gaussian measurementsCommunications on Pure and Applied Mathematics, 2007
- Two observations regarding embedding subsets of Euclidean spaces in normed spacesAdvances in Mathematics, 2006
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- Empirical processes and random projectionsJournal of Functional Analysis, 2005
- Database-friendly random projections: Johnson-Lindenstrauss with binary coinsJournal of Computer and System Sciences, 2003
- An elementary proof of a theorem of Johnson and LindenstraussRandom Structures & Algorithms, 2002
- QuantizationIEEE Transactions on Information Theory, 1998