TECHNICAL REPORTS: (2008)
A Fast Algorithm for Edge-Preserving Variational Multichannel Image Restoration
Junfeng Yang, Wotao Yin, Yin Zhang, & Yilun Wang
We generalize the alternating minimization algorithm recently proposed in [32] to effciently solve a general, edge-preserving, variational model for recovering multichannel images degraded by within- and cross-channel blurs, as well as additive Gaussian noise. This general model allows the use of localized weights and higher-order derivatives in regularization, and includes a multichannel extension of total variation (MTV) regularization as a special case. In the MTV case, we show that the model can be derived from an extended half-quadratic transform of Geman and Yang [14]. For color images with three channels and when applied to the MTV model (either locally weighted or not), the per-iteration computational complexity of this algorithm is dominated by nine fast Fourier transforms. We establish strong convergence results for the algorithm including finite convergence for some variables and fast q-linear convergence for the others. Numerical results on various types of blurs are presented to demonstrate the performance of our algorithm compared to that of the MATLAB deblurring functions. We also present experimental results on regularization models using weighted MTV and higher-order derivatives to demonstrate improvements in image quality provided by these models over the plain MTV model.
Key Words: half-quadratic, cross-channel, image deblurring, isotropic total variation, fast Fourier transform.
July 2008
A Fast Algorithm for Large Scale l1-Regularized Logistic Regression
Jianing Shi, Wotao Yin, Stanley Osher, & Paul Sajda
l1-regularized logistic regression, also known as sparse logistic regression, is widely used in machine learning, computer vision, data mining, bioinformatics and neural signal processing. The use of l1-regularization attributes attractive properties to the classifier, such as feature selection, robustness to noise, and as a result, classifier generality in the context of supervised learning. When a sparse logistic regression problem has large-scale data in high dimensions, it is computationally expensive to minimize the non-differentiable l1-norm in the objective function. Motivated by recent work (Hale et al., 2008; Koh et al., 2007), we propose a novel hybrid algorithm based on combining two types of optimization iterations: one being very fast while the other being slower but more accurate. Called hybrid iterative shrinkage (HIS), the resulting algorithm is based completely on memory efficient operations such as matrix-vector multiplications. Furthermore, we show various optimization techniques including line search and continuation can significantly accelerate convergence. The algorithm has global convergence at a geometric rate (a Q-linear rate in optimization terminology). We present a numerical comparison with several existing algorithms, using benchmark data from the UCI machine learning repository, and show our algorithm is the most computationally efficient without loss of accuracy.
Key Words: Logistic regression, l1 regularization, fixed point continuation, supervised learning, large scale.
July 2008
Fast Linearized Bregman Iteration for Compressive Sensing and Sparse Denoising
Stanley Osher, Yu Mao, Bin Dong, & Wotao Yin
We propose and analyze an extremely fast, e±cient and simple method for solving the problem:
min { ||x||1 : Au = f }
This method was first described in [1], with more details in [2] and rigorous theory given in [3]. The motivation was compressive sensing, which now has a vast and exciting history, which seems to have started with Candes, et.al. [4] and Donoho, [5]. See [2], [3] for a large set of references. Our method introduces an improvement called "kicking" of the very efficient method of [1], [2] and also applies it to the problem of denoising of undersampled signals. The use of Bregman iteration for denoising of images began in [6] and led to improved results for total variation based methods. Here we apply it to denoise signals, especially essentially sparse signals, which might even be undersampled.
June 2008
Solving Computationally Expensive Optimization Problems with CPU Time-Correlated Functions
Mark A. Abramson, Thomas J. Asaki, J. E. Dennis, Jr., Raymond Magallanez, & Matthew J. Sottile
In this paper, we characterize a new class of optimization problems in which objective function values are correlated with the computational time required to obtain these values. That is, as the optimal solution is approached, the computational time required to compute an objective function values decreases significantly. This is motivated by an application in which each objective function evaluation requires both a numerical fluid dynamics simulation and an image registration process, and the goal is to find the parameter values of a predetermined reference image by comparing the flow dynamics from the numerical simulation and the reference image through the image comparison process. In designing an approach to numerically solve the more general class of problems in an efficient way, we make use of surrogates based on CPU times of previously evaluated points, rather than their function values, all within the SEARCH step framework of mesh adaptive direct search algorithms. Because of the expected CPU time correlation, a time cutoff parameter was added to the objective function evaluation to allow its termination during the comparison process if the computational time exceeds a specified threshold. The approach was tested using the NOMADm and DACE MATLAB software packages, and results are presented.
June 2008
Numerical Solution of Implicitly Constrained Optimization Problems
Matthias Heinkenschloss
Many applications require the minimization of a smooth function f: Rn → R whose evaluation requires the solution of a system of nonlinear equations. This system represents a numerical simulation that must be run to evaluate f. We refer to this system of nonlinear equations as an implicit constraint.
In theory f can be minimized using the steepest descent method or Newton-type methods for unconstrained minimization. However, for the practical application of derivative based methods for the minimization of f one has to deal with many interesting issues that arise out of the presence of the system of nonlinear equations that must be solved to evaluate f.
This article studies some of these issues, ranging from sensitivity and adjoint techniques for derivative computation to implementation issues in Newton-type methods. A discretized optimal control problem governed by the unsteady Burgers equation is used to illustrate the ideas.
Key words: Unconstrained minimization, implicit constraints, adjoints, sensitivities, Newton method, nonlinear programming, optimal control, Burgers equation.
May 2008
A Quadratically Constrained Minimization Problem Arising from PDE of Monge-Ampére Type
D.C. Sorensen & Roland Glowinski
This note develops theory and a solution technique for a quadratically constrained eigenvalue minimization problem. This class of problems arises in the numerical solution of fully-nonlinear boundary value problems of Monge-Ampére type. Though it is most important in the three dimensional case, the solution method is directly applicable to systems of arbitrary dimension.
The focus here is on solving the minimization subproblem which is part of a method to numerically solve a Monge-Ampére type equation. These subproblems must be evaluated many times in this numerical solution technique and thus efficiency is of utmost importance.
A novelty of this minimization algorithm is that it is finite of complexity O(N^3) with the exception of solving a very simple rational function of one variable. This function is essentially the same for any dimension. This result is quite surprising given the nature of the minimization problem.
May 2008
ORTHOMADS: A Deterministic MADS Instance with Orthogonal Directions
Mark A. Abramson, Charles Audet, J.E. Dennis, Jr. & Sébastien Le Digabel
The purpose of this paper is to introduce a new way of choosing directions for
the Mesh Adaptive Direct Search (MADS) class of algorithms. The advantages of
this new OrthoMADS instantiation of MADS are that the polling directions are
chosen deterministically, ensuring that the results of a given run are repeatable,
and that they are orthogonal to each other, therefore the convex cones of missed
directions at each iteration are minimal in size.
The convergence results for OrthoMADS follow directly from those already published
for MADS, and they hold deterministically, rather than with probability one, as for
LTMADS, the first MADS instance. The initial numerical results are quite good for
both smooth and nonsmooth, and constrained and unconstrained problems considered here.
Key words: Mesh Adaptive Direct Search algorithms (MADS), deterministic, orthogonal directions, constrained optimization, nonlinear programming.
February 2008
A Curvilinear Search Method for p-Harmonic Flows on Spheres
Donald Goldfarb, Zaiwen Wen, & Wotao Yin
The problem of finding p-harmonic flows arises in a wide range of applications including micromagnetics, liquid crystal theory, directional diffusion, and chromaticity denoising. In this paper, we propose an innovative curvilinear search method for minimizing p-harmonic energies over spheres. Starting from a flow (map) on the unit sphere, our method searches along a curve that lies on the sphere in a manner similar to a standard inexact line search descent method. We show that our method is globally convergent if the step length satisfies the Armijo-Wolfe conditions. Computational tests are presented to demonstrate the efficiency of the proposed method and a variant of it that uses Barzilai-Borwein steps.
Key words: Energy minimization, p-harmonic maps, p-harmonic flows, finite difference, curvi- linear search, global convergence, chromaticity denoising.
January 2008
Iterative Reweighted Algorithms for Compressive Sensing
Rick Chartrand & Wotao Yin
The theory of compressive sensing has shown that sparse signals can be reconstructed exactly from many fewer measurements than traditionally believed necessary. In [1], it was shown empirically that using lp minimization with p<1 can do so with fewer measurements than with p=1. In this paper we consider the use of iteratively reweighted algorithms for computing local minima of the nonconvex problem. In particular, a particular regularization strategy is found to greatly improve the ability of a reweighted least-squares algorithm to recover sparse signals, with exact recovery being observed for signals that are much less sparse than required by an unregularized version (such as FOCUSS, [2]). Improvements are also observed for the reweighted-l1 approach of [3].
Key words: Compressive sensing, signal reconstruction, nonconvex optimization, iteratively reweighted least squares, l1 minimization.
January 2008