Variational Bayesian Blind Image Deconvolution: A review <s> C. Covariance approximation and general optimization issues <s> SUMMARY This paper presents necessary and sufficient conditions under which a random variable X may be generated as the ratio ZI V where Z and V are independent and Z has a standard normal distribution. This representation is useful in Monte Carlo calculations. It is established that when 7 V2 is exponential, X is double exponential; and that when WV has the asymptotic distribution of the Kolmogorov distance statistic, X is logistic. <s> BIB001 </s> Variational Bayesian Blind Image Deconvolution: A review <s> C. Covariance approximation and general optimization issues <s> In this paper, we propose novel algorithms for total variation (TV) based image restoration and parameter estimation utilizing variational distribution approximations. Within the hierarchical Bayesian formulation, the reconstructed image and the unknown hyper parameters for the image prior and the noise are simultaneously estimated. The proposed algorithms provide approximations to the posterior distributions of the latent variables using variational methods. We show that some of the current approaches to TV-based image restoration are special cases of our framework. Experimental results show that the proposed approaches provide competitive performance without any assumptions about unknown hyper parameters and clearly outperform existing methods when additional information is included. <s> BIB002 </s> Variational Bayesian Blind Image Deconvolution: A review <s> C. Covariance approximation and general optimization issues <s> The heavy-tailed distribution of gradients in natural scenes have proven effective priors for a range of problems such as denoising, deblurring and super-resolution. These distributions are well modeled by a hyper-Laplacian (p(x) ∝ e-k|x|α ), typically with 0.5 ≤ α ≤ 0.8. However, the use of sparse distributions makes the problem non-convex and impractically slow to solve for multi-megapixel images. In this paper we describe a deconvolution approach that is several orders of magnitude faster than existing techniques that use hyper-Laplacian priors. We adopt an alternating minimization scheme where one of the two phases is a non-convex problem that is separable over pixels. This per-pixel sub-problem may be solved with a lookup table (LUT). Alternatively, for two specific values of α, 1/2 and 2/3 an analytic solution can be found, by finding the roots of a cubic and quartic polynomial, respectively. Our approach (using either LUTs or analytic formulae) is able to deconvolve a 1 megapixel image in less than ~3 seconds, achieving comparable quality to existing methods such as iteratively reweighted least squares (IRLS) that take ~20 minutes. Furthermore, our method is quite general and can easily be extended to related image processing problems, beyond the deconvolution application demonstrated. <s> BIB003 </s> Variational Bayesian Blind Image Deconvolution: A review <s> C. Covariance approximation and general optimization issues <s> Nonconvex nonsmooth regularization has advantages over convex regularization for restoring images with neat edges. However, its practical interest used to be limited by the difficulty of the computational stage which requires a nonconvex nonsmooth minimization. In this paper, we deal with nonconvex nonsmooth minimization methods for image restoration and reconstruction. Our theoretical results show that the solution of the nonconvex nonsmooth minimization problem is composed of constant regions surrounded by closed contours and neat edges. The main goal of this paper is to develop fast minimization algorithms to solve the nonconvex nonsmooth minimization problem. Our experimental results show that the effectiveness and efficiency of the proposed algorithms. <s> BIB004 </s> Variational Bayesian Blind Image Deconvolution: A review <s> C. Covariance approximation and general optimization issues <s> In blind deconvolution one aims to estimate from an input blurred image y a sharp image x and an unknown blur kernel k. Recent research shows that a key to success is to consider the overall shape of the posterior distribution p(x, k\y) and not only its mode. This leads to a distinction between MAP x, k strategies which estimate the mode pair x, k and often lead to undesired results, and MAP k strategies which select the best k while marginalizing over all possible x images. The MAP k principle is significantly more robust than the MAP x, k one, yet, it involves a challenging marginalization over latent images. As a result, MAP k techniques are considered complicated, and have not been widely exploited. This paper derives a simple approximated MAP k algorithm which involves only a modest modification of common MAP x, k algorithms. We show that MAP k can, in fact, be optimized easily, with no additional computational complexity. <s> BIB005 </s> Variational Bayesian Blind Image Deconvolution: A review <s> C. Covariance approximation and general optimization issues <s> Many problems of recent interest in statistics and machine learning can be posed in the framework of convex optimization. Due to the explosion in size and complexity of modern datasets, it is increasingly important to be able to solve problems with a very large number of features or training examples. As a result, both the decentralized collection or storage of these datasets as well as accompanying distributed solution methods are either necessary or at least highly desirable. In this review, we argue that the alternating direction method of multipliers is well suited to distributed convex optimization, and in particular to large-scale problems arising in statistics, machine learning, and related areas. The method was developed in the 1970s, with roots in the 1950s, and is equivalent or closely related to many other algorithms, such as dual decomposition, the method of multipliers, Douglas–Rachford splitting, Spingarn's method of partial inverses, Dykstra's alternating projections, Bregman iterative algorithms for l1 problems, proximal methods, and others. After briefly surveying the theory and history of the algorithm, we discuss applications to a wide variety of statistical and machine learning problems of recent interest, including the lasso, sparse logistic regression, basis pursuit, covariance selection, support vector machines, and many others. We also discuss general distributed optimization, extensions to the nonconvex setting, and efficient implementation, including some details on distributed MPI and Hadoop MapReduce implementations. <s> BIB006 </s> Variational Bayesian Blind Image Deconvolution: A review <s> C. Covariance approximation and general optimization issues <s> A nonconvex variational model is introduced which contains the $\ell_q$-``norm,” $q\in (0,1)$, of the gradient of the underlying image in the regularization part together with a least squares--type data fidelity term which may depend on a possibly spatially dependent weighting parameter. Hence, the regularization term in this functional is a nonconvex compromise between the minimization of the support of the reconstruction and the classical convex total variation model. In the discrete setting, existence of a minimizer is proved, and a Newton-type solution algorithm is introduced and its global as well as local superlinear convergence toward a stationary point of a locally regularized version of the problem is established. The potential nonpositive definiteness of the Hessian of the objective during the iteration is handled by a trust-region--based regularization scheme. The performance of the new algorithm is studied by means of a series of numerical tests. For the associated infinite dimensional model a... <s> BIB007 </s> Variational Bayesian Blind Image Deconvolution: A review <s> C. Covariance approximation and general optimization issues <s> We present a general method for blind image deconvolution using Bayesian inference with super-Gaussian sparse image priors. We consider a large family of priors suitable for modeling natural images, and develop the general procedure for estimating the unknown image and the blur. Our formulation includes a number of existing modeling and inference methods as special cases while providing additional flexibility in image modeling and algorithm design. We also present an analysis of the proposed inference compared to other methods and discuss its advantages. Theoretical and experimental results demonstrate that the proposed formulation is very effective, efficient, and flexible. <s> BIB008 </s> Variational Bayesian Blind Image Deconvolution: A review <s> C. Covariance approximation and general optimization issues <s> Regularized minimization problems with nonconvex, nonsmooth, perhaps non-Lipschitz penalty functions have attracted considerable attention in recent years, owing to their wide applications in image restoration, signal reconstruction, and variable selection. In this paper, we derive affine-scaled second order necessary and sufficient conditions for local minimizers of such minimization problems. Moreover, we propose a global convergent smoothing trust region Newton method which can find a point satisfying the affine-scaled second order necessary optimality condition from any starting point. Numerical examples are given to demonstrate the effectiveness of the smoothing trust region Newton method. <s> BIB009 </s> Variational Bayesian Blind Image Deconvolution: A review <s> C. Covariance approximation and general optimization issues <s> Iteratively reweighted least squares (IRLS) is one of the most effective methods to minimize the l p regularized linear inverse problem. Unfortunately, the regularizer is nonsmooth and nonconvex when 0 < p < 1. In spite of its properties and mainly due to its high computation cost, IRLS is not widely used in image deconvolution and reconstruction. In this paper, we first derive the IRLS method from the perspective of majorization minimization and then propose an Alternating Direction Method of Multipliers (ADMM) to solve the reweighted linear equations. Interestingly, the resulting algorithm has a shrinkage operator that pushes each component to zero in a multiplicative fashion. Experimental results on both image deconvolution and reconstruction demonstrate that the proposed method outperforms state-of-the-art algorithms in terms of speed and recovery quality. <s> BIB010
The covariance matrix C x plays a very important role not only in the image estimation step but also in the kernel estimation step. This matrix makes VB methods different from MAP methods. Intuitively, the introduction of C x in the estimation of the weights ξ makes their estimated values slightly smaller than when the covariance is not considered. As a result, the edges are better preserved. Besides, in the kernel estimation step, it provides an adaptive smoothness promoting regularization term which helps avoid the delta kernel estimates. Unfortunately, due to the high computational cost, C x is approximated by the inverse of the diagonal of the weighted deconvolution matrix C −1 x . Since C −1 x is not diagonal, the diagonal approximation definitely introduces an error. The diagonal approximation is only reliable when β −1 and ξ are relatively large. If both β −1 and ξ are small, this approximation is not that reliable. Another alternative is the mean value approximation proposed by Babacan et al. BIB002 , which replaces the weights ξ γ with the average N i=1 ξ γ (i)/N , so that C x is a circulant matrix associated with the kernel h Cx = F −1 Λ −1 h , where F denotes the 2-D DFT and Λ h is a column vector formed by the eigenvalues of C −1 x . h Cx has a large but finite support thanks to regularization and can be computed efficiently with the use of an FFT. This approximation takes the non-diagonal elements information into account, but the important information on the spatially variant weights is lost. The consequences of the use of the diagonal and mean value approximation remain an open question. Better but also feasible approximations to C x should also be explored. Notice that the image estimation step involves solving a nonconvex problem when the penalty function is nonconvex, e.g., ρ(s) = s p /p (0 < p < 1). Assuming that the covariance term in ξ is ignored, it has been shown in BIB010 that the IRLS method which alternatively solves the linear equations in  and updates the weights by BIB001 , definitely converges to a stationary point. Since the problem is nonconvex, the initial weights can make a difference in the final result, especially for the extremely nonconvex functions like log. A typical choice for the initial weights is the use of a large constant (e.g., 10 4 , see BIB005 BIB008 ). It is conceivable that a ξ whose large values are located at the blur region may lead to a good stationary point, as the blur will be removed accurately. Since it is hard to know the blur region, finding such a good initial weights is not a trivial task in BID. Finally, we would like to mention that the linear equations (25) can be efficiently solved by ADMM BIB010 (Alternating Direction Method of Multipliers, see BIB006 for a comprehensive review), provided that the blur is spatially invariant. Together with the IRLS method BIB010 , other nonconvex optimization methods including variable splitting and look-up-table based method BIB003 , 1 -decomposition based method BIB004 , and recently the smoothing trust region methods BIB007 BIB009 have also been applied to image deconvolution.