A Caltech Library Service

Convex Optimization Methods for Graphs and Statistical Modeling

Chandrasekaran, Venkat (2011) Convex Optimization Methods for Graphs and Statistical Modeling. PhD thesis, Massachusetts Institute of Technology.

PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 low-rank matrix into the individual components. Based on new rank-sparsity 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 high-dimensional 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 low-rank 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 FA9550-06-1-0324, MURI AFOSR grant FA9550-06-1-0303, NSF FRG 0757207, AFOSR grant FA9550-08-1-0180, and MURI ARO grant W911NF-06-1-0076.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR) Multidisciplinary University Research Initiative (MURI)FA9550-06-1-0324
Air Force Office of Scientific Research (AFOSR) Multidisciplinary University Research Initiative (MURI)FA9550-06-1-0303
NSFFRG 0757207
Air Force Office of Scientific Research (AFOSR)FA9550-08-1-0180
Army Research Office (ARO) Multidisciplinary University Research Initiative (MURI)W911NF-06-1-0076
Record Number:CaltechAUTHORS:20121008-130644748
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34757
Deposited By: Tony Diaz
Deposited On:08 Oct 2012 20:48
Last Modified:03 Oct 2019 04:22

Repository Staff Only: item control page