Catalogo dei Corsi di studio

Programma corso: il programma sara' in buona parte (ma non del  tutto) simile a quello del corso dei due anni precedenti.  Riporto il programma di massima:

DISUGUAGLIANZA DI HOEFFDING
Disuguaglianza di Hoeffiding  per v.a. di Rademacher  e per v.a. limitate. Applicazione: boosting randomized algorithms

VARIABILI ALEATORIE SUBGAUSSIANE
Variabile gaussiana standard: stima delle code,  momenti e funzione generatrice dei momenti.  Definizione di v.a. subgaussiana e caratterizzazioni equivalenti. Spazio normato  delle v.a. subgaussian. Centering. Stima della norma subgaussiana della somma di v.a. subgaussiane indipendenti a media zero.

COVERING NUMBER E PACKING NUMBER
epsilon-net e covering number,. Insieme epsilon-separato e packing number.  Equivalenza tra i covering and il packing numbers. Covering number per sottinsiemi di R^n. Stime sul covering number della palla e della sfera euclidee.

STIME DALL'ALTO DELLA NORMA DI MATRICI RANDOM SUBGAUSSIANE
Utilizzo degli epsilon-net per approssimare funzioni lipschitziani.  Stima della norma di matrici random con entrate subgaussiane,  a media zero, indipendenti.  Stima della norma di matrici simmetriche random con entrate subgaussiane,  a media zero, indipendenti su e sopra la diagonale.

TEORIA PERTURBATIVA PER MATRICI DETERMINISTICHE
 Disuguaglianza di Weyl per gli autovalori. Teorema di Davis-Kahan per gli autovettori. Corollario del Teorema di Davis-Kahan: stima della distanza tra gli autovettori sotto perturbazioni 

CLUSTERING: STOCHASTIC BLOCK MODEL
Stochastic block model. Analisi spettrale del valore atteso della matrice di adiacenza del grafo.  Spectral clustering algorithm con la matrice di adiacenza. Efficacia della spectral clustering algorithm. 

