非凸スパース制約最小化による信号復元: 非凸性制御によるアルゴリズム軌道の安定化

坂田, 綾香; 小渕, 智之

doi:10.51094/jxiv.364

##article.authors##

坂田, 綾香統計数理研究所数理・推論研究系 https://orcid.org/0000-0003-1660-0222
小渕, 智之京都大学大学院情報科学研究科

DOI:

https://doi.org/10.51094/jxiv.364

キーワード:

MCP、確率伝搬法、非凸スパース制約、 SCAD

抄録

本稿では，圧縮センシングにおける非凸スパース制約を用いた信号復元法について紹介する. ここでは Smoothly Clipped Absolute Deviation(SCAD)，Minimax Concave Penalty(MCP) と呼ばれる非凸スパース制約の最小化法を扱う.これらの制約は，非凸性パラメータと呼ぶ正則化パラメータにより形が変化し，ある極限では l1 制約と一致する.本稿では，近似確率伝搬法と呼ばれるアルゴリズムにより非凸制約最小化問題を解くことを考える.対応する理論解析から，非凸制約最小化法は l1 制約最小化法よりも高い復元性能を与え，非凸性パラメータが小さいほどその性能が高くなることが示される.しかし，非凸性パラメータが小さくなると近似確率伝搬法が収束しない問題が生じる.この問題の背景に，近似確率伝搬法の固定点への引き込み領域が消失するという現象があることを示し，この現象に由来する収束性の悪さを非凸性制御と呼ぶ方法により部分的に解決する.

利益相反に関する開示

本研究に関して利益相反に該当する事項はない

ダウンロード *前日までの集計結果を表示します

ダウンロード実績データは、公開の翌日以降に作成されます。

引用文献

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.