Course contents
The course starts with re-introducing main notations and notions of
linear algebra,
for then introducing the singular value decomposition and its main mathematical
properties and interpretations. We will indulge on several
applications of the singular
value decomposition relevant for data analysis such as the Principal
Component Analysis,
Low-rank Approximation and Compression, Document Ranking, and Least
Squares problems.
We show how randomization plays a significant role in breaking the “curse of
dimensionality” for the computation of the singular value decomposition of
humongous matrices. In order to address more formally probabilistic arguments
and concentration of measure phenomena, we focus on basic tools of
probability theory, so to be able to prove the two fundamental Hoeffdings’
and Bernstein inequalities. We show then one application of these inequalities
by proving the celebrated Johnson-Lindenstrauss lemma, of the randomized
quasi-isometrical mapping of large and high-dimensional data sets to
lower dimensions.
While linear algebra and probability are certainly fundamental tools
for big data analysis, the picture would not be complete without an introduction
on convex analysis and convex optimization methods, to which we will
dedicate a relevant chapter. As an application of the fusion of linear algebra,
probability, and optimization, we present the theory of compressed sensing
and sparse recovery, i.e., the nonadaptive randomized acquisition of (sparsely
representable) high-dimensional data and their optimal recovery methods.
Università di Pavia - Offerta formativa