CLUSTER ANALYSIS
Cluster analysis. Dissimilarity function. Within cluster point scatter. Between-cluster point scatter.   Combinatorial clustering basato sull'elencazione delle funzioni surgettive e criticità della sua implementazione.  k-means clustering.  Similarità  e grafi pesati associati ($\epsilon$-neighborhood graph, k-nearest neighbor graph, mutual k-nearest neighbor graph, fully connected graph).  Laplaciano non normalizzato di un grafo pesato non-orientato.
Spectral clustering algorithm con il laplaciano non normalizzato (unnormalized spectral clustering.

VETTORI ALEATORI IN ALTA DIMENSIONE
Matrice di covarianza per un vettore aleatorio. Vettori aleatori  isotropi. Richiami sulle v.a. gaussiane e sui vettori aleatori gaussiani. Espressione del valore atteso del v.a. gaussiano standard con le funzione Gamma. Concentrazione della norma per vettori con entrate indipendenti, subgaussiane, momento secondo unitario  e applicazione al vettore gaussiano standard. 

MATRICI GAUSSIANE STANDARD
 Matrici gaussiane standard e loro proprietà.  Varietà grassmaniana. 

DIMENSION REDUCTION: LEMMA DI  JOHNSON-LINDENSTRAUSS
 Teorema di concentrazione per funzioni lipschitziane di un vettore aleatorio uniformemente distribuito sulla sfera. Lemma di  Johnson-Lindenstrauss per N punti.

PROCESSI  GAUSSIANI, AMPIEZZA  GAUSSIANA E SFERICA 
Processi stocastici, funzione di covarianza.   Ampiezza gaussiana e sferica   e loro confronto. Ampiezza gaussiana  di alcuni insiemi notevoli. 

STIMATORI  IN ALTA DIMENSIONE
M*-bound.  Stimatori per osservazioni lineari gaussiane senza rumore/con rumore: feasibility program e optimization program in termini del funzionale di Minkowski. Stimatori per la regressione lineare 

SPARSE RECOVERY AND EXACT SPARSE RICOVERY
 Cenni sulla sparsità nella rappresentazione wavelet di segnali e nella regressione lineare in genetica. Vettori sparsi e vettori sparsi rispetto ad un dizionario. Stimatori per osservazioni lineari gaussiane con rumore di un vettore sparso rispetto ad un dizionario.  Teorema di fuga. Exact sparse recovery. 

Si possono vedere le sezioni dedicate al corso dell'anno scorso  alla pagina: https://www1.mat.uniroma1.it/people/faggionato/didattica/dida1.html

Libri di testo: il materiale sara' preso da diverse fonti (non acquistate libri). Tratteremo 

alcune parti dei seguenti testi:

R. Vershynin. ``High-Dimensional Probability. An Introduction with Applications in Data Science". Cambridge University Press. Disponibile  online (gratuitamente).

M. J. Wainwright. ``High-Dimensional Statistics. A Non-Asymptotic Viewpoint". Cambridge University Press.

R. Vershynin, Estimation in high dimension: a geometric perspective. https://arxiv.org/pdf/1405.5103.pdf

T. Hastie, R. Tibshirani, J. Friedman. The elements of statistical learning. Springer series in Statistics. Free online

U. von Luxburg, A tutorial in spectral clustering Statistics and Computing, 17 (4), 2007 (free online)

Esami: certamete esame orale, forse anche esame scritto

Date esami: vedere la pagina del dipartimento (consiglio: in alto cliccate su Ordina per data): https://docs.google.com/spreadsheets/u/1/d/e/2PACX-1vQt4Q8_g7oiydvFHlkdF...

Ricevimento: su appuntamento

Programma corso: il programma e' diverso da quello dei due anni precedenti. In particolare non ci saranno le catene di Markov, per evitare sovrapposizioni con processi stocastici. 

Entropia: sorpresa di un evento,   entropia di una variabile aleatoria,  entropia congiunta  per  due variabili aleatorie, entropia condizionata, entropia congiunta condizionata,  distanza di Kullback-Leibler, mutua informazione, entropia relativa di misure di probabilità

Teoria dei codici: codici univocamente decodificabile, codici prefisso,  disuguaglianza di Kraft, teorema di Shannon per la stima dal basso della lunghezza media della codeword  con entropia delle sorgente, codice di Shannon-Fano, codice di Huffman come codice ottimale.

Processi stocastici ed entropia:  processi stocastici a tempo discreto, processi stocastici stazionari, tasso di entropia di un processo stocastico, esistenza del tasso di entropia per processi stocastici stazionari,.

Coupling: coupling di due misure e di due variabili aleatorie, distanza in variazione totale, teorema del maximal coupling, funzione inversa generalizzata della funzione di ripartizione, simulazione di una v.a. reale tramite la sua funzione di ripartizione e la v.a. uniforme su [0,1].

Dominazione stocastica:  dominazione stocastica di  due misure di probabilità su R, dominazione stocastica di  due v.a. reali e formulazioni equivalenti (tramite code e funzioni di ripartizioni), coupling e dominazione stocastica per v.a. reali,  coupling monotono. 

Dominazione stocastica tra v.a. binomiali, dominazione stocastica tra v.a. di Poisson, insiemi parzialmente ordinati (poset),  sottinsiemi crescenti di POSET, funzioni crescenti su POSET, dominazione stocastica per misure di probabilità su un poset, teorema di Strassen e sue implicazioni. 

Bernoulli bond percolation: probabilità di percolazione, probabilità critica, monotonia della probabilità critica rispetto alla dimensione, transizione di fase per d>1, disuguaglianza FKG e altre tecniche di base. In alternativa alla Bernoulli bond percolation saranno  trattati grafi random.

Funzione generatrice dei momenti. 

Vettori aleatori gaussiani e cenni sul moto Browniano

Per il corso dell'anno scorso, vedere la sezione dedicata alla pagina

https://www1.mat.uniroma1.it/people/faggionato/didattica/dida1.html

dove potete trovare tanto materiale (c'e' anche la sezione dello stesso corso di 2 anni fa)

Libri di testo:

Alcuni capitoli dei seguenti testi (disponibili online):
T.M. Cover, J.A. Thomas; Elements of information theory. 2nd Edition, John Wiley & Sons, inc., 2006.
J.R. Norris; Markov chains. Cambridge University Press.
 S. Roch. Modern Discrete Probability: An Essential Toolkit (online lecture notes)
G. Grimmett. Percolation. Springer Verlag
File con integrazioni scritte dalla docente

Esami: scritto+orale. Il voto dello scritto si puo' usare anche per l'orale in un altro appello.

Date esami: vedere la pagina del dipartimento (consiglio: in alto cliccate su Ordina per data): https://docs.google.com/spreadsheets/u/1/d/e/2PACX-1vQt4Q8_g7oiydvFHlkdF...

Ricevimento: su appuntamento