PIECEWISE SPARSE RECOVERY VIA PIECEWISE INVERSE SCALE SPACE ALGORITHM WITH DELETION RULE

doi:10.4208/jcm.1810-m2017-0233

Journal of Computational Mathematics ›› 2020, Vol. 38 ›› Issue (2): 375-394.DOI: 10.4208/jcm.1810-m2017-0233

PIECEWISE SPARSE RECOVERY VIA PIECEWISE INVERSE SCALE SPACE ALGORITHM WITH DELETION RULE

Yijun Zhong, Chongjun Li

School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China

Received:2017-06-26 Revised:2018-03-07 Online:2020-03-15 Published:2020-03-15
Supported by:
This work was supported by the National Natural Science Foundation of China (Nos. 11871137, 11471066, 11290143), the Fundamental Research of Civil Aircraft (No. MJ-F-2012-04), the Fundamental Research Funds for the Central Universities, and the Liaoning BaiQianWan Talents Program. The authors are grateful to Prof. Michael Moeller for providing a number of valuable comments and explanations for a comprehensive understanding of the Inverse Scale Space algorithm.

PDF ( 7 ) Cited

Yijun Zhong, Chongjun Li. PIECEWISE SPARSE RECOVERY VIA PIECEWISE INVERSE SCALE SPACE ALGORITHM WITH DELETION RULE[J]. Journal of Computational Mathematics, 2020, 38(2): 375-394.

In some applications, there are signals with piecewise structure to be recovered. In this paper, we propose a piecewise_ISS (P_ISS) method which aims to preserve the piecewise sparse structure (or the small-scaled entries) of piecewise signals. In order to avoid selecting redundant false small-scaled elements, we also implement the piecewise_ISS algorithm in parallel and distributed manners equipped with a deletion rule. Numerical experiments indicate that compared with aISS, the P ISS algorithm is more effective and robust for piecewise sparse recovery.

Key words: Inverse scale space, Piecewise sparse, Sparse recovery, Small-scaled entries

CLC Number:

90C25
94A12

[1] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci, 2:1(2009), 183-202.

[2] M. Burger, S. Osher, J. Xu, G. Gilboa, Nonlinear inverse scale space methods for image restoration, in International Conference on Variational, Geometric, and Level Set Methods in Computer Vision, Springer, 2005, 25-36.

[3] M. Burger, G. Gilboa, S. Osher, et al, Nonlinear inverse scale space methods, Commun. Math. Sci., 4:1(2006), 179-212.

[4] M. Burger, K. Frick, S. Osher, et al, Inverse total variation flow, SIAM Multiscale Modeling & Simulation, 6:2(2007), 366-395.

[5] M. Burger, E. Resmerita, L. He, Error Estimation for Bregman iterations and inverse scale space methods in image restoration, Computing, 81:2-3(2007), 109-135.

[6] M. Burger, A note on sparse reconstruction methods, J. Phys. Conf. Ser., 124:1(2008), 012002.

[7] M. Burger, M. Möller, M. Benning, et al, An adaptive inverse scale space method for compressed sensing, Math. Comput., 82:281(2013), 269-299.

[8] J.F. Cai, S. Osher, and Z. Shen, Convergence of the linearized Bregman iteration for l¹ norm minimization, Math. Comp, 78:268(2009), 2127-2136.

[9] J.F. Cai, S. Osher, and Z. Shen, Linearized Bregman iterations for compressed sensing, Math. Comp, 78:267(2009), 1515-1536.

[10] G. Chen, M. Teboulle, Convergence analysis of a proximal-like minimization algorithm using bregman functions, SIAM J. Optimiz., 3:3(1993), 538-543.

[11] D.L. Donoho, Y. Tsaig, I. Drori, et al. Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit, IEEE Trans. Inform. Theory, 58:2(2012) 1094-1121.

[12] I. Ekeland,R. Man, Convex Analysis and Variational Problems, SIAM, 1999.

[13] M. Elad, Sparse and Redundant Representations:From Theory to Applications in Signal and Image Processing, Springer New York, 2010.

[14] Y.C. Eldar, M, Mishali, Block sparsity and sampling over a union of subspaces, in International Conference on Digital Signal Processing IEEE, 2009, 1-8.

[15] Y.C. Eldar, P. Kuppinger, H. Bolcskei, Block-sparse signals:uncertainty relations and efficient recovery, IEEE Trans. Signal Proces., 58:6(2010), 3042-3054.

[16] E. Elhamifar, R. Vidal, Block-sparse recovery via convex optimization, IEEE Trans.Signal Proces., 60:8(2011), 4094-4107.

[17] E.T. Hale, W. Yin, and Y. Zhang, Fixed-point continuation for l¹-minimization:methodology and convergence, SIAM J. Optim, 19:3(2008), 1107-1130.

[18] Y.X. Hao, C.J. Li and R.H. Wang, Sparse approximate solution of fitting surface to scattered points by MLASSO model, Sci. China Math., 7(2018), 1-18.

[19] J.B. Hiriart-Urruty, C. Lem, Fundamentals of Convex Analysis, Grundlehren Text Editions, 1993.

[20] J.L. Starck, M. Elad and D.L. Donoho, Image decomposition via the combination of sparse representations and a variational approach, IEEE Trans. image proces., 14:10(2005), 1570-1582.

[21] M. Möller, Multiscale Methods For (Generalized) Sparse Recovery And Applications In High Dimensional Imaging, PhD thesis, Universität Münster, 2012.

[22] D. Needell and J.A. Tropp, CoSaMP:Iterative Signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. A., 26:3(2008), 301-321.

[23] S. Osher, R. Feng, J. Xiong, et al., Sparse recovery via differential inclusions, Appl. Comput. Harmon. A., 41:2(2016), 436-469.

[24] S. Osher, Y. Mao, B. Dong, and W. Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Commun. Math. Sci, 8:1(2010), 93-111.

[25] S. Osher, W. Yin, D. Goldfarb, et al., An Iterative Regularization Method for Total VariationBased Image Restoration, SIAM Journal on Multiscale Modeling & Simulation, 4:2(2005), 460-489.

[26] L. Peotta and P. Vandergheynst, Matching pursuit with block incoherent dictionaries, IEEE Trans. Signal Proces., 55:9(2007), 4549-4557.

[27] Z.W. Wen, W. Yin, D. Goldfarb, et al., A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation, SIAM J. Sci. Comput., 32:4(2010), 1832-1857.

[28] Y. Yao, L. Rosasco and A. Caponnetto, On early stopping in gradient descent learning, Constr. Approx., 26:2(2007), 289-315.

[29] W. Yin, S. Osher, D. Goldfarb, and J. Darbon, Bregman iterative algorithms for l¹-minimization with applications to compressed sensing, SIAM J. Imaging Sci, 1:1(2008), 143-168.

[30] X. Zhang, M. Burger, and S. Osher, A unified primal-dual algorithm framework based on Bregman iteration, J. Sci. Comput, 46:1(2011), 20-46.

[1]	Didi Lv, Xiaoqun Zhang. A GREEDY ALGORITHM FOR SPARSE PRECISION MATRIX APPROXIMATION [J]. Journal of Computational Mathematics, 2021, 39(5): 693-707.

Viewed

Full text

Abstract

PIECEWISE SPARSE RECOVERY VIA PIECEWISE INVERSE SCALE SPACE ALGORITHM WITH DELETION RULE

扫码分享