|
|
- 2017
稀疏信息处理中的迭代分式阈值算法
|
Abstract:
摘要： 在稀疏信息处理中, l0范数优化问题通常转化为l1范数优化问题来求解。 但l1 范数优化问题存在一些不足。 为寻找一种更有效的求稀疏解的算法, 首先构造一个新的收缩算子, 其次证明该收缩算子是某非凸函数的邻近算子。 然后用该非凸函数替代l0-范数, 对新的优化问题用向前-向后分裂方法得到对应的迭代阈值算法-迭代分式阈值算法(IFTA)。 仿真实验表明该算法(IFTA)在稀疏信号重构和高维变量选择中均有良好的表现。
Abstract: In sparse information processing, l0 minimization is often relaxed to l1 minimization to find sparse solutions. However, l1 minimization has some deficiencies. The paper aims to find a more effective algorithm to find the sparse solutions. At first, a new shrinkage operator was constructed. Secondly, this shrinkage operator was proved to be the proximal mapping of some non-convex function. Then, a new iterative thresholding algorithm, iterative fraction thresholding algorithm(IFTA), was given by applying forward-backward splitting to the new optimization problem when l0-norm is replaced with this non-convex function. At last, the simulations indicate that the iterative fraction thresholding algorithm(IFTA)performs well in sparse signal reconstruction and high-dimensional variable selection
| [1] | BLOMGREN P, CHAN T F. Color TV: total variation methods for restoration of vector-valued images[J]. IEEE Transactions on Image Processing, 1998, 7(3):304-309. |
| [2] | DONOHO D L, STARK P B. Uncertainty principles and signal recovery[J]. SIAM Journal on Applied Mathematics, 1989, 49(3):906-931. |
| [3] | NATARAJAN B. Sparse approximate solutions to linear systems[J]. SIAM Journal on Computing, 1995, 24(2):227-234. |
| [4] | DONOHO D L, HUO X M. Uncertainty principles and ideal atomic decomposition[J]. IEEE Transactions on Information Theory, 2001, 47(7):2845-2862. |
| [5] | CANDèS E, TAO T. Near optimal signal recovery from random projections: universal encoding strateies[J]. IEEE Transactions on Information Theory, 2006, 52(12):5406-5425. |
| [6] | CANDèS E, TAO T. Decoding by linear programming[J]. IEEE Transactions on Information Theory, 2005, 51(12):4203-4215. |
| [7] | LI Y, CICHOCKI A, AMARI S. Sparse component analysis for blind source separation with less sensors than sources[C] // Processdings of 4th International Symposium on Independent Component Analysis and Blind Signal Separation. Japan: ICA, 2003: 89-94. |
| [8] | ZHANG Y. Theory of compressive sensing via <i>l</i><sub>1</sub>-minimization: a non-RIP analysis and extensions[J]. Journal of the Operations Research Society of China, 2013, 1(1):79-105. |
| [9] | VORONIN S, CHARTRAND R. A new generalized thresholding algorithm for inverse problems with sparsity constraints[C] // Proceedings of the 38th IEEE International Conference on Acoustics, Speech and Signal Processing(ICASSP). Canada: IEEE, 2013:1636-1640. |
| [10] | CANDèS E, TAO T. The dantzig selector: statistical estimation when p is much larger than n[J]. The Annals of Statistics, 2007, 35(6):2313-2351. |
| [11] | CANDèS E, ROMERG J, TAO T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2):489-509. |
| [12] | GOLDSTEIN T, OSHER S. The split bregman method for <i>l</i><sub>1</sub>-regularized problems[J]. SIAM Journal on Imaging Sciences, 2009, 2(2):323-343. |
| [13] | XU Z B, CHANG X Y, XU F M, et al. l<sub>1/2</sub> regularization: a thresholding representation theory and a fast solver[J]. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(7):1013-1027. |
| [14] | ROCKAFELLAR R T, WETS R J B. Variational analysis[M]. Berlin: Springer-Verlag, 1998. |
| [15] | DONOHO D L, ELAD M. Optimally sparse representation in general(nonorthogonal)dictionaries via <i>l</i><sup>1</sup> minimization[J]. Proceedings of the National Academy of Science of the United States of America, 2003, 100(5):2197-2202. |
| [16] | GRIBONVAL R, NIELSEN M. Sparse decompositions in unions of bases[J]. IEEE Transactions on Information Theory, 2003, 49(12):3320-3325. |
| [17] | MALLAT S, ZHANG Z. Matching pursuits with time-frequency dictionaries[J]. IEEE Transactions on Singnal Process, 1993, 41(12):3397-3415. |
| [18] | DONOHO D L. De-noising by soft thresholding[J]. IEEE Transactions on Information Theory, 1995, 41(3):613-627. |
| [19] | SONG Q F, LIANG F M. High-dimensional variable selection with reciprocal <i>l</i><sub>1</sub>-regularization[J]. Journal of the American Statistical Association, 2015, 110(512):1607-1620. |
| [20] | LOBO M, FAZEL M, BOYD S. Portfolio optimization with linear and fixed transaction costs[J]. Annals of Operations Research, 2006, 152(1):341-365. |
| [21] | COHEN A, DAHMEN W, DEVORE R. Compressed sensing and best k-term approximation[J]. Journal of The American Mathematical Society, 2009, 22(1):211-231. |
| [22] | CANDèS E, ROMBERG J, TAO T. Stable signal recovery from incomplete and inaccurate measurements[J]. Communications on Pure Applied Mathematics, 2006, 59(8):1207-1223. |
| [23] | TROPP J, NEEDELL D. CoSaMP: iterative signal recovery from incomplete and inaccurate samples[J]. Applied and Computational Harmonic Analysis, 2008, 26(3):301-321. |
