This talks discusses moments based convex relaxations of semi-algebraic optimization problems arising in three closely related fields: identification of switched systems, manifold embedding of dynamic data and semi-supervised learning. As we will show in this talk, all of these problems are equivalent to minimizing the rank of a matrix that depends polynomially on the data. While in principle this is a hard non-convex problem, the use of moments based ideas allows for reducing it to a structured principal component decomposition: decomposing a matrix as a sum of structured low-rank and sparse components. In turn, this problem can be very efficiently solved using Augmented Lagrangian methods. In particular, we will discuss the use of Alternating Directions Method of Multipliers (ADMM), which in this case requires performing only a sequence of singular value decomposition and thresholding operations. Finally, we will cover some recent results providing explicit upper bounds on the order of the moments based relaxation guaranteeing that it is equivalent to the original non-convex problem. In the second portion of the talk we will present a practical application of these results to problems that involve extracting actionable information from very large data streams, including genomic and video data segmentation, contextually abnormal activity detection and tracking in crowded scenarios.
Copyright. All Rights Reserved.