论文标题
二元迭代硬阈值收敛，最佳测量数量用于1位压缩感应
Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing
论文作者
论文摘要
压缩传感一直是依赖线性操作的非常成功的高维信号采集和恢复技术。但是，在存储或处理之前，必须对信号的实际测量进行量化。 1（一个） - 位压缩传感是压缩传感的大量量化版本，在其中，信号的每个线性测量都降低到一个位：测量的符号。一旦收集了足够的测量，1位压缩感应中的恢复问题旨在以尽可能准确的方式找到原始信号。恢复问题与学习理论中传统的“半空间学习”问题有关。 为了恢复稀疏向量，从1位测量值中的流行重建方法是二元迭代硬阈值（BIHT）算法。该算法是一种简单的投影次级下降方法，尽管该问题的概念性不佳，但已知在经验上却很好地收敛。 BIHT的收敛属性在理论上并不合理，除了大量的测量值（即，许多大于$ \ axmax \ {k^{10}，24^{48}，k^{3.5}/ε\} $的测量值大于$ \ max \ {k^{10}，24^{48}，$ k $ k $ and $ k $ spars $ denot and $ denot and $εdem，因素）。在本文中，我们表明，BIHT算法仅使用$ \ tilde {o}（\ frac {k}ε）$测量收敛。请注意，这种依赖性对$ k $和$ε$对于1位压缩感测的任何恢复方法都是最佳的。据我们所知，BIHT是唯一需要所有参数（$ k $ and $ k $和$ε$）中最佳测量数量的实用和高效（多项式时间）算法。这也是在适当的结构条件下，梯度下降算法收敛到正确解决方案的梯度下降算法。
Compressed sensing has been a very successful high-dimensional signal acquisition and recovery technique that relies on linear operations. However, the actual measurements of signals have to be quantized before storing or processing. 1(One)-bit compressed sensing is a heavily quantized version of compressed sensing, where each linear measurement of a signal is reduced to just one bit: the sign of the measurement. Once enough of such measurements are collected, the recovery problem in 1-bit compressed sensing aims to find the original signal with as much accuracy as possible. The recovery problem is related to the traditional "halfspace-learning" problem in learning theory. For recovery of sparse vectors, a popular reconstruction method from 1-bit measurements is the binary iterative hard thresholding (BIHT) algorithm. The algorithm is a simple projected sub-gradient descent method, and is known to converge well empirically, despite the nonconvexity of the problem. The convergence property of BIHT was not theoretically justified, except with an exorbitantly large number of measurements (i.e., a number of measurement greater than $\max\{k^{10}, 24^{48}, k^{3.5}/ε\}$, where $k$ is the sparsity, $ε$ denotes the approximation error, and even this expression hides other factors). In this paper we show that the BIHT algorithm converges with only $\tilde{O}(\frac{k}ε)$ measurements. Note that, this dependence on $k$ and $ε$ is optimal for any recovery method in 1-bit compressed sensing. With this result, to the best of our knowledge, BIHT is the only practical and efficient (polynomial time) algorithm that requires the optimal number of measurements in all parameters (both $k$ and $ε$). This is also an example of a gradient descent algorithm converging to the correct solution for a nonconvex problem, under suitable structural conditions.
