×

zbMATH — the first resource for mathematics

A modified quasi-Newton diagonal update algorithm for total variation denoising problems and nonlinear monotone equations with applications in compressive sensing. (English) Zbl 1363.65096
Summary: We present a new algorithm to accelerate the Chambolle gradient projection method for total variation image restoration. The new proposed method considers an approximation of the Hessian based on the secant equation. Combined with the quasi-Cauchy equations and diagonal updating, we can obtain a positive definite diagonal matrix. In the proposed minimization method model, we use the positive definite diagonal matrix instead of the constant time stepsize in Chambolle’s method. The global convergence of the proposed scheme is proved. Some numerical results illustrate the efficiency of this method. Moreover, we also extend the quasi-Newton diagonal updating method to solve nonlinear systems of monotone equations. Performance comparisons show that the proposed method is efficient. A practical application of the monotone equations is shown and tested on sparse signal reconstruction in compressed sensing.

MSC:
65H10 Numerical computation of solutions to systems of equations
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
Software:
Matlab; na28
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aubert, Mathematical Problems in Image Processing (2002) · Zbl 1109.35002
[2] Chan, Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods (2005) · Zbl 1095.68127 · doi:10.1137/1.9780898717877
[3] Rudin, Nonlinear total variation based noise removal algorithms, Physica D 60 pp 259– (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F
[4] Chambolle, Image recovery via total variation minimization and related problems, Numerische Mathematik 76 pp 167– (1997) · Zbl 0874.68299 · doi:10.1007/s002110050258
[5] Chan, A nonlinear primal-dual method for total variation-based image restoration, SIAM Journal on Scientific Computing 20 pp 1964– (1999) · Zbl 0929.68118 · doi:10.1137/S1064827596299767
[6] Carter JL Dual methods for total variation-based image restoration Ph.D. Thesis 2001
[7] Chambolle, An algorithm for total variation minimization and applications, Journal of Mathematical Imaging and Vision 20 pp 89– (2004) · Zbl 1366.94048 · doi:10.1023/B:JMIV.0000011321.19549.88
[8] Chambolle, EMMCVPR 05 pp 136– (2005)
[9] Zhu M Wright SJ Chan TF Duality-based algorithms for total variation image restoration Technical Report 2008
[10] Yu, On nonmonotone Chambolle gradient projection algorithms for total variation image restoration, Journal of Mathematical Imaging and Vision 35 pp 143– (2009) · Zbl 05788099 · doi:10.1007/s10851-009-0160-3
[11] Dai, Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming, Numerische Mathematik 100 pp 21– (2005) · Zbl 1068.65073 · doi:10.1007/s00211-004-0569-y
[12] Goldfarb, Parametric maximum flow algorithms for fast total variation minimization, SIAM Journal on Scientific Computing 31 pp 3712– (2009) · Zbl 1198.49040 · doi:10.1137/070706318
[13] Yin, Bregman iterative algorithms for l1-minimization with applications to compressed sensing, SIAM Journal on Imaging Sciences 1 pp 143– (2008) · Zbl 1203.90153 · doi:10.1137/070703983
[14] Goldstein, The split bregman method for l1-regularized problems, SIAM Journal on Imaging Sciences 2 pp 323– (2009) · Zbl 1177.65088 · doi:10.1137/080725891
[15] Xiao, Non-smooth equations based method for l1-norm problems with applications to compressed sensing, Nonlinear Analysis: Theory, Methods, Applications 74 pp 3570– (2011) · Zbl 1217.65069 · doi:10.1016/j.na.2011.02.040
[16] Zhang, Spectral gradient projection method for solving nonlinear monotone equations, Journal of Computational and Applied Mathematics 196 pp 478– (2006) · Zbl 1128.65034 · doi:10.1016/j.cam.2005.10.002
[17] Xiao, An alternating direction method for linear constrained matrix nuclear norm minimization, Numerical Linear Algebra with Applications 19 pp 541– (2012) · Zbl 1274.65115 · doi:10.1002/nla.783
[18] Zhu M Fast numerical algorithms for total variation based image restoration Ph.D. Thesis 2008
[19] Ekeland, Convex Analysis and Variational Problems (1999) · Zbl 0939.49002 · doi:10.1137/1.9781611971088
[20] Barzilai, Two-point step size gradient methods, IMA Journal of Numerical Analysis 8 pp 141– (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[21] Hassan, A new gradient method via quasi-Cauchy relation which guarantees descent, Journal of Computational and Applied Mathematics 230 pp 300– (2009) · Zbl 1179.65067 · doi:10.1016/j.cam.2008.11.013
[22] Leong, A monotone gradient method via weak secant equation for unconstrained optimization, Taiwanese Journal of Mathematical 14 pp 413– (2010) · Zbl 1203.90148
[23] Leong, A scaling on diagonal quasi-Newton update for large-scale unconstrained optimization, Bulletin of the Malaysian Mathematical Sciences Soceity 35 (2) pp 247– (2012)
[24] Nazareth, The quasi-Cauchy relation and diagonal updating, SIAM Journal on Optimization 9 pp 1192– (1999) · Zbl 1013.90137 · doi:10.1137/S1052623498331793
[25] Grippo, A nonmonotone line search technique for Newtons method, SIAM Journal on Optimization 7 pp 26– (1986) · Zbl 0616.65067
[26] Hiriart-Urruty, Convex Analysis and Minimization Algorithms (1993) · Zbl 0795.49001 · doi:10.1007/978-3-662-02796-7
[27] Bertsekas, Nonlinear Programming (1999)
[28] Birgin, Nonmonotone spectral projected gradient methods on convex sets, SIAM Journal on Optimization 10 (4) pp 1196– (2000) · Zbl 1047.90077 · doi:10.1137/S1052623497330963
[29] Dahl, Algorithms and software for total variation image reconstruction via first-order methods, Numerical Algorithms 53 pp 67– (2010) · Zbl 1181.94009 · doi:10.1007/s11075-009-9310-3
[30] Li, A class of derivative-free methods for large-scale nonlinear monotone equations, IMA Journal of Numerical Analysis 31 pp 1625– (2011) · Zbl 1241.65047 · doi:10.1093/imanum/drq015
[31] Yu, An adaptive prediction-correction method for solving large-scale nonlinear systems of monotone equations with applications, Abstract and Applied Analysis 2013 pp 1– (2013)
[32] Solodovand, Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods pp 355– (1999)
[33] Figueiredo, Gradient projection for sparsere construction:application to compressed sensing and other inverse problems, IEEE Journal Selected Topics in Signal Processing 1 (4) pp 586– (2007) · doi:10.1109/JSTSP.2007.910281
[34] Kim, An interior-point method for large-scale l1-regularized least squares, IEEE Journal of Selected Topics in Signal Processing 1 (4) pp 606– (2007) · doi:10.1109/JSTSP.2007.910971
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.