Metric entropy is defined as the logarithm of the minimum covering number of a compact set by balls of very small radius. In this series of lectures, we will provide an overview of various available techniques and significant applications to theory of approximation, machine learning, data compression,probability and statistics.

All talks are accessible to graduate students in any areas of mathematics.

This lecture series is a survey of greedy approximation methods for nonlinear sparse approximation of functions.

Lecture 1: Structured Random Matrices in Compressive Sensing (School of Mathematics Colloquium)
Thursday, March 8, 3:30 p.m., Room 16, Vincent Hall

Compressive sensing is concerned with the recovery of sparse vectors from incomplete linear information via efficient algorithms. It is well-known that Gaussian random matrices provide optimal measurement matrices in this context. From an application point of view such completely unstructured matrices are, however, of limited use. Indeed, structure allows to model physically meaningful information acquisition processes, and also allows fast matrix-vector multiplication which helps in speeding up recovery algorithms such as l1-minimization. In this talk I will report on two types of structured random matrices. Partial random circulant matrices describe subsampled random convolutions. I will present sparse recovery results for these, and in particular, recent estimates for their restricted isometry constants. The corresponding analysis uses a new generic chaining type bound for chaos processes. Furthermore, I will discuss a structured random matrix arising in radar imaging. The randomness comes from placing antenna elements at random locations on a square aperture. The difficulty in the corresponding analysis lies in the fact that neither the columns nor the rows of this matrix are independent.

Lecture 2: Restricted Isometry Properties of Random Matrices
Friday, March 9, 1:30 p.m., Room 305, Lind Hall

I will discuss techniques for proving the restricted isometry property for certain classes of random matrices, including Gaussian and Bernoulli matrices. Depending on interest, I will also cover random partial Fourier matrices and/or partial random circulant matrices.

We will discuss techniques for approximating a point in high-dimensional Euclidean space which is close to a known low-dimensional compact submanifold when only a compressed linear sketch of the point is available. More specifically, given a point, x, in R^D we will consider linear measurement operators, M: R^D -> R^m, which have associated nonlinear inverses, A: R^m -> R^D, so that || x - A(Mx) || is small even when m << D. Both the design of good linear operators, M, and the design of stable nonlinear inverses, A, will be discussed. More specifically, an algorithmic implementation a particular nonlinear inverse will be presented, along with related stability bounds for the approximation of manifold data.

Lecture 1, Tuesday, March 20, 2012, 1:30-2:30pm, Room 305 Lind Hall

The lecture will have two parts. The first part will give a brief overview of machine learning (ML), including a discussion on some of the key problems the community focuses on solving. In this context, we will briefly discuss support vector machine (SVMs) and kernel methods. The second part will focus on probabilistic graphical models with a brief discussion of the progress so far, some applications, and some key themes currently being explored by the community.

The lecture provides background material to the IMA workshop talks by Alex Smola (Yahoo) on Monday, 3/26, and by Corinna Cortes (Google) on Thursday, 3/29 .

Lecture 2, Thursday, March 22, 2012, 1:30-2:30pm, Room 305 Lind Hall

The primary theme of the lecture will be high-dimensional problems. The lecture will have two parts. The first part will focus on consistency of high-dimensional modeling, with focus on regression especially when the number of samples is smaller than the number of dimensions, which is the case for several modern problems. The analysis will be connected to structure learning problems in graphical models (lecture 1). The second ill focus on large scale optimization, which emphasis on non-smooth and online optimization problems. Such optimization methods form a key part of learning in a wide variety of models.

The lecture will provide background material to the IMA workshop talks, including the one given by Steven Wright on Tuesday, 3/27.

The talk will provide a survey of recent developments in statistical analysis of high-dimensional data, where the number of parameters is much larger than the number of experimental units. Areas of application include image analysis, microarray analysis, finance, document classification, astronomy, atmospheric science, among others. The talk will be accessible for graduate students with background in mathematics or statistics.

The theory of compressed sensing considers the following problem: Let A ∈ C ^mxn and let x ∈ Cⁿ be s-sparse, i.e., x_i = 0 for all but s indices i. One seeks to recover x uniquely and effciently from linear measurements y = Ax, although m ‹‹ n. A sufficient condition to ensure that this is possible is the Restricted Isometry Property (RIP). A is said to have the RIP, if its restriction to any small subset of the columns acts almost like an isometry.

In this talk, we study two classes of matrices with respect to the RIP: First, we consider matrices A which represent the convolution with a random vector followed by a restriction to an arbitrary fixed set of entries. We focus on the scenario that ∈is a Rademacher vector, i.e., a vector whose entries are independent random signs. Second, we study Gabor synthesis matrices, that is, matrices consisting of time-frequency shifts of a Rademacher vector.

This is joint work with Shahar Mendelson and Holger Rauhut.

Information passing through social interactions in moving animal groups, such as bird flocks and fish schools, is credited both with improving group responsiveness to external environmental stimuli and with maintaining group cohesiveness in the presence of uncertainty. Agent-based dynamical models with interaction terms that enable information diffusion have been used successfully to reproduce a range of observed collective motions. I will discuss analytic approaches for examining group decision making and exploring group robustness to uncertainty. Of particular interest is the role of the topology of the interconnections among individuals on the emergent outcomes and performance at the level of the group.

Dr. Ehrich Leonard will also be delivering the IMA Public Lecture in the evening.

TBA

Dr. Wigderson will be delivering the IMA Public Lecture in the evening.