arXiv:2207.03427

Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing

Namiko Matsumoto, Arya Mazumdar

제출 2022-07-07

원문 초록

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}/\epsilon\}$, where $k$ is the sparsity, $\epsilon$ 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}{\epsilon})$ 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.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2505.23869v5stat.ML공통 태그 compressed sensing공식 코드 · Papers with Code

Gibbs 무작위성-압축 명제

Gibbs randomness-compression proposition

손실 압축 과정과 연관된 측정 벡터 집합에 대한 Gibbs 엔트로피를 통해 무작위성과 압축을 연결하는 명제를 제안한다. 이 연결을 구축하는 과정에서, 반복적인 압축-학습 주기에서 압축을 탐색하는 수단으로 학습 과제의 성능을 사용한다. 이는 열역학적 효율을 탐색 수단으로 사용하는 통계역학적 관점에서의 반복적 coarse-graining으로 볼 수 있다. 압축률의 매우 작은 감소와 성능 사이의 공단조(comonotonic) 관계를 통해 이 연결을 공식화한다. 기준선 모델로 세 가지 서로 다른 모델 압축 과정을 사용하여, 심층 학습의 정형적인 비전 과제에서 이 명제의 타당성을 입증한다. 다음의 단순한 것부터 복잡한 것까지의 모델 압축 접근법을 사용한다: (1) 무작위 가지치기, (2) 크기(magnitude) 가지치기, (3) 이중 방식의 압축 센싱(compressed sensing)을 활용하는 이중 tomographic 압축을 이용한 보다 복잡한 압축으로, 이는 새로운 방법으로 소개된다. 심층 학습 네트워크의 남은 가중치를 측정 벡터로 사용하여 Gibbs 엔트로피를 측정한다. 성능으로 탐색한 압축과 학습된 모델에 대한 엔트로피 측정으로부터 얻은 무작위성 사이에 본질적으로 계산 가능한 연결이 존재한다는 개념을 보여준다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.