• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
26
November

Linear Algebra

2020/2021
Academic Year
ENG
Instruction in English
5
ECTS credits
Course type:
Compulsory course
When:
1 year, 1 semester

Course Syllabus

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

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

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 find various norms of the same vectors and to find a vector norm which is the most appropriate for a give problem
  • To use Bézier curve for elegant smoothing of a polygon
  • 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

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

Assessment Elements

  • non-blocking Quizzes
  • non-blocking Programming
  • non-blocking SGA
Interim Assessment

Interim Assessment

  • Interim assessment (1 semester)
    Total = max(10, (IntermadiateTest + FinalExam)/2 +BonusScore), where IntermadiateTest means the mark for the written test after the 1st module, FinalExam means the mark for the final exam, and BonusScore means the additional score for the students who either prepare a special talk or demonstrate enormous activity during the classes. The talks are evaluated according to the scientific and practical value of the talk, the quality of the presentation, and the number of students participated in the project.
Bibliography

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.