Signal Reconstruction by minimization of nonconvex penalty: Stable altorithm using nonconvexity control
DOI:
https://doi.org/10.51094/jxiv.364Keywords:
Nonconvex penatly, SCAD, MCP, Message PassingAbstract
In this paper, we introduce a signal recontruction method using nonconvex sparse penalties in compressed sensing. We introduce Smoothly Clipped Absolute Deviation (SCAD) and Minimax Concave Penalty (MCP). These penalties change their forms depending on regularization parameters called the nonconvexity parameter, and coincide with the l1 constraint in some limit. In this paper, we consider solving the problem of non-convex penalties minimization by an algorithm called the approximate message passing method. The corresponding theoretical analysis shows that the nonconvex penalty minimization method gives higher reconstruction performance than the l1-minimization method, and the smaller the nonconvexity parameter, the higher the performance. However, a problem arises when the approximate message passing method does not converge when the nonconvexity parameter becomes small. We identify a phenomenon that the approximate message passing method loses the region of attraction to a fixed point, and we partially solve this problem in convergence convergence by a method called nonconvexity control.
Conflicts of Interest Disclosure
There are no conflicts of interest related to this research.Downloads *Displays the aggregated results up to the previous day.
References
Agarwal, N., Allen-Zhu, Z., Bullins, B., Hazan, E. and Ma, T. (2016). Finding Approximate Local Minima for Nonconvex Optimization in Linear Time, arXiv preprint arXiv:1611.01146, 2016.
The Event Horizon Telescope Collaboration et al (2019). First M87 Event Horizon Telescope Results. I. The Shadow of the Supermassive Black Hole, The Astrophysical Journal Letters, 875, p. L1.
Bayati, M. and Montanari, A. (2011). The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing, IEEE Transaction on information theory, 57 (2), 764–785.
Bayati, M. and Montanari, A. (2012). The Lasso risk for Gaussian matrices, IEEE Transaction on information theory, 58 (4), 1997–2017.
Boche, H., Calderbank, R., Kutyniok, G. and Vyb ́ıral, J. (2015). Compressed Sensing and its Applications, Springer.
Cand ́es, E. J. (2008). The restricted isometry property and its implications for compressed sensing, Comptes Rendus Mathematique, 346, 589–592.
Cand ́es, E. J. and Tao, T. (2006). Decoding by linear programming, IEEE transactions on information theory, 52 (12), 5406–5425.
Chartrand, R. (2007). Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14, 707–710.
Chartrand, R. and Staneva, S. (2008). Restricted isometry properties and nonconvex compressive sensing, Inverse Problems, 24 (3), p. 035020.
Chartrand, R. and Yin, W. (2008). Iteratively reweighted algorithms for compressive sensing, IEEE International Conference on Acoustics, Speech and Signal Processing, 3869–3872, IEEE.
Chen, S. S., Donoho, D. L. and Saunders, M. A. (2001). Atomic Decomposition by Basis Pursuit, SIAM Review, 43 (1), 129–159.
De Almeida, J. and Thouless, D. J. (1978). Stability of the Sherrington-Kirkpatrick solution of a spin glass model, Journal of Physics A: Mathematical and General, 11 (5), p. 983.
Donoho, D. L. (2006a). Compressed sensing, IEEE Transactions on information theory, 52 (4), 1289–1306.
Donoho, D. L. (2006b). High-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to Dimension, Discrete & Computational Geometry, 35 (4), 617–652.
Donoho, D. L. and Tanner, J. (2009). Counting faces of randomly-projected polytopes when the projection radically lowers dimension, Journal of American Mathematical Society, 22, 1–53.
Donoho, D. L., Maleki, A. and Montanari, A. (2009a). Message-passing algorithms for compressed sensing, Proceedings of the National Academy of Sciences, 106 (45), 18914– 18919.
Donoho, D. L., Maleki, A. and Montanari, A. (2009b). Message-passing algorithms for compressed sensing, Proceedings of the National Academy of Sciences, 106 (45), 18914– 18919.
Elad, M. (2010). Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing, Springer.
Fan, J. and Li, R. (2001). Variable selection via nonconcave penalized likelihood and its oracle properties, Journal of the American statistical Association, 96 (456), 1348–1360.
Gerbelot, C., Abbara, A. and Krzakala, F. (2020). Asymptotic Errors for High- Dimensional Convex Penalized Linear Regression beyond Gaussian Matrices, Proceedings of Machine Learning Research, 33rd Annual Conference on Learning Theory, 1–32, MLR press.
Gribonval, R. and Nielsen, M. (2003). Sparse representation in unions of bases,DC Approximation Approach for l0-minimization in Compressed Sensing, IEEE Transaction on Information Theory, 49 (12), p. 3320.
Kabashima, Y. (2003). A CDMA multiuser detection algorithm on the basis of belief propagation, J Phys A: Math & Gen, 36, 11111–11121.
Kabashima, Y. and Saad, D. (1998). Belief propagation vs. TAP for decoding corrupted messages, EPL (Europhysics Letters), 44 (5), p. 668.
Kabashima, Y. and Uda, S. (2004). A BP-based algorithm for performing Bayesian inference in large perceptron-type networks, International Conference on Algorithmic Learning Theory, 479–493, Springer.
Kabashima, Y., Wadayama, T. and Tanaka, T. (2009). A typical reconstruction limit for compressed sensing based on l1-norm minimization, Journal of Statistical Mechanics: Theory and Experiment, 2009 (09), p. L09003.
Krzakala, F., M ́ezard, M., Sausset, F., Sun, Y. and Zdeborov ́a, L. (2012). Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices, Journal of Statistical Mechanics: Theory and Experiment, 2012 (08), p. P08009.
Lustig, M., Donoho, D. and Pauly, J. M. (2007). Sparse MRI: The Application of Compressed Sensing for Rapid MR Imaging, Magnetic Resonance in Medicine, 58, 1182– 1195.
MacKay, D. J. (1999). Good error-correcting codes based on very sparse matrices, IEEE transactions on Information Theory, 45 (2), 399–431.
Mezard, M. and Montanari, A. (2009). Information, physics, and computation, Oxford University Press.
M ́ezard, M., Parisi, G. and Virasoro, M. (1987). Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, 9, World Scientific Publishing Co Inc.
Montanari, A. and Bayati, M. (2011). The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing, IEEE Transaction on Information Theory, 57, p. 764–785.
Natarajan, B. K. (1995). Sparse approximate solutions to linear systems, SIAM journal on computing, 24 (2), 227–234.
Obuchi, T. and Sakata, A. (2019). Cross validation in sparse linear regression with piecewise continuous nonconvex penalties and its acceleration, J Phys A: Math & Theor, 52, p. 414003.
Rangan, S. (2011). Generalized approximate message passing for estimation with random linear mixing, Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on, 2168–2172, IEEE.
Sakata, A. (2018). Estimator of prediction error based on approximate message passing for penalized linear regression, Journal of Statistical Mechanics: Theory and Experiment, 2018 (6), p. 063404.
Sakata, A. and Obuchi, T. (2021). Perfect reconstruction of sparse signals with piecewise continuous nonconvex penalties and nonconvexity control, Journal of Statistical Mechanics: Theory and Experiment, 2021 (9), p.093401.
Sakata, A. and Xu, Y. (2018). Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis, Journal of Statistical Mechanics: Theory and Experiment, 2018 (3), p. 033404.
Schniter, P., Rangan, S. and Fletcher, A. K. (2017). Vector Approximate Message Passing, Information Theory Proceedings (ISIT), 2017 IEEE International Symposium on, 1588–1592, IEEE.
Takahashi, T. and Kabashima, Y. (2020). Macroscopic Analysis of Vector Approximate Message Passing in a Model Mismatch Setting, Information Theory Proceedings (ISIT), 2020 IEEE International Symposium on, 1403–1408, IEEE.
Thouless, D. J., Anderson, P. W. and Palmer, R. G. (1977). Solution of’solvable model of a spin glass’, Philosophical Magazine, 35 (3), 593–601.
Tropp, J. A. (2007). Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit, IEEE Transaction on Information Theory, 53 (12), 4655–4666.
Xu, Y., Kabashima, Y. and Zdeborov ́a, L. (2014). Bayesian signal reconstruction for 1-bit compressed sensing, Journal of Statistical Mechanics: Theory and Experiment, 2014 (11), p. P11015.
Zhang, C.-H. (2010). Nearly Unbiased Variable Selection Under Minimax Concave Penalty, The Annals of Statistics, 38 (2), 894–942.
Downloads
Posted
Submitted: 2023-04-13 03:57:41 UTC
Published: 2023-04-14 10:46:53 UTC
License
Copyright (c) 2023
Ayaka Sakata
Tomoyuki Obuchi
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
