Approximate Message Passing with Nearest Neighbor Sparsity Pattern Learning

• DOI: 10.48550/arxiv.1601.00543
• Publication Date: 2016-01-01
• Authors: Xiangming Meng; Sheng Wu; Linling Kuang; Defeng;  Huang; Jianhua Lu
• Keywords: Best bin first; Nearest-neighbor chain algorithm; Nearest neighbor graph

We consider the problem of recovering clustered sparse signals with no prior knowledge sparsity pattern. Beyond simple sparsity, interest often exhibits an underlying pattern which, if leveraged, can improve reconstruction performance. However, is usually unknown a priori. Inspired by idea k-nearest neighbor (k-NN) algorithm, we propose efficient algorithm termed approximate message passing nearest learning (AMP-NNSPL), which learns adaptively. AMP-NNSPL specifies flexible spike and slab on signal and, after each AMP iteration, sets ratios as average estimates via expectation maximization (EM). Experimental results both synthetic real data demonstrate superiority our proposed in terms performance computational complexity.