For many computational problems, it is beneficial to see them through the prism of high-dimensional geometry. For example, one can represent an object (e.g., an image) as a high-dimensional vector, depicting hundreds or more features (e.g., pixels). Often direct or classical solutions to such problems suffer from the so-called "curse of dimensionality": the performance guarantees tend to have exponential dependence on the dimension. Modern tools from high-dimensional computational geometry address this obstacle.

These lectures will give an overview of some key problems and tools in the area, including nearest neighbor search, dimensionality reduction, embeddings and intrinsic dimension, and may touch upon some connections to related areas, such as sublinear algorithms.

The second session of this talk will take place on Wednesday, September 4 from 9:00 am – 10:30 am.

Random matrices have come to play a significant role in computational mathematics and statistics. Established methods from random matrix theory have led to striking advances in these areas, but ongoing research has generated difficult questions that cannot be addressed without new tools. The purpose of this tutorial is to introduce some recent techniques, collectively called matrix concentration inequalities, that can simplify the study of many types of random matrices. These results parallel classical tail bounds for scalar random variables, such as the Bernstein inequality, but they apply directly to matrices. In particular, matrix concentration inequalities can be used to control the spectral norm of a sum of independent random matrices by harnessing basic properties of the summands. Many variants and extensions are now available, and the outlines of a larger theory are starting to emerge. These new techniques have already led to advances in many areas, including partial covariance estimation, randomized schemes for low-rank matrix decomposition, relaxation and rounding methods for combinatorial optimization, construction of maps for dimensionality reduction, techniques for subsampling large matrices, analysis of sparse approximation algorithms, and many others.

The first session of this talk will take place on Tuesday, September 3 from 2:00 pm – 3:00 pm; the third session of this talk will take place on Tuesday, September 3 from 4:30 pm – 5:30 pm.

Relevant Papers

J. A. Tropp, "User-Friendly Tools for Random Matrices: An Introduction", 2012. Available at users.cms.caltech.edu/~jtropp/notes/Tro12-User-Friendly-Tools-NIPS.pdf
J. A. Tropp, "User-Friendly Tail Bounds for Sums of Random Matrices", FOCM 2012. Available at users.cms.caltech.edu/~jtropp/papers/Tro12-User-Friendly-FOCM.pdf
L. Mackey et al., "Matrix concentration inequalities via the method of exchangeable pairs," 2012. Available at users.cms.caltech.edu/~jtropp/papers/MJCFT12-Matrix-Concentration.pdf

The introduction of randomization over the last decade into the design and analysis of algorithms for matrix computations has provided a new paradigm, particularly appropriate for many very large-scale applications, as well as a complementary perspective to traditional numerical linear algebra approaches to matrix computations. These novel approaches have been motivated by technological developments in many application areas that permit the automatic generation of large data sets, and they are of particular interest for large-scale data analysis since many data sets are naturally modeled as matrices.

This tutorial will describe the theory underlying randomized algorithms for matrix problems (such as matrix multiplication, least-squares regression, least absolute deviations regression, and low-rank matrix approximation) as well as where that theory is headed. Although the use of randomization is sometimes a relatively-straightforward application of Johnson-Lindenstrauss ideas, Euclidean spaces are much more structured objects than general metric spaces, and thus the best—both in theory and in numerical analysis and data analysis practice—randomized matrix algorithms take this into account. An emphasis will be placed on highlighting a few key concepts, several of which have natural statistical interpretations, that are responsible for the improvements in worst case theory and also for the usefulness of these algorithms in large-scale numerical and data applications.

The second session of this talk will take place on Wednesday, September 4 from 2:00 pm – 3:30 pm.

The area of high-dimensional statistics concerns problems in which the ambient dimension is of the same order or substantially larger than the sample size. Although its roots are classical (dating back to Kolmogorov), it has become the focus of increasing attention in the modern era of big data. In this tutorial lecture, we survey some recent progress in different areas, including sparse estimation, covariance estimation, low-rank matrix recovery, graphical model selection, and non-parametric regression, with emphasis on the techniques used to obtain non-asymptotic results.

The second session of this talk will take place on Thursday, September 5 from 2:00 pm – 3:30 pm.

Why is it that graphs play such a key role in a essentially all applications of mathematics to real-life problems? The main reason is that there are so many situations in natural sciences/engineering/social sciences and more where we are trying to understand a complex system that consists of interacting pairs. These can be molecules in some biological system or two companies engaged in a business transaction etc. But what do you do when the underlying interactions may involve more than two parties? We are currently much less prepared to deal with such problems. It is natural to introduce into the game higher-dimensional simplicial complexes (a graph is a one-dimensional simplicial complex). This leads us into a fascinating set of problems and challenges, some of which already resolved and many still widely open. As it turns out graphs are just one example where a basic combinatorial object is inherently one-dimensional and where higher-dimensional counterparts suggest themselves. I will introduce recent work on high-dimensional permutations and tournaments.

These lectures are based on joint papers with several coauthors, e.g.

• http://arxiv.org/abs/1010.1400
• http://arxiv.org/abs/0903.1359
• http://arxiv.org/abs/1106.0649
• http://arxiv.org/abs/1108.5042
• http://arxiv.org/abs/1203.3312
• http://arxiv.org/abs/1208.4218
• http://arxiv.org/abs/1302.1684
• http://arxiv.org/abs/1307.2684

​The second session of this talk will take place on Friday, September 6 from 2:00 pm – 3:30 pm.