Approximate Message Passing with Nearest Neighbor Sparsity Pattern Learning
This work addresses signal reconstruction for applications where sparsity patterns are unknown, offering an incremental improvement over existing methods.
The paper tackles the problem of recovering clustered sparse signals without prior knowledge of the sparsity pattern by proposing AMP-NNSPL, an algorithm that learns the pattern adaptively using k-nearest neighbors and expectation maximization, resulting in improved reconstruction performance and computational efficiency as demonstrated on synthetic and real data.
We consider the problem of recovering clustered sparse signals with no prior knowledge of the sparsity pattern. Beyond simple sparsity, signals of interest often exhibits an underlying sparsity pattern which, if leveraged, can improve the reconstruction performance. However, the sparsity pattern is usually unknown a priori. Inspired by the idea of k-nearest neighbor (k-NN) algorithm, we propose an efficient algorithm termed approximate message passing with nearest neighbor sparsity pattern learning (AMP-NNSPL), which learns the sparsity pattern adaptively. AMP-NNSPL specifies a flexible spike and slab prior on the unknown signal and, after each AMP iteration, sets the sparse ratios as the average of the nearest neighbor estimates via expectation maximization (EM). Experimental results on both synthetic and real data demonstrate the superiority of our proposed algorithm both in terms of reconstruction performance and computational complexity.