Chandrasekaran, Venkat (2011) Convex Optimization Methods for Graphs and Statistical Modeling. PhD thesis, Massachusetts Institute of Technology. http://resolver.caltech.edu/CaltechAUTHORS:20121008130644748

PDF
 Accepted Version
See Usage Policy. 1401Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20121008130644748
Abstract
An outstanding challenge in many problems throughout science and engineering is to succinctly characterize the relationships among a large number of interacting entities. Models based on graphs form one major thrust in this thesis, as graphs often provide a concise representation of the interactions among a large set of variables. A second major emphasis of this thesis are classes of structured models that satisfy certain algebraic constraints. The common theme underlying these approaches is the development of computational methods based on convex optimization, which are in turn useful in a broad array of problems in signal processing and machine learning. The specific contributions are as follows: We propose a convex optimization method for decomposing the sum of a sparse matrix and a lowrank matrix into the individual components. Based on new ranksparsity uncertainty principles, we give conditions under which the convex program exactly recovers the underlying components. Building on the previous point, we describe a convex optimization approach to latent variable Gaussian graphical model selection. We provide theoretical guarantees of the statistical consistency of this convex program in the highdimensional scaling regime in which the number of latent/observed variables grows with the number of samples of the observed variables. The algebraic varieties of sparse and lowrank matrices play a prominent role in this analysis. We present a general convex optimization formulation for linear inverse problems, in which we have limited measurements in the form of linear functionals of a signal or model of interest. When these underlying models have algebraic structure, the resulting convex programs can be solved exactly or approximately via semidefinite programming. We provide sharp estimates (based on computing certain Gaussian statistics related to the underlying model geometry) of the number of generic linear measurements required for exact and robust recovery in a variety of settings. We present convex graph invariants, which are invariants of a graph that are convex functions of the underlying adjacency matrix. Graph invariants characterize structural properties of a graph that do not depend on the labeling of the nodes; convex graph invariants constitute an important subclass, and they provide a systematic and unified computational framework based on convex optimization for solving a number of interesting graph problems. We emphasize a unified view of the underlying convex geometry common to these different frameworks. We describe applications of these methods to problems in financial modeling and network analysis, and conclude with a discussion of directions for future research.
Item Type:  Thesis (PhD)  

Additional Information:  This research was supported in part by the following grants  MURI AFOSR grant FA95500610324, MURI AFOSR grant FA95500610303, NSF FRG 0757207, AFOSR grant FA95500810180, and MURI ARO grant W911NF0610076.  
Funders: 
 
Record Number:  CaltechAUTHORS:20121008130644748  
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:20121008130644748  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  34757  
Collection:  CaltechAUTHORS  
Deposited By:  Tony Diaz  
Deposited On:  08 Oct 2012 20:48  
Last Modified:  27 Dec 2012 02:49 
Repository Staff Only: item control page