Frank-Wolfe And Primal-Dual Algorithms For Constrained Least Squares Problem

With the arrival of the big data space, the demanding for the information is in-creasing. But the information is mainly viewed as image. In the images acquisition or transmission processing, due to various factors, the images will inevitably leaded to a decline in the quality of the images. For example, the geometric distortion, the mo-tion blur, defocus blur, and the noises, etc. Therefore, digital image restoration is an important aspect of the digital image processing.In image restoration problem, box-constrained least squares minimization prob-lem often needs to solved. Traditionally, the steepest descent method was usually used for solving an unconstrained least squares problem, then projecting the solution into the box-constraints. This approach will obtain a suboptimal solution. Frank-Wolfe algorithm and Primal-Dual algorithm, which both enjoy the convergence rate of O(1/k), are applied to solve the constrained minimization problem in this pa-per. The main contents of this paper are:developing numerical optimization algo-rithms to solve the constrained least squares problems to improve the quality of the restored the gray scale images. The main work in this paper is as follows:(1) Images restoration theories are introduced in the first section, and the re-searches in recent years about images restoration are reviewed. Because the box-constrained least squares problem has been applied to many areas, so that the box-constrained least squares model was considered to restore the images.(2) The steepest descent algorithm is a minimization algorithm, which based on the direction of the negative gradient and was applied to solve the box-constrained least squares problem.(3) Because the steepest descent method is for solving the unconstrained prob-lem, the Frank-Wolfe algorithm was applied to solve the box-constrained least squares problem.(4) The Primal-Dual algorithm was described clearly and applied to solve the box-constrained least squares problems.(5) The results of the experiments which compares the Frank-Wolfe algorithm with the steepest descent algorithm and the Primal-Dual algorithm with the steepest descent algorithm respectively show that the Primal-Dual algorithm and the Frank-Wolfe algorithm are superior than the steepest descent algorithm. The algo-rithms for solving constrained problems are better than the unconstrained algorithms.