solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看7670次
Fast binary embeddings, and quantized compressed sensing with structured matrices. (arXiv:1801.08639v1 [cs.IT])
来源于:arXiv
This paper deals with two related problems, namely distance-preserving binary
embeddings and quantization for compressed sensing . First, we propose fast
methods to replace points from a subset $\mathcal{X} \subset \mathbb{R}^n$,
associated with the Euclidean metric, with points in the cube $\{\pm 1\}^m$ and
we associate the cube with a pseudo-metric that approximates Euclidean distance
among points in $\mathcal{X}$. Our methods rely on quantizing fast
Johnson-Lindenstrauss embeddings based on bounded orthonormal systems and
partial circulant ensembles, both of which admit fast transforms. Our
quantization methods utilize noise-shaping, and include Sigma-Delta schemes and
distributed noise-shaping schemes. The resulting approximation errors decay
polynomially and exponentially fast in $m$, depending on the embedding method.
This dramatically outperforms the current decay rates associated with binary
embeddings and Hamming distances. Additionally, it is the first such binary
embedding r 查看全文>>