High-dimensional data analysis
Fall 2026
High-dimensional data analysis
Fall 2026
Basic Information
Instructor: Aditya Potukuchi
Time: Thursday (Donnerstag) 14:00-15:30, in room TBA
Office: MPI-SWS 214
Grading: 4-5 problem sets, written exam.
Main textbook: Foundations of data science
PROBLEM SETS
Course outline: This course is intended for a very basic probabilistic/geometric/information-theoretic perspective on understanding large unstructured data. The structure of the course that of a basic applied linear algebra and probability "toolkit" course, and the use of these tools extends far beyond the context into much of science. These tools naturally suggest algorithms at several points along the way, which we will study. If time permits, I will include one quite ingenious and tactful application of some subset of these ideas in a slightly larger context of algorithm design. The planned list of topcs we cover is
1. Intro to linear algebra and basic spectral analysis
- basic linear algebra, linear transforms, rank, basic ``toolkit'' results
- SVD - analysis and algorithms
- PCA - analysis and algorithms (and also experiments?)
2. Motivation and intro to probability
- intro to probability and some basic ``toolkit'' results
- basic quantitative reasoning, asymptotic notation, growth-rate of functions
- CountMin sketch, or other hash/sketch/etc.. results
3. Intro to dimensionality reduction
- norms, law of large numbers, volume of unit ball
- concentration and and Johnson-Lindenstrauss lemma
4. More refined spectral and probabilistic analysis
- basic spectral graph theory, expansion
- clustering - analysis and algorithms for community detection on the stochastic block model
- intro to Markov chains and spectral analysis of MC's
- some algorithm using all the above - clear candidate is convex volume, but I am open to whichever fits best in the moment.
Schedule
Oct 29: Motivation and linear algebraic background review/crash course.