The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group


with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Going off the grid with limited data | DWQP: A solver for large scale box constrained quadratic programs.

Gongguo Tang | Srikrishna Sridhar, EE Post-doc | CS Grad Student

Date and Time: Mar 05, 2013 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building


Title: Going off the grid with limited data

Abstract: Most of the recent activity on sparse signal recovery has focused on signals with sparse representations in finite discrete dictionaries. However, signals encountered in applications such as imaging, radar, sonar, sensor array, communication, seismology, and remote sensing are usually specified by sparse parameters in continuous domains. In this talk, I will show that atomic minimization provides a general convex approach to directly enforce sparsity in the continuous domain, thus circumventing some of the computational and theoretical issues arising from discretization based approaches. I then specialize the framework to estimating the continuous frequencies and phases of a mixture of complex exponentials from incomplete, noisy, and corrupted time samples. I will demonstrate that the corresponding atomic minimization problems have exact semidefinite reformulations. For the natural random subsampling scheme, the number of samples necessary for accurate frequency estimation is proportional to the number of frequencies present in the signal, up to log factors. This is a direct generalization of compressive sensing with a discretized Fourier dictionary that is completely free of gridding. I will also discuss implications of the results in spectral estimation, signal sampling, and super-resolution imaging.

Title: DWQP: A solver for large scale box constrained quadratic programs.

Abstract: Box constrained quadratic programs (BQPs) are a class of quadratic programming problems where the variables are subject only to lower and upper bound constraints. Large scale BQPs arise in many applications such as support vector machines, portfolio optimization, nonnegative matrix factorizations and sparse optimization. Instead of using specialized algorithms for a specific application, we exploit the structure of the data to solve BQPs of unprecedented scale. The intuition behind our approach is that while the applications for BQPs vary widely, only a handful of data processing techniques are needed solve the problem.

Our solver uses an asynchronous version of Stochastic Coordinate descent (SCD); an algorithm that updates, during each iteration, a single component from the vector of decision variables. The inexpensive and sparse update rule of SCD makes it an ideal candidate for a large scale BQP solver.

We demonstrate that understanding two aspects of the hardware; processor affinity and data placement is essential in building a BQP solver that can effectively use multi-core processors. Our preliminary results show that our solver can be up to 100x faster than state-of-the-art commercial quadratic programming solvers.