Justin Romberg

Georgia Institute of Technology, USA

Convex Programming for Non-Convex Problems
Video recording available for Signal Processing Society Members
Wednesday, 13 June
Emperors’ Hall
10:30 – 11:30


We consider the question of estimating a solution to a system of equations that involve convex nonlinearities, a problem that is common in machine learning and signal processing.

Because of these nonlinearities, conventional estimators based on empirical risk minimization generally involve solving a non-convex optimization program. We propose a method (called “anchored regression”) that is based on convex programming and amounts to maximizing a linear functional (perhaps augmented by a regularizer) over a convex set. 

The proposed convex program is formulated in the natural space of the problem, and avoids the introduction of auxiliary variables, making it computationally favorable. Working in the native space also provides us with the flexibility to incorporate structural priors (e.g., sparsity) on the solution.

For our analysis, we model the equations as being drawn from a fixed set according to a probability law.  Our main results provide guarantees on the accuracy of the estimator in terms of the number of equations we are solving, the amount of noise present, a measure of statistical complexity of the random equations, and the geometry of the regularizer at the true solution. We also provide recipes for constructing the anchor vector (that determines the linear functional to maximize) directly from the observed data.

We will discuss applications of this technique to nonlinear problems including phase retrieval, blind deconvolution, and inverting the action of a neural network.

This is joint work with Sohail Bahmani.


Bio Sketch:

Justin Romberg is the Schlumberger Professor in the School of Electrical and Computer Engineering at the Georgia Institute of Technology.

Dr. Romberg received the B.S.E.E. (1997), M.S. (1999) and Ph.D. (2004) degrees from Rice University in Houston, Texas; in 2010, he was named a Rice University Outstanding Young Engineering Alumnus. From Fall 2003 until Fall 2006, he was a Postdoctoral Scholar in Applied and Computational Mathematics at the California Institute of Technology. Justin Romberg has been on the faculty at the Georgia Institute of Technology since 2006 where he is the Schlumberger Professor in the School of Electrical and Computer Engineering. He is currently on the editorial board for the SIAM Journal on Imaging Science.