论文标题
改善通用一位压缩感应中的支持恢复
Improved Support Recovery in Universal One-bit Compressed Sensing
论文作者
论文摘要
一位压缩传感（1BC）是一种极为量化的信号采集方法，在过去十年中已经进行了严格的研究。在1BC中，将高维信号的线性样品量化为每个样品的仅一个位（测量的符号）。假设原始信号向量稀疏，现有的1BC中的现有结果旨在找到向量的支持，或近似允许误差的信号。本文的重点是支持恢复，这通常也在计算上促进了近似信号恢复。 1BCS的{\ em Universal}测量矩阵是指适合所有稀疏信号的一组测量值。有了普遍性，众所周知，$ \tildeθ（k^2）$ 1BCS的测量是必要的，足以支撑恢复（其中$ k $表示稀疏）。为了改善对稀疏性从二次到线性的依赖性，在这项工作中，我们提出了近似支持恢复（允许$ε> 0 $错误的错误比例）和超集恢复（允许$ε$ $ afters $ε$ afteral forts prientives）。我们表明，使用$ \ tilde {o}（k/ε）$测量是可能的第一种恢复类型，而使用$ \ tilde {o}（\ max \ max \ {k/ε，k^{3/2}} \}）$ \ tilde {o}可能更具挑战性的恢复类型，更具挑战性。我们还表明，在这两种情况下，对于通用恢复都是必需的$ω（K/ε）$测量值。 如果我们考虑在有限的信号类别（例如理性信号或具有有限动态范围的信号）内的通用恢复，则可以改善结果。在这两种情况下，只有$ \ tilde {o}（k/ε）$测量都可以进行超集恢复。本文还提供了有关通用但近似支持恢复的其他结果。我们所有的主要恢复算法都是简单且多项式时间。
One-bit compressed sensing (1bCS) is an extremely quantized signal acquisition method that has been proposed and studied rigorously in the past decade. In 1bCS, linear samples of a high dimensional signal are quantized to only one bit per sample (sign of the measurement). Assuming the original signal vector to be sparse, existing results in 1bCS either aim to find the support of the vector, or approximate the signal allowing a small error. The focus of this paper is support recovery, which often also computationally facilitate approximate signal recovery. A {\em universal} measurement matrix for 1bCS refers to one set of measurements that work for all sparse signals. With universality, it is known that $\tildeΘ(k^2)$ 1bCS measurements are necessary and sufficient for support recovery (where $k$ denotes the sparsity). To improve the dependence on sparsity from quadratic to linear, in this work we propose approximate support recovery (allowing $ε>0$ proportion of errors), and superset recovery (allowing $ε$ proportion of false positives). We show that the first type of recovery is possible with $\tilde{O}(k/ε)$ measurements, while the later type of recovery, more challenging, is possible with $\tilde{O}(\max\{k/ε,k^{3/2}\})$ measurements. We also show that in both cases $Ω(k/ε)$ measurements would be necessary for universal recovery. Improved results are possible if we consider universal recovery within a restricted class of signals, such as rational signals, or signals with bounded dynamic range. In both cases superset recovery is possible with only $\tilde{O}(k/ε)$ measurements. Other results on universal but approximate support recovery are also provided in this paper. All of our main recovery algorithms are simple and polynomial-time.
