In this paper we study the problem of recovering sparse or compressible
signals from uniformly quantized measurements. We present a new class of convex
optimization programs, or decoders, coined Basis Pursuit DeQuantizer of moment
$p$ (BPDQ$_p$), that model the quantization distortion more faithfully than the
commonly used Basis Pursuit DeNoise (BPDN) program. Our decoders proceed by
minimizing the sparsity of the signal to be reconstructed subject to a
data-fidelity constraint expressed in the $\ell_p$-norm of the residual error
for $2\leq p\leq \infty$.
We show theoretically that, (i) the reconstruction error of these new
decoders is bounded if the sensing matrix satisfies an extended Restricted
Isometry Property involving the $\ell_p$ norm, and (ii), for Gaussian random
matrices and uniformly quantized measurements, BPDQ$_p$ performance exceeds
that of BPDN by dividing the reconstruction error due to quantization by
$\sqrt{p+1}$. This last effect happens with high probability when the number of
measurements exceeds a value growing with $p$, i.e. in an oversampled situation
compared to what is commonly required by BPDN = BPDQ$_2$. To demonstrate the
theoretical power of BPDQ$_p$, we report numerical simulations on signal and
image reconstruction problems.

本研究提出了一类新的凸优化解码器 BPDQ$_p$ 来恢复从均匀量化测量中得到的稀疏信号，证明了在满足扩展的限制等距特性的矩阵中使用 BPDQ$_p$ 可以有效降低重构误差，同时在高斯随机矩阵和均匀量化测量下的表现超过传统的 BPDN 方案。

去量化压缩感知：过采样和非高斯约束相结合

Dequantizing Compressed Sensing: When Oversampling and Non-Gaussian  Constraints Combine

Let $G_{m \times n}$ be an $m \times n$ real random matrix whose elements are
independent and identically distributed standard normal random variables, and
let $\kappa_2(G_{m \times n})$ be the 2-norm condition number of $G_{m \times
n}$. We prove that, for any $m \geq 2$, $n \geq 2$ and $x \geq |n-m|+1$,
$\kappa_2(G_{m \times n})$ satisfies $
\frac{1}{\sqrt{2\pi}} ({c}/{x})^{|n-m|+1} < P(\frac{\kappa_2(G_{m \times n})}
{{n}/{(|n-m|+1)}}> x) <
\frac{1}{\sqrt{2\pi}} ({C}/{x})^{|n-m|+1}, $ where $0.245 \leq c \leq 2.000$
and $ 5.013 \leq C \leq 6.414$ are universal positive constants independent of
$m$, $n$ and $x$. Moreover, for any $m \geq 2$ and $n \geq 2$, $
E(\log\kappa_2(G_{m \times n})) < \log \frac{n}{|n-m|+1} + 2.258. $ A similar
pair of results for complex Gaussian random matrices is also established.

研究了实高斯随机矩阵和复高斯随机矩阵的条件数，得到了它们的概率界。