Direct and Converse Theorems in Estimating Signals with Sublinear Sparsity
This provides theoretical guarantees for denoisers in message-passing algorithms, addressing a fundamental issue in signal processing for sublinear sparsity, but it is incremental as it builds on existing Bayesian estimators.
The paper tackles the problem of estimating signals with sublinear sparsity over an additive white Gaussian noise channel, proving that the maximum likelihood estimator achieves vanishing square error under low noise, while all estimators fail under high noise, with thresholds coinciding for constant amplitude signals.
This paper addresses the estimation of signals with sublinear sparsity sent over the additive white Gaussian noise channel. This fundamental problem arises in designing denoisers used in message-passing algorithms for sublinear sparsity. The main results are direct and converse theorems in the sublinear sparsity limit, where the signal sparsity grows sublinearly in the signal dimension as the signal dimension tends to infinity. As a direct theorem, the maximum likelihood estimator is proved to achieve vanishing square error in the sublinear sparsity limit if the noise variance is smaller than a threshold. As a converse theorem, all estimators cannot achieve square errors smaller than the signal power under a mild condition if the noise variance is larger than another threshold. In particular, the two thresholds coincide with each other when non-zero signals have constant amplitude. These results imply the asymptotic optimality of an existing separable Bayesian estimator used in approximate message-passing for sublinear sparsity.