Titles By Year
Abstracts By Year
Technical Reports (2013)
On the Approximation of the Dirichlet to Neumann Map for High Contrast Two Phase Composites
Yingpei Wang
Many problems in the natural world have high contrast properties, like transport in composites, fluid in porous media and so on. These problems have huge numerical difficulties because of the singularities of their solutions. It may be really expensive to solve these problems directly by traditional numerical methods. It is necessary and important to understand these problems more in mathematical aspect first, and then using the mathematical results to simplify the original problems or develop more efficient numerical methods.
In this thesis we are going to approximate the Dirichlet to Neumann map for the high contrast two phase composites. The mathematical formulation of our problem is to approximate the energy for an elliptic equation with arbitrary boundary conditions. The boundary conditions may have highly oscillations, which makes our problems very interesting and difficult.
We developed a method to divide the domain into two different subdomains, one is close to and the other one is far from the boundary, and we can approximate the energy in these two subdomains separately. In the subdomain far from the boundary, the energy is not influenced that much by the boundary conditions. Methods for approximation of the energy in this subdomain are studied before. In the subdomain near the boundary, the energy depends on the boundary conditions a lot. We used a new method to approximate the energy there such that it works for any kind of boundary conditions. By this way, we can have the approximation for the total energy of high contrast problems with any boundary conditions.
In other words, we can have a matrix up to any dimension to approximate the continuous Dirichlet to Neumann map of the high contrast composites. Then we will use this matrix as a preconditioner in domain decomposition methods, such that our numerical methods are very efficient to solve the problems in high contrast composites.
April 2013
Linearly Convergent Decentralized Consensus Optimization with the Alternating Direction Method of Multipliers
W. Shi, Q. Ling, K. Yuan, G. Wu, & W. Yin
In a decentralized consensus optimization problem, a network of agents minimizes the summation of their local objec- tive functions on a common set of decision variables, allowing only information exchange among neighbors. The alternating direction method of multipliers (ADMM) has been shown to be a powerful tool for solving the problem with empirically fast convergence.
This paper establishes the linear convergence rate of the ADMM in decentralized consensus optimization. The theoretical convergence rate is a function of the network topology, properties of the local objective functions, and the algorithm parameter. This result not only gives a performance guarantee for the ADMM but also provides a guideline to ac- celerate its convergence for decentralized consensus optimization problems.
April 2013
A Linearized Bregman Algorithm for Decentralized Basis Pursuit
K. Yuan, Q. Ling, W. Yin, & A. Ribeiro
We solve a decentralized basis pursuit problem in a multiagent system, where each agent holds part of the linear observations on a common sparse vector, and all the agents collaborate to recover the sparse vector through limited neighbor-to-neighbor communication.
The proposed decentralized linearized Bregman algorithm solves the Lagrange dual of an augmented l1 model that is equivalent to basis pursuit. The fact that this dual problem is unconstrained and differentiable enables a lightweight yet efficient decentralized gradient algorithm.
We prove nearly linear convergence of the algorithm in the sense that uniformly for every agent i, the error obeys |x_i(k) - x*|<=e(k) and e(k)<=rho e(k-1)+gamma, where rho<=1 and gamma>=0 are independent of k or i. Numerical experiments demonstrate this convergence.
April 2013
Optimal Distribution of Medical Backpacks and Health Surveillance Assistants in Malawi
Amber G. Kunkel, Elizabeth S. Van Itallie, & Duo Wu
Despite recent progress, Malawi continues to perform poorly on key health indicators such as child mortality and life expectancy. These problems are exacerbated by a severe lack of access to health care. Health Surveillance Assistants (HSAs) help bridge this gap by providing community-level access to basic health care services. However, the success of these HSAs is limited by a lack of supplies and long distances between HSAs and patients. To address this issue, we used large-scale p-median and capacitated facility location problems to create a scalable, three-tiered plan for optimal allocation of HSAs, HSA designated medical backpacks, and backpack resupply centers. Our analysis uses real data on the location and characteristics of hospitals, health centers, and the general population. In addition to offering specific recommendations for HSA, backpack, and resupply center locations, it provides general insights into the scope of the proposed HSA backpack program scale-up. In particular, it demonstrates the importance of local health centers to the resupply network. The proposed assignments are robust to changes in the underlying population structure, and could significantly improve access to medical supplies for both HSAs and patients.
March 2013
Gradient Methods for Convex Minimization: Better Rates Under Weaker Conditions
Hui Zhang & Wotao Yin
The convergence behavior of gradient methods for minimizing convex differentiable functions is one of the core questions in convex optimization. This paper shows that their well-known complexities can be achieved under conditions weaker than the commonly assumed ones. We relax the common gradient Lipschitz-continuity condition and strong convexity condition to ones that hold only over certain line segments. Specifically, we establish complexities O(R/eps) and O(sqrt(R/eps)) for the ordinary and accelerate gradient methods, respectively, assuming that ∇f is Lipschitz continuous with constant R over the line segment joining x and x-∇f/R for each x in the domain of f. Then we improve them to O((R/ν) log(1/eps)) and O(sqrt(R/ν) log(1/eps)) for function f that also satisfies the secant inequality (∇f(x))T(x-x*)> ≥ ν||x-x*||2 for each x in the domain of f and its projection x* to the minimizer set of f. The secant condition is also shown to be necessary for the geometric decay of solution error. Not only are the relaxed conditions met by more functions, the restrictions give smaller R and larger ν than they are without the restrictions and thus lead to better complexity bounds. We apply these results to sparse optimization and demonstrate a faster algorithm.
March 2013
Trace-Penalty Minimization for Large-scale Eigenspace Computation
Zaiwen Wen, Chao Yang, Xin Liu, & Yin Zhang
The Rayleigh-Ritz (RR) procedure, including orthogonalization, constitutes a major bottleneck in computing relatively high-dimensional eigenspaces of large sparse matrices. Although operations involved in RR steps can be parallelized to an extent, their parallel scalability, limited by some inherent sequentiality, is lower than dense matrix-matrix multiplications. The primary motivation of this paper is to develop a methodology that reduces the use of the RR procedure in exchange for matrix-matrix multiplications. We propose an unconstrained penalty model and establish its equivalence to the eigenvalue problem. This model enables us to deploy gradient-type algorithms heavily dominated by dense matrixmatrix multiplications. Although the proposed algorithm does not necessarily reduce the total number of arithmetic operations, it leverages highly optimized operations on modern high performance computers to achieve parallel scalability. Numerical results based on a preliminary implementation, parallelized using OpenMP, show that our approach is promising.
February 2013
Applying the Short-Time Direct Directed Transfer Function to Human Electrocorticographic Recordings from a Language Task
Meagan Lee Whaley
This thesis applied the short-time direct directed transfer function (SdDTF) to time series data recordings from intracranial electrodes that measure the brain's electrical activity to determine the causal influences that occurred between brain regions during a speech production task. The combination of high temporal and spatial resolution of the electrocorticography (ECoG) recordings directly from the cortex render these measurements of brain activity desirable, particularly when analyzing the fine cognitive dynamics involved in word generation. This research applied a new method to characterize the SdDTF results by compressing across time and high gamma frequencies, generating adjacency matrices, and graphing them to visualize the influences between anatomical regions over the duration of the entire task. This consolidated SdDTF analysis technique allowed for data from a total of seven patients to be combined, generating results which were consistent with current speech production models. The results from this thesis contribute to the expansion of language research by identifying areas relevant to word generation, providing information that will help surgeons avoid irreparable damage to crucial cortex during brain surgery.
February 2013
A New Detail-Preserving Regularity Scheme
W. Guo, J. Qin, & W. Yin
It is a challenge task to reconstruct images from their noisy, blurry, and/or incomplete measurements, especially those with important details and features such as medical MR and CT images.
We propose a novel regularization model that integrates two recently-developed regularization approaches based on total generalized variation (TGV) and the shearlet transform and recovers both edges and fine details of images much better than the existing regularization models based on total variation (TV) and wavelets.
Specifically, while TV preserves sharp edges and suffers the oil-painting artifact, TGV "selectively regularizes" only image edge regions and thus avoids oil-painting artifact. Unlike the wavelet transform, which represents isotropic image features much more sparsely than anisotropic ones, the shearlet transform can also efficiently represent anisotropic features such as edges, curves, and so on. The proposed model has been tested in the compressive sensing context and reconstructed high-quality images from fewer measurements than the state-of-the-art methods. It also applies to other image processing tasks such as denoising, deblurring, change detection, object tracking, etc. The proposed model is solved by variable splitting and the alternating direction method of multiplier (ADMM). For certain sensing operators including the partial Fourier transform, all the ADMM subproblems have closed-form solutions. Convergence of the algorithm is presented.
The numerical simulation presented in this paper uses the incomplete Fourier, discrete cosine, and wavelet measurements of magnetic resonance (MR) images and natural images. The proposed method is demonstrated to preserve various image features including edges and textures much better than TV/wavelet based methods.
January 2013