1Spike-and-Slab Approximate Message-Passing for High-Dimensional Piecewise-Constant Recovery

Abstract—One of the challenges in Big Data is efficient han-dling of high-dimensional data or signals. This paper proposes a novel AMP algorithm for solving high-dimensional linear systems Y = HX +W ∈ RM which has a piecewise-constant solution X ∈ RN, under a compressed sensing framework (M ≤ N). We refer to the proposed AMP as ssAMP. This ssAMP algorithm is derived from the classical message-passing rule over a bipartite graph which includes spike-and-slab po-tential functions to encourage the piecewise-constant nature of X. The ssAMP iteration includes a novel scalarwise denoiser satisfying the Lipschitz continuity, generating an approximate MMSE estimate of the signal. The Lipschitz continuity of our denoiser enables the ssAMP to use the state evolution framework, given by the works [16],[19], for MSE prediction. In addition, we empirically show that ssAMP has better phase transition characteristic than TV-AMP [22] and GrAMPA [26] which are the existing AMPs for piecewise-constant recovery. We also discuss computational efficiency, empirically showing that ssAMP has computational advantage over the other recent algorithms under a high-dimensional setting. Index Terms—Compressed sensing, piecewise-constant signals, approximate message-passing (AMP), TV-AMP, total variation denoising I