Fortgeschrittene Themen der Funktionalanalysis (5 LP)
Random Matrices and Matrix Completion - TU Berlin - 2016
Random matrix theory studies properties of random matrices, chosen from some distribution on the set
of all matrices of fixed dimension. The asymptotic regime (when the dimensions of the random matrices tend
to infinity) was studied in connection with statistical physics. Nevertheless,
recent developments in theoretical computer science motivated also detailed study of the non-asymptotic regime,
where the dimensions of random matrices are fixed.
After the success of methods of recovery of sparse vectors from random measurements developped in the frame of compressed
sensing, new methods of recovery of low-rank matrices from small number of random measurements were introduces in the last decade.
Such problems are nowadays of big importance in many fields. For example, recommendation systems of online shops
try to predict user's interest in new products from a limited number of user's product ratings. Assuming by experience
that the full (but unreachable) matrix of ratings of all products by all user's is of (approximately) low rank,
this task reduces into a quest of completing a low-rank matrix from few observed entries. This problem was popularized
by the Netflix Prize.
The lecture will take place in the week September 26 - 30, 2016 at Technical University Berlin.
It will consist of a series of 10 lectures, 90 minutes long. We shall meet two times a day, at 10am and 2pm at MA 313.
The material presented will include
The course assumes basic knowledge of statistics (random variables, independence) and linear algebra (spectrum of a matrix, adjoint matrix, operator norm, trace).
- Introduction to randomness: concentration of measure, Lemma of Johnson and Lindenstrauss
- Low-rank matrix recovery: Rank r-Null space property, Rank r-Restricted isometry property, Gaussian information map
- Random matrices: Matrix norms, Golden-Thompson inequality, Non-commutative Bernstein inequality, Lieb's theorem
- Matrix Completion: Recovery of a low-rank matrix from few observed entries
I am preparing lecture notes. A preliminary version can be downloaded here (version: October 3, 2016).
I plan to come back to Berlin
for exams later in the autumn 2016, otherwise you can arrange your exam with Prof. Kutyniok.
Passing the exam gives 5 Leistungspunkte (LP) according to ECTS.
Roman Vershynin, Introduction to the non-asymptotic analysis of random matrices, 2011
Joel Tropp, User-friendly tail bounds for sums of random matrices, 2012
Joel Tropp, An Introduction to Matrix Concentration Inequalities, 2015
Terence Tao, Topics in Random Matrix Theory, AMS, 2012