Statistics of slow mixing Markov processes with applications to community
Date: Fri, October 25, 2019
Time: 11:30am - 1:00pm
Location: Holmes Hall 244
Speaker: Narayana Prasad Santhanam, Associate Professor, UH EE
Sponsored by College of Engineering Professors and Pizza series
•Ph.D., University of California, San Diego, 2006
•M.S., University of California, San Diego, 2003
•BTech, India Institute of Technology, Chennai, (then Madras), 2000
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
Abstract:
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. This is joint work with my past and current students (M. Asadi, R. Paravi, M. Hosseini and C. Wu).