THEME 1: Statistical recovery problems in high-dimensions: Some recent progress and challenges ahead

 

Abstract:

Data sets in modern engineering and science often have a high-dimensional nature, meaning that the ambient dimension may be of the same size or larger than the number of observations. Examples include gene array analysis, medical imaging, social networks, atmospheric sciences, astronomical surveys, and financial data analysis, among others. With this motivation, an on-going line of work, with contributors from machine learning, information theory, signal processing, mathematical statistics, and computer science, seeks to develop efficient methods high-dimensional recovery problems, and the corresponding theory that provides rigorous guarantees. Examples include:

• compressed sensing, where the goal is to recover sparse vectors from noisy projections,
• the inverse problem in graphical models, where the goal is to estimate the structure of an unknown network
  based on samples,
• random matrix theory and estimation of structured covariance matrices (e.g., capturing correlations among
  many financial instruments) and
• estimation of low-rank matrices, including the ”Netflix” problem and subspace tracking problems.

The goal of these lectures is to provide an overview some challenges and recent progress in this area. We begin by presenting a general framework for establishing consistency and convergence rates for estimators based on convex relaxations, and we illustrate its consequences for various specific models, We also compare such achievable rates obtained using such computationally-efficient methods to those that can be obtained using optimal procedures (whose complexity is typically exponential). This comparison shows that it is often possible to match or approach the information-theoretic limitations using polynomial-time algorithms.

Speaker Bio:

Martin Wainwright received the Bachelors degree in mathematics from University of Waterloo, Canada, and the Ph.D. degree in electrical engineering and computer science from Massachusetts Institute of Technology (MIT), Cambridge. He is currently an Associate Professor at the University of California at Berkeley, with a joint appointment between the Department of Statistics and the Department of Electrical Engineering and Computer Sciences. His research interests include statistical signal processing, coding and information theory, statistical machine learning, and high-dimensional statistics. Dr.Wainwright has been awarded an Alfred P. Sloan Foundation Fellowship, an NSF CAREER Award, the George M. Sprowls Prize for his dissertation research (EECS department, MIT), a Natural Sciences and Engineering Research Council of Canada 1967 Fellowship, an IEEE Signal Processing Society Best Paper Award in 2008, and several outstanding conference paper awards.