Quartic Optimization Problems

Many tasks in signal processing and machine learning involve minimizing polynomials of degree four. These include phase retrieval, matrix factorization, sensor network localization and many more. In this talk, I will give an overview of the challenges of quartic minimization as well as some complexity results. In particular, we will focus on a particular class of convex quartic problems, and we analyze the notion of quartic condition number. We design an algorithm for reducing this condition number. To do so, we build a preconditioner using a generalized version of the Lewis weights (a.k.a leverage scores), and we show that it is optimal in some specific sense.

Based on joint work with Yurii Nesterov.