Beginning Lecture Course - week 1
Title: Methods for sparse analysis of high-dimensional data, I
Lecturer: Becca Wilett, Duke University
Teaching Assistant:Kalyani Krishnamurthy, Duke University
Course Description: This mini-course will cover fundamental aspects of estimating a function (e.g., a communication signal, medical image, surveillance video, or social network interaction model) from error-corrupted data. We will see how the "curse of dimensionality" limits our ability to control the estimation error in general settings. However, when the function of interest admits a sparse representation, we can exploit this sparsity to achieve significantly higher estimation accuracy. This course will describe various sparse representations of functions and data, methods for computing sparse estimates from noisy or error-riddled observations, and the role of sparsity in fundamental performance limits. In particular, we will examine recent work in compressed sensing, low-rank matrix completion, sparse covariance matrix estimation, and manifold learning.
Pre-requisites: Intro to linear algebra
References: A wavelet tour of signal processing, third edition: The sparse way by Stephane Mallat
Sparse and redundant representations: From theory to applications in signal and image processing by Michael Elad
Advanced Lecture Course - week 1
Title: Sublinear-time algorithms
Lecturer: Sofya Raskhodnikova, Penn State University
Teaching Assistant:Shubhangi Saraf, MIT
Course Description: The course will cover the design and analysis of algorithms that are restricted to run in sublinear time. Such algorithms are typically randomized and produce only approximate answers. A characteristic feature of sublinear algorithms is that they do not have time to access the entire input. Therefore, input representation and the model for accessing the input play an important role. We will study different models appropriate for sublinear algorithms. The course will cover sublinear algorithms discovered in a variety of areas, including graph theory, algebra, geometry, image analysis and discrete mathematics, and introduce many techniques that are applied to analyzing sublinear algorithms.
Pre-requisites: a course on the analysis of algorithms would be very helpful; familiarity with asymptotic notation is required.
References: http://www.eng.tau.ac.il/~danar/TOP06/index.htm
http://people.csail.mit.edu/ronitt/COURSE/S07/index.html
http://stellar.mit.edu/S/course/6/fa10/6.896/
Beginning Lecture Course - week 2
Title: Methods for sparse analysis of high-dimensional data, II
Lecturer: Rachel Ward, New York University
Teaching Assistant: Sarah Constantin, Yale University
Course Description: Massive data sets are all around us; often, however, the high-dimensional data is well-parametrized by only a few (known or unknown) variables. Embedding such data into lower dimensions is important for reducing storage cost and speeding up computation in several applications. We will discuss methods for dimensionality reduction using random linear projections. We will then discuss the application of fast decoding algorithms to reconstruct the data from their lower-dimensional projections. Finally, we will focus on the use of random projections in numerical linear algebra for speeding up high-dimensional matrix computations.
Pre-requisites: Linear algebra and probability (necessary) and a semester of real analysis (preferred)
Advanced Lecture Course - week 2
Title: Algorithms for sparse analysis
Lecturer:Anna Gilbert, University of Michigan
Teaching Assistant: Mary Wootters, University of Michigan
Course Description: The past 10 years have seen a confluence of research in sparse approximation amongst computer science, mathematics, and electrical engineering. Sparse approximation encompasses a large number of mathematical, algorithmic, and signal processing problems which all attempt to balance the size of a (linear) representation of data and the fidelity of that representation. I will discuss several of the basic algorithmic problems (Lecture 1), their hardness or rigorous analysis of the complexity of these problems (Lecture 2), and algorithms for their (approximate) solutions (Lectures 3 and 4). These algorithms include two main paradigms: convex optimization and greedy algorithms. I will include along the way applications in signal processing and more theoretical aspects of computer science.