Seminars & Events

Mathematics and Computer Science Division
"Optimization and its applications to graph partitioning and sparse recovery"

DATE: April 12, 2010
TIME: 10:30 AM - 11:30 AM
SPEAKER: Dung Phan, University of Florida, LANS CACHE Postdoctoral Interviewee
LOCATION: Building 240 Seminar Room 4301, Argonne National Laboratory
HOST: Stefan Wild

Description:
In this talk, we will discuss two applications of optimization to real-world problems: graph partitioning and sparse image and signal reconstruction.Given a graph with edge weights, the graph partitioning problem is topartition the vertices into two sets satisfying specified size constraints, while minimizing the sum of the weights of the edges that connect the vertices in the two sets. This NP-complete combinatorial problem arises in many areas including parallel computing, sparse matrix factorizations, VLSI design, and data mining. We present an exact algorithm for solving this problem which is based on a branch and bound method applied to a continuous quadratic programming formulation. Lower bounds are obtained by decomposing the objective function into convex and concave parts and replacing the concave part by an affine underestimate.Many signal and image reconstruction problems amount to finding a sparse approximate solution to an underdetermined system of linear equations. Under certain assumptions, the problem can be approximated by a convex optimization problem. The SpaRSA algorithm has been shown to work well in practice for solving this nonlinear problem, however, had not been analyzed. We prove that if the objective function is convex, then the error in the function value at iteration k, for k sufficiently large, is bounded by a/(b+k) for suitable choices of a and b. Moreover, if the objective function is strongly convex, then the convergence is R-linear. An improved version of the algorithm based on a cycle version of the BB iteration and an adaptive line search is given. Numerical results providing empirical support to the theoretical results will be presented.

More Information:
Please take the elevators to the Fourth floor and turn right, go down the walk way, room 4301 will be on your left hand side.

Thank you!
Save the event to your calendar [schedule.ics]