A fast method for finding the global solution of the regularized structured total least squares problem for image deblurring

摘要

Given a linear system Ax approximate to b over the real or complex field, where both A and b are subject to noise, the total least squares (TLS) problem seeks to find a correction matrix and a correction right-hand side vector of minimal norm which makes the linear system feasible. To avoid ill posedness, a regularization term is added to the objective function; this leads to the so-called regularized TLS problem. A further complication arises when the matrix A and correspondingly the correction matrix must have a specific structure. This is modeled by the regularized structured TLS (RSTLS) problem. In general this problem is nonconvex and hence difficult to solve. However, the RSTLS problem arising from image deblurring applications under reflexive or periodic boundary conditions possesses a special structure where all relevant matrices are simultaneously diagonalizable (SD). In this paper we introduce an algorithm for finding the global optimum of the RSTLS problem with this SD structure. The devised method is based on decomposing the problem into single variable problems and then transforming them into one-dimensional unimodal real-valued minimization problems which can be solved globally. Based on the uniqueness and attainment properties of the RSTLS solution we show that a constrained version of the problem possesses a strong duality result and can thus be solved via a sequence of RSTLS problems.