Statistics of slow mixing Markov processes with applications to community detection

ECE Seminar: Statistics of slow mixing Markov processes with applications to community detection

Starts at: September 17, 2015 4:30 PM

Ends at: 6:00 PM

Location: Scaife 125

Speaker: Dr. Narayana Santhanam

Affiliation: University of Hawaii

Refreshments provided: Yes

Link to Poster

Link to Video (1)


Empirical observations from finite sized samples from Markov processes do not always yield stationary properties. For example, a string's frequency in a finite Markov sample need not in any way reflect its stationary probability. When the samples eventually does reflect the stationary properties, we say that the process has mixed. The core ideas in this talk revolve around interpretation of samples before mixing has occured. In particular, we highlight the "surprises" lurking in this regime relative to the more common, folk wisdom obtained from the stationary regime. Naturally then, to build clustering and community detection algorithms on graphs we build Markov random walks such that the restriction of the random walk to within any one cluster mixes much faster than the overall walk itself. A careful interpretation of samples from the random walk using algorithmic primitives based on coupling then reveals the community structure of the graph.

Narayana Santhanam has been with the University of Hawaii since 2009, and is currently an Associate Professor in the Department of Electrical Engineering. He obtained his B.Tech from the Indian Institute of Technology, Chennai (then Madras) in 2000; MS and PhD from the University of California, San Diego in 2003 and 2006 respectively. From 2007-2008, he held a postdoctoral position at the University of California, Berkeley. His research interests lie in the intersection of information theory and statistics, with a focus on the undersampled/high dimensional regime and including applications to finance, biology, communication and estimation theory. He is the recipient of the 2006 Information Theory Best Paper award from the IEEE Information Theory Society along with A. Orlitsky and J. Zhang; as well as the organizer of several workshops on high dimensional statistics and "big data" problems over the last five years. He is currently a member of the NSF Center for Science of Information (CSoI), a Science and Technology center, and is the core person representing University of Hawaii at the CSoI.