JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2017, Vol. 52 ›› Issue (9): 76-82.doi: 10.6040/j.issn.1671-9352.0.2017.192

Previous Articles     Next Articles

The iterative fraction thresholding algorithm in sparse information processing

ZHANG Qian, LI Hai-yang*   

  1. Department of Mathematics, Xian Polytechnic University, Xian 710048, Shaanxi, China
  • Received:2017-04-24 Online:2017-09-20 Published:2017-09-15

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.

Key words: shrinkage operator, proximal mapping, iterative thresholding algorithm, sparse information processing

CLC Number: 

  • O231
[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] SONG Q F, LIANG F M. High-dimensional variable selection with reciprocal l1-regularization[J]. Journal of the American Statistical Association, 2015, 110(512):1607-1620.
[4] 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.
[5] LOBO M, FAZEL M, BOYD S. Portfolio optimization with linear and fixed transaction costs[J]. Annals of Operations Research, 2006, 152(1):341-365.
[6] NATARAJAN B. Sparse approximate solutions to linear systems[J]. SIAM Journal on Computing, 1995, 24(2):227-234.
[7] CANDÈS E, TAO T. Decoding by linear programming[J]. IEEE Transactions on Information Theory, 2005, 51(12):4203-4215.
[8] 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.
[9] 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.
[10] DONOHO D L, ELAD M. Optimally sparse representation in general(nonorthogonal)dictionaries via l1 minimization[J]. Proceedings of the National Academy of Science of the United States of America, 2003, 100(5):2197-2202.
[11] DONOHO D L, HUO X M. Uncertainty principles and ideal atomic decomposition[J]. IEEE Transactions on Information Theory, 2001, 47(7):2845-2862.
[12] 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.
[13] GRIBONVAL R, NIELSEN M. Sparse decompositions in unions of bases[J]. IEEE Transactions on Information Theory, 2003, 49(12):3320-3325.
[14] MALLAT S, ZHANG Z. Matching pursuits with time-frequency dictionaries[J]. IEEE Transactions on Singnal Process, 1993, 41(12):3397-3415.
[15] TROPP J, NEEDELL D. CoSaMP: iterative signal recovery from incomplete and inaccurate samples[J]. Applied and Computational Harmonic Analysis, 2008, 26(3):301-321.
[16] ZHANG Y. Theory of compressive sensing via l1-minimization: a non-RIP analysis and extensions[J]. Journal of the Operations Research Society of China, 2013, 1(1):79-105.
[17] 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.
[18] DONOHO D L. De-noising by soft thresholding[J]. IEEE Transactions on Information Theory, 1995, 41(3):613-627.
[19] GOLDSTEIN T, OSHER S. The split bregman method for l1-regularized problems[J]. SIAM Journal on Imaging Sciences, 2009, 2(2):323-343.
[20] XU Z B, CHANG X Y, XU F M, et al. l1/2 regularization: a thresholding representation theory and a fast solver[J]. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(7):1013-1027.
[21] 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.
[22] ROCKAFELLAR R T, WETS R J B. Variational analysis[M]. Berlin: Springer-Verlag, 1998.
[23] 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.
[1] ZHANG Chun-yan, HAO Sheng-nan, FENG Li-chao. Stochastic suppression on explosive solutions of a class of nonlinear impulsive differential systems by noise [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(2): 29-36.
[2] WEI Li-Feng, CHEN Li. [J]. J4, 2009, 44(12): 1-5.
[3] ZHANG Jia-Cheng, TUN Bao-Wei. Mixed type guaranteed cost controller design for neutral systems with nonlinearity [J]. J4, 2009, 44(10): 67-74.
[4] . A new approach for finitetime stabilization for a class of nonlinear systems [J]. J4, 2009, 44(7): 55-61.
[5] YAN Peng, SHEN Yanjun, WANG Jianfeng. Stability analysis of a class of neutral type singular systems [J]. J4, 2009, 44(4): 66-71 .
[6] ZHANG Wei, JU Peijun.

[J]. J4, 2009, 44(1): 63-66 .
[7] LI Cui-cui,SHEN Yan-jun*,ZHU Lin . Finite time control of an uncertain linear singular system with a time-varying disturbance [J]. J4, 2007, 42(12): 104-109 .
[8] SUN Wei-wei,WANG Yu-zhen . Stability analysis for some classes of time-delay nonlinear Hamiltonian systems [J]. J4, 2007, 42(12): 1-09 .
[9] SUN Yan-yan and WU Zhen . Sufficient condition of one kind of indefinite LQ solvable problem under partial information [J]. J4, 2007, 42(3): 29-31 .
[10] ZHANG Wei,JU Pei-jun* . Robust resilient H∞ control for interval singular systems with time-varying delays [J]. J4, 2008, 43(4): 58-61 .
[11] MA Hong-ji,HOU Ting,XING Jian-min . Indefinite stochastic LQ problem with exponential stability degree constraint [J]. J4, 2008, 43(5): 58-62 .
Full text



No Suggested Reading articles found!