Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing
Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing
复制标题
DOI：
10.1109/focs54457.2022.00082
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Namiko Matsumoto;A. Mazumdar
中科院分区：
文献类型：
--
作者：
Namiko Matsumoto;A. Mazumdar
压缩感知是一种非常成功的依赖于线性运算的高维信号采集和恢复技术。然而，在存储或处理信号之前，必须对信号的实际测量进行量化。1(1)比特压缩感知是压缩感知的高度量化版本，其中信号的每个线性测量被减少到只有一个比特：测量的符号。一旦收集到足够的测量数据，1比特压缩感知中的恢复问题旨在尽可能准确地找到原始信号。恢复问题与学习理论中传统的“半空间学习”问题有关。对于稀疏向量的恢复，一种流行的基于一位测量的重建方法是二进制迭代硬阈值(BIHT)算法。该算法是一种简单的投影次梯度下降法，尽管问题是非凸性的，但已知的经验是收敛得很好。BIHT的收敛性质在理论上是不合理的，除非有过多的测量(即测量的数量大于$max k^{10}，24^{48}，k^3.5}/epsilon$，其中k是稀疏性，$epsilon$表示逼近误差，甚至这个表达式隐藏了其他因素)。在这篇文章中，我们证明了BIHT估计收敛到原始信号时，只需要${\tilde{O}\Left(\frac{k}{\epsilon}\Right)$。注意，这种对k和$\epsilon$的依赖对于1比特压缩感测中的任何恢复方法都是最优的。有了这个结果，就我们所知，BIHT算法是唯一实用和有效的(多项式时间)算法，它在所有参数(k和$epsilon$)中都需要最优的测量值数量。这也是在适当的结构条件下，梯度下降算法收敛到非凸问题的正确解的一个例子。
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 them. 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 one-bit measurements is the binary iterative hard thresholding (BIHT) algorithm. The algorithm is a simple projected subgradient 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}/\epsilon\}$, where k is the sparsity and $\epsilon$ denotes the approximation error, and even this expression hides other factors). In this paper we show that the BIHT estimates converge to the original signal with only ${\tilde{O}}\left(\frac{k}{\epsilon}\right)$ measurements. Note that, this dependence on k and $\epsilon$ 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 $\epsilon$). This is also an example of a gradient descent algorithm converging to the correct solution for a nonconvex problem, under suitable structural conditions.