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

Gongguo
——————————–
Title: Going off the grid with limited data

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.

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

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.