Embedded Files
* Related publications
[1-a] Jaewook Kang, Hyoyoung Jung, Heung-No Lee, and Kiseon Kim, "Spike-and-Slab approximate message-passing for high-dimensional piecewise-constant recovery," available at arXiv:1408.3930, 2014 (preprint PDF)
[1-b] Jaewook Kang, Hyoyoung Jung, Heung-No Lee, and Kiseon Kim, "One-dimensional Piecewise-Constant Signal Recovery via Spike-and-Slab Approximate Message-Passing," to appear in proc. of the 48th Asilomar Conference (Asilomar, CA), Nov. 2014. (IEEE Xplore)
* Overview
In this work, we revisit the 1-D piecewise-constant recovery problem with the Bayesian Approximate message-passing (AMP) framework, proposing a novel and fast AMP algorithm. This proposed AMP is referred to as Spike-and-Slab Approximate Message-Passing (ssAMP-1D).
The advantages of the proposed ssAMP-1D is mainly from the following statements:
-------------------------------------------------------------------------------------------------------------------------------------------
1) The ssAMP-1D recovery is characterized by phase transition (PT) competitive to the state-of-the-art performance.
2) ssAMP-1D provides a faster recovery with O(MN) periteration cost and rapid convergence compared to the other recent solvers.
3) ssAMP-1D is fully scalarable; therefore, it can be easily parallelizable and/or decentralized for large-scale problems.
-------------------------------------------------------------------------------------------------------------------------------------------
* Some experimental results
1) Noiseless phase transition
We provide empirical comparison of noiseless PT performance (
), for two types of the finite differences (FDs): Gaussian FDs and Ternary FDs. For each empirical PT curve, we fixed the length to
, and considered a grid where we uniformly divided the range as the x-axis and the range
as the y-axis with the stepsize 0.025. These PT curves are connection of experimental points having 0.5 success rate of the signal recovery, where the recovery success is declared when NMSE has
. For all the solvers, we set the number of maximum iterations to t=2000, and the iteration stopping tolerance was very tightly set to
hence, the PT curves are supposed to represent algorithm performance after convergence. In addition, we emphasize that in the configuration of ssAMP 1D, the parameter
should be appropriately tuned according to types of the FDs. For the Gaussian FDs (the ternary FDs), we configure ssAMP-1D with
which is 3 times (1.5 times) larger than the one used in the signal generation.
2) NMSE convergence over iteration
The main advantage in ssAMP-1D is from its swift convergence. In order to validate such fast nature of ssAMP-1D, we measured NMSE over iterations for four different cases of
:
3) Average CPU runtime
This figure depicts the average CPU runtime over the signal length N, where we set a target MSE for fairness since some algorithms may run longer but give a better MSE without any stopping criterion. Namely, in this experiment, we made all the algorithms to stop their iterations when reaching the target MSE
(-30 dB of NMSE). In addition, we loosely set the maximum iterations to t=2000 based on the result of the "NMSE convergence over iteration".
* Support
This work was supported in part by National Research Foundation funded by Ministry of Science, ICT and Future Planning of Korea (the Grant 2009-00422), and in part by Ministry of Oceans and Fisheries of Korea under the project titled ’Domestic products development of marine survey and ocean exploration equipment.
* Source codes download
1) ssAMP-1D [1], Chambolle-Pock [4], TV-AMP [3] (Written by Jaewook Kang,source codes)
*ssAMP-1D Copyright (C) 2014 Jaewook Kang, Hyoyoung Jung, Heung-No Lee, Kiseon Kim
- Feedback for the source codes is very welcome. Please send your comment to jwkkang(at)gist.ac.kr.
Version 1 (2014 Aug)
-Initial version of ssAMP-1D algorithm packages
Version 2 (2015 Jan)
- Modifying signal model
- Re-configuring of GrAMPA and ssAMP-1D
- Re-setting the experiment setup for phase transition and CPU runtime experiment
2) EFLA [2] (obtained from http://www.public.asu.edu/~jye02/Software/SLEP/)
3) GrAMPA [5](obtained from http://www2.ece.ohio-state.edu/~schniter/GrAMPA/download.html )
* Selected References
[2] J. Liu, L. Yuan, and J. Ye. “An efficient algorithm for a class of fused lasso problems,” proc of ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2010.
[3] D. L. Donoho, I. Johnstone, and A. Montanari, “Accurate prediction of phase transitions in compressed sensing via a connection to minimax denoising, ” IEEE Trans. Inform. Theory, vol. 59, no. 6, pp. 3396-3433, June 2013.
[4] A. Chambolle, T. Pock, “A first-order primal-dual algorithm for convex problems with applications to imaging,” J. Math. Imag. Vis., vol. 40, pp. 120-145, May 2011
[5] M. Borgerding and P. Schiniter, “Generalized approximate message passing for the cosparse analysis model,” avabilable at ArXiv:1312.3968v1 [cs.IT], Dec. 2013.
1 x 1
Page updated
Google Sites
Report abuse