We characterize the measurement complexity of compressed sensing of signals
drawn from a known prior distribution, even when the support of the prior is
the entire space (rather than, say, sparse vectors). We show for Gaussian
measurements and \emph{any} prior distribution on the signal, that the
posterior sampling estimator achieves near-optimal recovery guarantees.
Moreover, this result is robust to model mismatch, as long as the distribution
estimate (e.g., from an invertible generative model) is close to the true
distribution in Wasserstein distance. We implement the posterior sampling
estimator for deep generative priors using Langevin dynamics, and empirically
find that it produces accurate estimates with more diversity than MAP.

本研究研究了来自已知先验分布的信号的压缩感知的测量复杂性，即使先验的支撑是整个空间（而不是稀疏向量）。对于高斯测量和信号上的任何先验分布，我们展示了后验抽样估计器可以实现近乎最优的恢复保证，在模型不匹配的情况下，只要分布估计（例如，从可逆生成模型中）与 Wasserstein 距离中的真实分布接近。我们使用 Langevin 动力学为深度生成先验实现了后验抽样估计器，并实验性地发现，它产生的准确估计具有比 MAP 更多的多样性。

后验采样实例最优压缩感知

Instance-Optimal Compressed Sensing via Posterior Sampling

The problem central to sparse recovery and compressive sensing is that of
stable sparse recovery: we want a distribution of matrices A in R^{m\times n}
such that, for any x \in R^n and with probability at least 2/3 over A, there is
an algorithm to recover x* from Ax with
||x* - x||_p <= C min_{k-sparse x'} ||x - x'||_p for some constant C > 1 and
norm p. The measurement complexity of this problem is well understood for
constant C > 1. However, in a variety of applications it is important to obtain
C = 1 + eps for a small eps > 0, and this complexity is not well understood. We
resolve the dependence on eps in the number of measurements required of a
k-sparse recovery algorithm, up to polylogarithmic factors for the central
cases of p = 1 and p = 2. Namely, we give new algorithms and lower bounds that
show the number of measurements required is (1/eps^{p/2})k polylog(n). For p =
2, our bound of (1/eps) k log(n/k) is tight up to constant factors. We also
give matching bounds when the output is required to be k-sparse, in which case
we achieve (1/eps^p) k polylog(n). This shows the distinction between the
complexity of sparse and non-sparse outputs is fundamental.

该论文主要研究了稀疏恢复和压缩感知问题中的稀疏恢复算法及其测量复杂度，通过新的算法和下界证明，解决了在多种应用中需要小的常量 C > 1 的问题，同时还讨论了输出是否稀疏的复杂度区别。