In many applications, we face the challenge of modeling the interactions between multiple observations. A popular and successful approach in machine learning and AI is to hypothesize the existence of certain latent (or hidden) causes which help to explain the correlations in the observed data. The (unsupervised) learning problem is to accurately estimate a model with only samples of the observed variables. For example, in document modeling, we may wish to characterize the correlational structure of the "bag of words" in documents, or in community detection, we wish to discover the communities of individuals in social networks. Here, a standard model is to posit that documents are about a few topics (the hidden variables) and that each active topic determines the occurrence of words in the document. The learning problem is, using only the observed words in the documents (and not the hidden topics), to estimate the topic probability vectors (i.e. discover the strength by which words tend to appear under different topcis). In practice, a broad class of latent variable models is most often fit with either local search heuristics (such as the EM algorithm) or sampling based approaches.This talk will discuss a general and (computationally and statistically) efficient parameter estimation method for a wide class of latent variable models---including Gaussian mixture models (for clustering), hidden Markov models (for time series), and latent Dirichlet allocation (for topic modeling and community detection) ---by exploiting a certain tensor structure in their low-order observable moments. Specifically, parameter estimation is reduced to the problem of extracting a certain decomposition of a tensor derived from the (typically second- and third-order) moments; this particular decomposition can be viewed as a natural generalization of the (widely used) principal component analysis method.

Detecting or estimating a dense community from a network graph offers a rich set of problems involving the interplay of algorithms, complexity, and information limits. This talk will present an overview and recent results on this topic.Based on joint work with Yihong Wu and Jiaming Xu.

Recently, much attention is paid to the finite length analysis of the basic problems such as source coding and channel coding. In this talk we first summarize the information-spectrum approach to this kind of problems (called the second-order information theory) such as source coding, resolvability, intrinsic randomness, hypothesis testing, channel coding in a unified framework. In particular, special emphasis is addressed to the class of mixed sources and mixed channels that are defined to be the general mixture of stationary memoryless sources and the general mixture of stationary memoryless channels, respectively.Although it is generally quite hard to give single-letter characterizations to the formulas for general sources and general channels, it is shown that we can successfully derive the compact single-letter characterizations to the class of mixed sources/channels. In particular, we give the detailed proof for the second-order theorem on hypothesis testing with mixed sources.

In this talk, we will discuss a new class of models and techniques that can effectively model and extract rich low-dimensional structures in high-dimensional data such as images and videos, despite nonlinear transformation, gross corruption, or severely compressed measurements. This work leverages recent advancements in convex optimization for recovering low-rank or sparse signals that provide both strong theoretical guarantees and efficient and scalable algorithms for solving such high-dimensional combinatorial problems. These results and tools actually generalize to a large family of low-complexity structures whose associated regularizers are decomposable. We illustrate how these new mathematical models and tools could bring disruptive changes to solutions to many challenging tasks in computer vision, image processing, and pattern recognition. We will also illustrate some emerging applications of these tools to other data types such as web documents, image tags, microarray data, audio/music analysis, and learning graphical (neural network) models.This is joint work with John Wright of Columbia, Emmanuel Candes of Stanford, Zhouchen Lin of Peking University, and my students Zhengdong Zhang, Xiao Liang of Tsinghua University, Arvind Ganesh, Zihan Zhou, Kerui Min and Hossein Mobahi of UIUC