Georgia Institute of Technology, USA
Convex Programming for Non-Convex Problems
Wednesday, 13 June
10:30 – 11:30
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.
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.