Delivered at:: Big Data and Information Retrieval School

Course type:: Compulsory course

When:: 1 year, 2 module

Abstract

In the course we consider different linear algebra applications and methods, which can be applied to problems arising in other areas of science. These applications are very important and usually beyond the standard undergraduate courses. The course consists of both theoretical background and practical experience of solutions of linear algebra problems which can be used in computer science, data analysis, machine learning, mathematical modeling, and economical models. We discuss some topics of matrix analysis and numerical methods of linear algebra as well as some elements of functional analysis and mathematical statistics. We provide a number of useful algorithms which can be implemented and used in practice. In the course students are invited to give talks on the topics of choice related to applied or theoretical linear algebra. We also plan to invite some external lecturers who successfully apply linear algebra in their work.

Learning Objectives

Upon completion of this course students would be able to better understand and master the methods of applied linear algebra used in computer science, data analysis, machine learning, mathematical modeling, and economical models.

Expected Learning Outcomes

To find the pseudoinverse matrix and to use to find the minimal length solution of an indefinite linear system
To calculate and use SVD and full rank decompositions
To understand the least squares method and to find the least square solution of a system of linear equations
To use the linear regression model to make simple prognoses
To interpolate an unknown function by polynomials and by polynomial splines,
To interpolate an unknown function by polynomials and by polynomial splines
To use Hermite polynomial to interpolate functions with known values of the derivatives
To use Bézier curve for elegant smoothing of a polygon
To find various norms of the same vectors and to find a vector norm which is the most appropriate for a give problem
To find matrix norms compatible with a given vector norm
To find a norm of given vector by using a unit circle associated to the norm only
To calculate the matrix norms induced by the most important vector norms
To evaluate matrix norms using the spectral radius and the singular radius of a matrix
To apply Chebyshev polynomials to various function interpolation problems
To use dot product in spaces of functions and orthogonal families of polynomials to for approximation problems
To find the condition number of a matrix and to use it to evaluate the error of a solution of a system of linear equations
To use the condition number to evaluate the error of an approximatecalculation of a matrix inverse
To use the various iteration methods (including the Jacobi method and the Gauss-Seidel method) for solutions of (large) systems of linear equations
To evaluate the number of iterations needed to find a solution with a given precision
To apply the First and Second Gershgorin’s theorems to evaluate the eigenvalues of a given matrix
To use advanced effective methods for finding the characteristic polynomials and the eigenvalues of a matrix
To use iterative methods for finding an eigenvector and an eigenvalue of a matrix, including the Perron eigenvector and the Perron-Frobenius eigenvalue of anindecomposable nonnegative matrix
To apply the iterative method of finding the Perron eigenvector in the PageRank algorithm
To use PageRank for influence ranking of a social network of a known configuration
To understand the linear productive model and to use the Leontiev inverse for evaluating the direct and indirect multi-sector transactions in the global economy
To calculate functions of square matrices, including matrix powers, exponents, polynomials, and logarithms using either the Jordan form or the Lagrange−Sylvester) polynomials
To calculate persistence diagram for a given dataset using methods from TDA.

Course Contents

Topic 1. Pseudoinverse matrix and the least squares method
The pseudoinverse (aka Moore-Penrose inverse) matrix, its definitions, main properties, and methods of computations. The idea of least squares method. Solution of a linear problem by the least squares method using the pseudoinverse matrix. The linear regression problem and examples of practical problems solution.
Topic 2. Matrix decomposition.
Matrix decompositions and its applications to image processing and machine learning. QR decomposition and singular value (SVD) decomposition.
Topic 3. Metrics and norms. Matrix norms.
Metrics in normed spaces. Matrix norms, their compatibility with vector norms. Holder and Frobenius norms. Spectral radius as a lower bound for matrix norms.
Topic 4. Elements of perturbation theory.
Bounds of the eigenvalues. Gershgorin's theorem. The condition number of a matrix. Error bounds of approximate solutions of systems of linear equations in terms of the errors of the evaluation of the right-hand side and the matrix of the system. Examples of approximate solutions of linear systems. *Methods for solving large systems of linear equations: an overview and examples.
Topic 5. Linear algebra and optimization.
Linear programming model. Examples. The dual problem. *Methods of solutions of the linear programming problem, simplex-method. Iterative methods for solving systems of linear equations. *Numerical methods for solving the minimization of the standard deviation with linear constraints. *The problem of quadratic programming and algorithms for its solution. *Convex programming problem and methods for its solution.
Topic 6. Introduction to topological data analisys (TDA).
Notion of an algebraic group. Simplical complexes. Vietoris–Rips complex. Groups corresponding to a simplicial complex. Betti numbers. Filtrations. Persistence homology.

Assessment Elements

Quizzes
Programming
SGA

Interim Assessment

Interim assessment (2 module)
0.175 * Programming + 0.275 * Quizzes + 0.55 * SGA

Bibliography

Recommended Core Bibliography

F. Aleskerov, H. Ersel, D. Piontkovski. Linear Algebra for Economists. Springer, 2011

Recommended Additional Bibliography

David A. Cox, John Little, Donal O’Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. - Springer International Publishing, Switzerland, 2015. Print ISBN: 978-3-319-16720-6. Online ISBN: 978-3-319-16721-3.

Master’s Programme 'Master of Data Science'

Linear Algebra

Course Syllabus