Summary: Nonlinear image reconstruction based upon sparse representations of images has received wide-spread attention recently with the emerging framework of compressed sensing (CS). This theory indicates that, when feasible, judicious selection of the type of distortion induced by measurement systems may dramatically improve our ability to perform signal reconstruction. The basic idea of this theory is that when the signal or image of interest is very sparse (i.e., zero-valued at most locations) or highly compressible in some basis, relatively few indirect observations are necessary to reconstruct the most significant non-zero signal components. For example, consider the surveillance of a scene at night that consists mostly of dark background with a small number of tiny, partially-lit objects. A conventional digital camera or imaging system would need a very high resolution focal plane array (i.e., many megapixels) to effectively localize the few visible objects, but collecting this large number of pixels can be very costly and energy inefficient, particularly in the context of high-end night vision technology. However, compressed sensing theory tells us that we can collect a relatively small number of random projection measurement of the scene and use these to accurately reconstruct the image with very high probability. Simply put, the compressed sensing paradigm reduces the number of measurements needed to accurately describe a signal by exploiting the signal's compressibility.

The Computational Optimization Group's research addresses three key challenges in applying compressed sensing theory to practical imaging systems: (1) physical constraints typically make it infeasible to actually measure random projections; therefore, innovative and sophisticated sensing systems need to be carefully designed to exploit CS theory, (2) extremely fast and scalable optimization methods are critical, since real-time response and decisions for many applications will hinge on the speed of the reconstruction algorithms, and (3) additional constraints must be incorporated into the optimization problem to reflect physical realities.

Summary: Many problems arising in physics and material science can be formulated as elliptic partial differential equations (PDEs) for which the solution is required to satisfy certain inequality constraints. Multigrid methods use a hierarchy of discretizations, approximating the solution of the PDE over a coarse mesh and interpolating the solution to initialize values for the subsequent finer mesh. When the solutions are constrained at each mesh level, this hierarchical scheme produces a sequence of nested constrainted-optimization problems. The approach we proposed uses two levels of iterations: the outer level consists of the computations associated with adaptive multigrid methods for solving PDEs, and the inner level consists of the Newton iterations associated with solving optimization problems with constraints. The optimization problems are solved using primal-dual interior methods, which impose a barrier (parametrized by a scalar that tends to zero near the optimal solution) on the iterates to prevent them from moving too close to the constraints. This allows for relatively long steplengths along a computed search direction, and, consequently, large reduction in the objective function value.

Best previously published results show that the best optimization method solved the minimal surface problem (seen on the right) in 423.62 seconds using a triangulation with 5,000 internal grid points in the discretization (the number of grid points determines the size of the optimization problem, and generally, the larger this number is, the more accurate the PDE solution becomes). Most other methods were not able to solve it within a specified time (1800 seconds). In contrast, the combination multigrid/interior-point method we proposed solved it in 114.21 seconds using 64,000 grid points. These results demonstrate that not only is our proposed approach significantly faster, it can also handle problems that are significantly larger.

Collaborators: Randy Bank (UC San Diego), Philip Gill (UC San Diego)

Summary: Near the solution, optimization algorithms based on Newton's method generally demonstrate quadratic convergence. Often, the rate-limiting step in these methods is the calculation of search directions, which involves solving symmetric linear systems of equations of the form Ax = b at each iteration. For large-scale problems, these equations can be solved using conjugate-gradient (CG) methods whenever A is positive definite. However, CG methods can break down if A is indefinite because the LDL' factorization of the tridiagonal matrix T in the underlying Lanczos process is unstable. (Here, L is unit lower triangular and D is diagonal.)

This instability can be overcome by diagonal pivoting strategies that compute an LBL' factorization of T instead, where B is block diagonal with 1x1 and 2x2 blocks. It can be proven that solving a symmetric tridiagonal linear system using a factorization we proposed with this pivoting strategy is normwise backwards stable, with the additional feature that it reduces to the LDL' factorization whenever T is positive definite. This pivoting strategy was used to solve indefinite systems (like the KKT system arising in optimization or saddle-point systems in numerical PDE). On these systems, the performance of a symmetric indefinite factorized CG (ASIFCG) method we developed has a comparable convergence behavior to those of well-established methods like SYMMLQ for solving symmetric indefinite systems; however, it was shown that ASIFCG is more computationally efficient. More recently, this diagonal pivoting approach was generalized to solve unsymmetric tridiagonal linear systems, and similar proofs of stability were also obtained.

Collaborators: James Bunch (UC San Diego), Jennifer Erway (Wake Forest)
Students: Joseph Tyson (Wake Forest)

Summary: Understanding the mechanism of molecular interactions helps biologists identify processes and molecular features that are important in protein binding. In biology, site-directed mutagenesis can either abrogate or enhance these interactions, a technique that allows biologists and chemists to develop more effective drugs and better disease treatment. With the growing number of molecular structures available in the Protein Data Bank, scientists are looking to use computational tools to help them model their problems in silico, e.g., predict potential docking configurations and identify which amino acids are crucial in the interactions using software.

Convex underestimation originated as a method for performing global minimization on protein folding by cleverly utilizing the overabundance of local energy minima: it traces out the shape of an energy landscape based on the location of its minima. Each local minima represents a stable, but not globally optimal, configuration between two protein molecules. By fitting a convex (often quadratic) surrogate function to the positions of the minima and narrowing the search space to near the minimum of this surrogate function, the method guides iterates toward the global minimum of the true energy function. For energy functions with single prominent energy basins, convex quadratic underestimation has been shown to be highly successful. However, for multi-basin functions, other prominent basins can impede the search for the global minima. To circumvent this issue, we developed a divide-and-conquer approach, where local minima from a coarse-grained sampling are clustered, with each cluster underestimated to produce a number of cluster minima. Published results demonstrate the effectiveness of this approach for small rigid docking systems. We combined this clustering-underestimation technique into a single step: rather than a single convex quadratic surrogate, a sum of negative Gaussian functions can more accurately model functions with multiple energy basins.