Embedded Files
IMPA - 06/01/2020 a 28/02/2020
IMPA - 06/01/2020 a 28/02/2020
News
News
Exam 2 is available. We will discuss it in class on Feb 26th.
Notes on compressed sensing.
The notes on generic chaining have been updated. Our second and final assignment consists of the exercises in these notes (including the new section at the end).
The final exam will be a take-home. More info below.
Please fill out the questionnaire about our final exam.
Feb 5th 2025: no class, but please check my notes on generic chaining. The exercises there are going to be part of your next HW assignment.
Exam 1 is available here. I will be available on Jan 29th from 12PM to 1PM in room 408 to answer questions.
The material in this page is being translated into English.
General information
General information
Professor: Roberto Imbuzeiro Oliveira
TA: Leonardo Voltarelli
Lectures: Tuesdays, Wednesdays and Thursdays from 15:00 + epsilon to 17:00 + epsilon in room 347 in IMPA
Meetings with TA: Tuesdays at 13:00 in room 347 in IMPA.
Syllabus: https://impa.br/ensino/programas-de-formacao/doutorado/disciplinas-doutorado/probabilidade-em-dimensao-alta-e-aplicacoes-estatisticas/ (this is the official syllabus, but we will not follow it precisely. Rather, we will follow Vershynin's book quite closely.)
What is this course about? Who is it for?
What is this course about? Who is it for?
We will follow High Dimensional Probability by Roman Vershynin fairly closely.
This course is geared towards MSc and PhD students in Mathematics and related areas who are very familiar with mathematical proofs. The only formal prerequisite is a Measure and Integration class + the basic definitions of Probability (such as independence). More experience will be quite helpful, and may be necessary for some/most.
Avaliação e acompanhamento
Avaliação e acompanhamento
Assignments: there will be two assigments, each with two parts
Exams: first exam is a take home due on Jan 30th. The second exam is also a take-home and is due on Feb 28th at 23:59.
Letter grade will be computed from the average numerical grades in the exams (0.6) and assignments (0.4).
All of the above is subject to change!
Topics covered
Topics covered
07/01/2025 to 09/01/2025 - Johnson-Lindenstrauss (Chapter 2 in the linked notes). Höffding and Chernoff bounds (you can follow the same notes; see Chap 4); application to degrees in the Erdös-Rényi random graph; Orlicz spaces and their norms; sub-Gaussian and sub-exponential random variables. We have essentially covered all of Chapter 2, except for Bernstein's inequality (but feel free to study the whole chapter!).
14/01/2025 to 16/01/2025 - a brief tour through most of Chapter 3 (except for the Grothendieck part). Community detection and matrix concentration (here are some notes undergoing translation).
21/01/2025 to 24/01/2025 - SDP methods for coomunity detection (see the above notes). Proof of Grothendieck's inequality via Rietz's method (from this paper by Alon and Naor). Gaussian concentration inequality via the smart path method (Proposition 4 in these notes by Tao).
28/01/2025 to 30/01/2025 - No classes due to Exam 1. Office hours on Jan 29th from 12PM to 1PM in office 408.
03/02/2025 to 05/02/2025 - Gaussian processes and their intrinsic (pseudo)metrics. Slepian and Sudakov-Fernique comparison inequalities. Application to the norm of a Gaussian random matrices. Sudakov's lower bound in terms of packing numbers. Covering numbers and Dudley's integral. No class on 05/02, but there is some reading material on generic chaining here. See Vershynin's book: sections 7.1 to 7.4 and 8.1.
10/02/2025 to 12/02/2025 - A bit more on generic chaining. VC dimension and its relationship to suprema of empirical processes of Boolean functions. Vershynin, Sections 8.3 and 8.4; also, see notes for lower bound for infinite VC dimension.
Last two weeks - Deviations of random matrices and high-dimensional recovery problems and compressed sensing. A rushed proof of Dvoretsky-Milman following Ledoux, The Concentration of Measure Phenomenon (Chapter 3) and Matousek, Lectures on Discrete Geometry. See also notes on compressed sensing and Vershynin, Chapter 9 up to and including 9.4.1; Chapter 10 up to 10.3.
Assignments and exams
Assignments and exams
Assignment 1, part 1 - to be turned in to the TA by 28/01/2025: Vershynin, Chapter 2, exercises 2.2.9,2.5.10,2.6.5, 2.7.3.
Assignment 1, part 2 - to be turned in to the TA by 28/01/2025: Vershynin, Chapter 3, exercises 3.1.4 and 3.1.6.
Exam 1 (take home - to be turned in by 30/01/2025)
Assignment 2 - to be turned in to the TA by 26/02/2025: see the exercises in the (updated) notes on generic chaining.
Google Sites
Report abuse