Title:  Separable convex optimization problem with overlapping variable : Algorithms and applications

Committee: 

Dr. Romberg, Advisor   

Dr. Wardi, Chair

Dr. Davenport

Abstract:

The objective of the proposed research is to develop a  decentralized framework that advances the role of optimization in real-time data processing and decision making by exploiting the underlying local structure in the space-time domain. In particular, we consider problems that can be decomposed into chunks that are only weakly connected.  We identify two cases of interest where this phenomenon occurs: spatial coupling and temporal coupling.  Indeed, many of our optimization programs are of this form—can be broken into overlapping elements that share variables locally. Some famous examples include signal/image recovery, (un)supervised learning,  inference, predictive control. We have developed in recent work decentralized algorithms for spatially loosely coupled problems based on the Jacobi algorithm and ADMM algorithm. In other recent work, we have demonstrated how the temporal coupling can be exploited to establish bounds on the updates to earlier solutions as a new component added to the objective and lead to a design of new efficient Newton-based solver. We propose to extend this result in two steps—the first step is designing a distributed Newton-based algorithm. The second step, develop a distributed Newton-based algorithm that draws on the former but is also capable of solving spatiotemporal problems in a streaming fashion. To demonstrate the contribution of our proposed approach, we will implement it on selected fundamental problems from in signal processing and related domains. These will include, among others, signal reconstruction from nonuniform samples, simultaneous localization, and mapping(SLAM), and several examples of non-homogeneous Poisson process regression.