Faster Gradient Descent and the Efficient Recovery of Images

 Vietnam Journal of Mathematics 2014

Hui Huang 1, 2*         Uri Ascher 3

1 Shenzhen Institutes of Advanced Technology (SIAT), Chinese Academy of Sciences;              2 Shenzhen VisuCA Key Lab           3University of British Columbia

Figure 1: Comparing different denoising schemes on the 256 × 256 Lena image: (a) true image; (b) image corrupted by 10 % Gaussian white noise serves as data; (c) image denoised using SD step sizes, stopping when ek is below 10−4, 17 iters; (d) image denoised using SD step sizes, stopping when ek is below 10−5, 309 iters, 51.9 s; (e) image denoised by 3 IRLS iterations with β = 0.083 after 17 SD steps, the total CPU time = 2.7 + 5.2 = 7.9 s; (f) image sharpened using 10 SD steps with Tukey function after 17 pre-denoising SD steps with Huber function, the total CPU time = 2.7 + 2.2 = 4.9 s

Much recent attention has been devoted to gradient descent algorithms where the steepest descent step size is replaced by a similar one from a previous iteration or gets updated only once every second step, thus forming a faster gradient descent method. For unconstrained convex quadratic optimization these methods can converge much faster than steepest descent. But the context of interest here is application to certain ill-posed inverse problems, where the steepest descent method is known to have a smoothing, regularizing effect, and where a strict optimization solution is not necessary. Specifically, in this paper we examine the effect of replacing steepest descent by a faster gradient descent algorithm in the practical context of image deblurring and denoising tasks. We also propose several highly efficient schemes for carrying out these tasks independently of the step size selection, as well as a scheme for the case where both blur and significant noise are present. In the above context there are situations where many steepest descent steps are required, thus building slowness into the solution procedure. Our general conclusion regarding gradient descent methods is that in such cases the faster gradient descent methods offer substantial advantages. In other situations where no such slowness buildup arises the steepest descent method can still be very effective.


Figure 2: TYPE =‘LAPLACIAN’, ALPHA =0.2: (b) data b corresponding to η = 10; (c) directly deblurring using β = 10−3 fails; (d) pre-denoising: for the relative error tolerance of 10−4, 10 LSD steps of (12a), (12b) are required; (e) 25 steps of (9) with β = 10−3 and LSD (11b) are required for the next deblurring; (f) 10 sharpening steps with the Tukey function (17) follow. The total CPU time = 14.5s

@ARTICLE{Faster Gradient Descent, 
author = {Hui Huang and Uri Ascher}, 
title = {Faster Gradient Descent and the Efficient Recovery of Images}, 
journal = {Vietnam Journal of Mathematics 2013},

month = {08},

volume = {42},

year = {2013},


Downloads (faster for people in China)

Downloads (faster for people in other places)