Algoritmi adattativi e calcolo parallelo (Adaptive Algorithm and

Algoritmi adattativi e calcolo parallelo (Adaptive Algorithm and Parallel Computing) 1. DESCRITTORI 1.1 SSD: ING‐IND/31. 1.2 Crediti: 9 1.3 Docente: Aurelio Uncini. 1.4 Calendarizzazione: secondo semestre. 1.5 Offerto a: MCOR. 1.6 Tipologia di valutazione: esame con votazione in trentesimi. 2. OBIETTIVI DEL MODULO E CAPACITÀ ACQUISITE DALLO STUDENTE ITALIANO
Il corso AACP fornisce strumenti teorici e applicativi avanzati per lo studio e la determinazione di strutture circuitali e algoritmi robusti per la elaborazione adattativa dell’informazione nel vari contesti applicativi: comunicazioni multimediali e multimodali, biologico, biomedico, acustico, TLC, telerilevamento, monitoraggio, modellazione e predizione di fenomeni fisici complessi. Vengono forniti gli elementi bi base per lo sviluppo di algoritmi, prevalentemente quelli introdotti nella prima parte del corso, su architetture parallele con diversa grana di parallelismo. INGLESE
The course ADAPTATIVE ALGORITHM AND PARALLEL COMPUTING (AAPC) provides theoretical and applicative tools for robust adaptive information processing in different application contexts: multimodal and multimedia communications, biological, biomedical, acoustical, TLC, remote sensing, monitoring, modelling and prediction of complex physical phenomena.
Are provided the basic elements for the development of algorithms on parallel architectures, mainly those introduced in the first part of the course, with different parallelism grain.
3. RISULTATI DI APPRENDIMENTO ATTESI ITALIANO Lo studente, oltre ad acquisire i fondamenti teorici di base, sarà in grado di disegnare e realizzare algoritmi, lineari e non lineari, anche su macchine parallele a diversa grana e di valutarne le prestazioni nella specifica applicazione. INGLESE The student acquires the basic theory and is able to design, implement and evaluate the performance of, linear and non‐linear algorithms, also on parallel machines with different grain on several application contexts. 4. PROGRAMMA ITALIANO 1. Filtraggio ottimo lineare ‐ Approccio Stocastico e stocastico approssimato. Equazioni normali di Wiener‐
Hopf; funzione coerenza; superficie errore; analisi componenti principali filtro ottimo. Modellazione sistemi dinamici, equalizzazione canale, cancellazione adattativa rumore. metodi Least Squares (LS); equazioni normali Yule‐Walker; interpretazione geometrica, principio di ortogonalità. LS pesato (WLS); LS regolarizzato. Sistemi sovra‐sotto determinati. Pseudo inversa Moore‐Penrose. Metodi discesa gradiente stocastico con funzione energia di Lyapunov. Metodi algebrici (QR‐LS, SVD‐LS). 2. Filtri adattativi. Algoritmi ricorsivi primo e secondo ordine metodo Levenberg‐Marquardt. Prestazioni: curva apprendimento; discesa gradiente; convergenza, prestazioni, stabilità, disparità autovalori SDA. Least Mean Squares e varianti. 3. Algoritmi a regressione sequenziale. Metodo Newton esatto: convergenza, prestazioni, stabilità, numero condizionamento matrice correlazione. Lemma inversione matriciale. LS ricorsivo. RLS processi non‐stazionari. Algoritmo della proiezione affine. Proiezione su sottospazi vettoriali; interpretazione con teoria della regolarizzazione di Tikhonov. Legge generale di adattamento: algoritmi proporzionali. Estensione multicanale. 4. Algoritmi di blocco e nel dominio trasformato. FA nel dominio della frequenza: overlap‐save‐FDAF, overlap‐add‐DAF. FDAF partizionati. FA in sottobande e metodi multirate. 5. Predizione lineare e algoritmi a ordine ricorsivo. Predizione avanti‐indietro, predittore simmetrico. Equazioni normali aumentate. Algoritmi a ordine ricorsivo. Algoritmo di Levinson‐Durbin, OR‐RLS e varianti. 6. Filtraggio spazio‐temporale. Array processing, strutture di beamformer; sintesi diretta risposta spaziale, beamforming statisticamente ottimi. Cancellatore di interferenze multiple. Stima direzione arrivo. 7. Filtri non‐lineari adattivi e reti neurali. Filtri polinomiali; serie di Volterra; algoritmo di back‐
propagation; functional‐link; soluzioni regolarizzate; problema bias‐vs‐variance. Data‐processing pattern‐recognition. 8. Elaborazione “alla cieca” dei segnali. Analisi componenti principali, trasformata Karuhunen‐Loève, analisi componenti indipendenti, separazione sorgenti di misture istantanee e convolutive; minimizzazione cumulanti, massima verosimiglianza; distanza di Kullback‐Leibler; spazio di Riemann, gradiente naturale; INFO‐MAX. 9. Fondamenti di Calcolo Parallelo: architetture parallele, definizione di algoritmo parallelo, programmazione con memoria condivisa, passaggio di messaggi di programmazione, moltiplicazioni matrici e vettori, metodi alle differenze finite. INGLESE 1. Linear filter theory. Stochastics and stochastic approximation approach The Wiener filter. Normal‐
equations in stochastic Wiener‐Hopf form. Frequency domain interpretation and coherence function. Performance surface. Statistical analysis. Adaptive filter and applications: dynamic systems modelling; adaptive noise cancellation; Least Squares. Yule‐Walker normal equations. Geometric interpretation. LS adaptive filtering. Weighted LS; regularized LS. Moore‐Penrose pseudo inverse matrix forms. Derivation of stochastic gradient descent algorithms family by Lyapunov energy function minimization. Matrix factorization forms: Cholesky, QR, singular value decomposition (SVD). Robust LS: QR‐LS; SVD‐
LS. Total LS. Matching‐pursuit algorithms. 2. Adaptive algorithms. First/second order AF. Levenberg‐Marquardt variant. AF performance: learning‐
curve; Steepest‐Descent Algorithm: convergence; performance, stability, eigenvalue autocorrelation matrix spread. Stochastic‐gradient descent algorithms: least mean squares (LMS); normalized LMS, least mean fourth. Delayed LMS. 3. Sequential regression algorithms. Exact Newton methods: convergence; performance, stability, eigenvalue autocorrelation matrix spread. Matrix inversion lemma. Sequential regression algorithm using LIM. Recursive LS (RLS). Non stationary RLS. Affine projection algorithm (APA). Proportionate algorithms. Exponentiated gradient algorithms. Multichannel algorithms extension. 4. Block and transform domain algorithms. Block LMS algorithms. Frequency domain algorithms: overlap‐
save FDAF, overlap‐add FDAF. Transform domain algorithms. Multirate and subband adaptive filters. 5. Linear prediction and order recursive algorithms. Linear estimation. Augmented normal equation. Order recursive algorithms. Partitioned matrix inversion lemma. OR filters. Levinson‐Durbin algorithm. OR‐RLS. 6. Discrete‐time space‐temporal filtering. Array processing. Beamforming. Statistic optimal BF, broad‐
band BF. Frost BF. GSC‐BF. Direction of arrivals estimation. 7. Non‐linear AF and neural networks. Volterra filters Cover theorem and functional‐links. Multi‐layer parceptron. Back‐propagation. Tikhonov regularization theory RBF. Bias‐vs‐variance problem. Data processing and pattern recognition. 8. Information‐theory based unsupervised learning. Karuhunen‐Loève transform. Principal component analysis. Independent component analysis. Instantaneous/convolutive blind source separation. Learning algorithms for PCA and ICA. Natural gradient learning algorithms. Infomax. 9. Parallel Computing Fundamentals: Parallel architectures, Parallel algorithm design, Shared memory programming, Message passing programming, Multi‐platform Shared‐memory parallel, Vector and Matrix Multiplication, Finite Difference Methods. 5. MATERIALE DIDATTICO 



Aurelio Uncini, “Elaborazione adattativa dei segnali”, Aracne editrice, Roma, ISBN 978–88–548–3142–1, 2010. Aurelio Uncini, “Algoritmi adattativi per circuiti intelligenti”, dispense. Aurelio Uncini, “Fondamenti di calcolo parallelo”, dispense. 6. SITO WEB DI RIFERIMENTO http://www.uncini.com/dida/aapc/index.html

Download Report