Fig 1. Professor Lu is giving the talk

Fig 2. Professor Lu is explaining the Random Energy Model

Professor Lu attended the University of Illinois at Urbana-Champaign, where he received the M.Sc. degree in mathematics and the Ph.D. degree in electrical engineering, both in 2007. He was a Research Assistant at the University of Illinois at Urbana-Champaign, and has worked for Microsoft Research Asia, Beijing, and Siemens Corporate Research, Princeton, NJ. From September 2007 and September 2010, he was a postdoctoral researcher at the Audiovisual Communications Laboratory at Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland. He is currently an Assistant Professor of electrical engineering at Harvard University, directing the Signals, Information, and Networks Group (SING) at the School of Engineering and Applied Sciences. His work received several awards, including the Most Innovative Paper Award of IEEE International Conference on Image Processing (ICIP) in 2006, the Best Student Paper Award of IEEE ICIP in 2007, the Best Student Presentation Award at the 31st SIAM SEAS Conference in 2007, and the Best Student Paper Award of IEEE International Conference on Acoustics, Speech and Signal Processing in 2011.

###### Title:

The Random Energy Model and Performance Bounds for Detecting Hidden Markov Processes

###### Abstract:

The random energy model (REM) is the simplest model of a disordered system that exhibits a phase transition (one-step replica symmetry breaking.) It was introduced by Derrida as the limit of a family of mean-field spin glass models, where the correlation between the energy levels become negligible. In this talk, I will describe the various ideas behind the solution of REM (microcanonical entropy densities, self-averaging, and the universality of extreme value statistics in the glass phase), and show that the very same mathematical structures appear in a host of problems in information processing. In particular, I will present our recent work on understanding the performance of detecting hidden Markov processes, a fundamental problem in statistical signal processing. The performance metric we analyze is the error exponent, which measures the optimal exponential rate of decay in the error probability as the observation time increases. This problem is simple to formulate, but exhibits deep connections to problems known to be hard, such as computing the Lyapunov exponents of products of random matrices. By interpolating between two random Hamiltonians, we show that a lower bound for the error exponent can be obtained by computing the free energy density of a generalized version of REM, which is exactly soluble by large deviations techniques. Our bound closely matches the empirical results in numerical experiments, and it suggests a second-order phase transition phenomenon in the error exponent: below a threshold SNR, the error exponent is nearly constant and near zero, indicating poor performance; above the threshold, there is rapid improvement in performance as the SNR increases. The location of the phase transition depends on the entropy rate of the Markov process. Finally, I will discuss cases where our lower bound is in fact asymptotically tight, in the limit of large state spaces of the underlying Markov processes.