Discreteness-Aware Approximate Message Passing for Discrete-Valued Vector Reconstruction

作     者：Hayakawa, Ryo Hayashi, Kazunori 

作者机构：Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan Osaka City Univ Grad Sch Engn Osaka 5588585 Japan 

出 版 物：《IEEE TRANSACTIONS ON SIGNAL PROCESSING》 (IEEE信号处理汇刊)

年 卷 期：2018年第66卷第24期

页      面：6443-6457页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 

基　　金：Ministry of Education, Culture, Sports, Science and Technology of Japan [15K06064, 15H02252, 18K04148, 18H03765] Japan Society for the Promotion of Science [17J07055] Grants-in-Aid for Scientific Research [15H02252, 18H03765, 18K04148, 15K06064, 17J07055] Funding Source: KAKEN 

主　　题：Discrete-valued vector reconstruction sum-of-absolute-value optimization approximate message passing state evolution 

摘      要：This paper considers the reconstruction of a discrete-valued random vector from possibly underdetermined linear measurements using sum-of-absolute-value (SOAV) optimization. The proposed algorithm, referred to as discreteness-aware approximate message passing (DAMP), is based on the idea of approximate message passing (AMP), which has been originally proposed for compressed sensing. The DAMP algorithm has low computational complexity and its performance in the large system limit can he predicted analytically via state evolution framework, where we provide a condition for the exact reconstruction with DAMP in the noise-free case. From the analysis, we also propose a method to determine the parameters of the SOAV optimization. Moreover, based on the state evolution, we provide Bayes optimal DAMP, which has the minimum mean-square-error at each iteration of the algorithm. Simulation results show that the DAMP algorithms can reconstruct the discrete-valued vector from underdetermined linear measurements and the empirical performance agrees with our theoretical results in large-scale systems. When the problem size is not large enough, the SOAV optimization with the proposed parameters can achieve better performance than the DAMP algorithms for high signal-to-noise ratio.