My research interests include applications of graphical models, machine learning, probability theory and statistical physics in:
Selected Projects (for a complete list click here)
Data-Driven Decision Making in Healthcare
Summary: Rehospitalization -patient admission to a hospital soon after the discharge- is both common and costly. Nearly one in every five
patients is readmitted to the hospital within 30 days of their discharge. The estimated cost of unplanned rehospitalizations to
Medicare in 2004 was around $17.4 billion. Research shows that hospital initiatives such as: patient education programs, follow-up home
visits by pharmacists, extensive discharge packages, etc., can avert many rehospitalizations. However, proper allocation of these
costly and limited resources is a challenging problem. In this project, we use machine learning and optimization tools for identifying
patients with highest risk of being rehospitalized and obtain a decision support mechanism for allocating scarce resources to post-discharge support.
Graphical Models, Approximate Message Passing, and Statistical Learning
Summary: Recently, Donoho, Maleki and Montanari introduced
approximate message passing (AMP) as an extremely effective algorithm for
reconstructing high dimensional sparse signals from a small number of observations.
They also showed (through extensive numerical experiments) that dynamics of AMP is accurately
tracked by a simple one-dimensional iteration termed "state evolution". In these papers we provided the first
rigorous foundation to state evolution. We proved that indeed it holds asymptotically in the large system
limit for sensing matrices with i.i.d. gaussian entries. Our techniques also provide a new approach
for the analysis of message-passing algorithms on dense graphs.
Modeling of Large Networks with Given Constraints
Summary: A central hurdle in working with large networks is the lack of good random graph models that capture their specific properties. Such random graph models can be useful for example in simulating algorithms for the Internet or detecting motifs (patterns) in biological systems. Unfortunately, the existing algorithms for generating random graphs with given degrees have large running times (quadratic on problem size), making them impractical to use for networks with millions of nodes. In this paper we designed the fastest (almost linear running time) algorithm and proved its correctness when the node degrees are in certain range. Recently, with Andrea Montanari and Amin Saberi, we extended that algorithm to design an efficient algorithm for generating random graphs with no short cycles that appeared in SODA 2009. These graphs are used to construct high performance codes that can achieve the Shannon capacity.
Belief Propagation Algorithm for Distributed Optimization: Theory and Applications
Belief propagation (BP) is a distributed algorithm that has been very successfully used in many areas including
machine learning and optimization. Despite its spectacular success, the
BP algorithm is known to be correct only in cycle-free networks. However, in practice, the (loopy) BP algorithm
works rather well in networks that have many cycles. In these papers we used BP algorithm for solving the well-known
maximum weight matchings (MWM) problem. We proved that BP solves this problem correctly on all graphs when the
linear programming (LP) relaxation of the problem has integer solutions. We also proved that BP and LP are
equivalent for finding MWM. The proof technique gives a better understanding of the often noted,
but poorly understood connection between BP and LP.
Fast Algorithms for Aligning Large Networks