Fast Image Deconvolution using Hyper-Laplacian Priors

This document is supplementary material to our NIPS 2009 paper [1] of the same name. While we choose to solve the w sub-problem (Eqn. 5) in [1] using a LUT or analytically (for some specific values of α), a number of numerical alternatives exist. The simplest and fastest approach is to use Newton-Raphson (NR) to find the roots of the polynomials in Eqn. 10 and Eqn 11 of [1]. As shown in Table 1, 4 iterations of NR take a similar time to our analytic solution. However, the numerical algorithm has poor stability, particularly when the polynomials skim the x-axis. In practice, we found it gave spurious solutions around 1-2 % of the time, an unacceptable rate given the iterative nature of our overall algorithm. Applying NR directly to Eqn. 5 of [1] is similarly unreliable. Although techniques with greater stability than NR exist, they are computationally more expensive. For example, we also compare to Matlab’s roots command, based on solving an eigenvalue problem, but this was several orders of magnitude slower than our analytic approach. Another benefit of our algorithms is that they are easily parallelizable. In addition to using Matlab’s. * and. ˆ operators, Algorithms 2 and 3 in [1] can be multi-threaded using the Intel Math Kernel Library (MKL) to give a ∼2 times speedup on a quad-core CPU (see Table 1). Lastly, the LUT approach can be used for values of α not restricted to 1/2 or 2/3. Figure 1 shows the advantage of using a LUT (or analytic method) over using a Newton-Raphson