preliminaries/la_crash_course_en.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Linear algebra background"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Questions\n",
    "\n",
    "- What is a vector and a matrix?\n",
    "- List main properties of vectors and matrices\n",
    "- What are computational complexities of basic matrix-vectors operations?\n",
    "- What functions of vectors and matrices exist?\n",
    "- What types of matrices do you know?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Main objects\n",
    "\n",
    "- A vector: $x = (x_1, \\ldots, x_n) \\in \\mathbb{R}^n$\n",
    "- A matrix: $A = (a_{ij}) \\in \\mathbb{R}^{m \\times n}$, $i=1,\\ldots,m$, $j = 1,\\ldots,n$\n",
    "- A system of linear equations: $Ax = b$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Properties\n",
    "- **Definition** A finite set of nonzero vectors $\\{x_1, \\ldots, x_p \\}$ is called *linear dependent*, if there exist scalars $c_1, \\ldots, c_p$ not all zero such that\n",
    "$$\n",
    "\\sum\\limits_{i=1}^p c_i x_i = 0.\n",
    "$$\n",
    "- **Definition** A *rank* of a matrix $A$ is a number of linear independent columns\n",
    "- **Definition** A matrix $A$ is called *positive-definite*, if for any nonzero vector $x$ the scalar $x^{\\top}A x$ is positive:\n",
    "$$\n",
    "A \\succ 0 \\iff x^{\\top}A x > 0\n",
    "$$\n",
    "In the same way, one can define negative-definite matrix and positive/negatve semidefinite matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- **Definition** Square real matrix is called *orthogonal* if \n",
    "$$\n",
    "AA^{\\top} = I\n",
    "$$\n",
    "- **Definition** A trace of square matrix $A$ is a sum of its diagonal elements:\n",
    "$$\n",
    "\\mathrm{trace}(A) = \\sum_{i=1}^n a_{ii}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Theorems\n",
    "\n",
    "- Theorem on matrix rank: row matrix rank equals column matrix rank\n",
    "- Sylvester's criterion: a matrix is positive definite iff all its principal minors are positive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Operations\n",
    "\n",
    "- Adding and subtracting of vectors, multiplication vector by scalar are performed elementwise - $O(n)$ operations (flops)\n",
    "- Dot product: \n",
    "$$\n",
    "\\langle x, y \\rangle = \\sum_{i=1}^n x_i y_i - O(n) \\text{ operations}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Matrix by vector product: \n",
    "$$\n",
    "(Ax)_i = \\sum_{k=1}^n a_{ik}x_k,\n",
    "$$ \n",
    "where $A \\in \\mathbb{R}^{m \\times n}$ and $x \\in \\mathbb{R}^n$:\n",
    "    - for dense matrix $A$ &mdash; $O(mn)$\n",
    "    - for sparse matrix $A$ where $N \\ll mn$ nonzero elements &mdash; $O(N)$\n",
    "    - for lowrank matrix $A = UV^{\\top}$, where $U \\in \\mathbb{R}^{m \\times p}, \\; V \\in \\mathbb{R}^{n \\times p}$ and $p \\ll \\min(n, m)$ &mdash; $O(p(n + m))$\n",
    "    - for some special matrices ([Toeplitz matrix](https://en.wikipedia.org/wiki/Toeplitz_matrix), [circulant](https://en.wikipedia.org/wiki/Circulant_matrix), [$\\mathcal{H}$ and $\\mathcal{H}^2$ matrices](https://en.wikipedia.org/wiki/Hierarchical_matrix)) multiplication by vector can be performed faster   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Matrix by matrix multiplication: \n",
    "$$\n",
    "A = BC \\qquad a_{ij} = \\sum_{k=1}^p b_{ik}c_{kj},\n",
    "$$\n",
    "where $A \\in \\mathbb{R}^{m \\times n}$, $B \\in \\mathbb{R}^{m \\times p}$ и $C \\in \\mathbb{R}^{p \\times n}$\n",
    "    - for dense matrices $B$ and $C$ &mdash; $O(mnp)$ operations\n",
    "    - significantly faster if one or both matrices $B$ and $C$ are sparse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## System of linaer equations \n",
    "\n",
    "$$\n",
    "Ax = b\n",
    "$$\n",
    "**For arbitrary square matrix $A \\in \\mathbb{R}^{n \\times n}$ solving system of linear equations costs $O(n^3)$ operations**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Questions\n",
    "\n",
    "- When system of linear equations is feasible?\n",
    "- What is inverse matrix?\n",
    "- How to solve system of linear equations?\n",
    "- For what matrices system of linear equations can be solved faster than $O(n^3)$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### For what matrices system of linear equations can be solved faster than $O(n^3)$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Diagonal matrices $A$ &mdash; $O(n)$ operations\n",
    "- Lower- and uppertriangular matrices &mdash; $O(n^2)$ operations. The methods to solve such systems is called forward and backward substitutions respectively\n",
    "- Orthogonal matrices $A$ \n",
    "    - for arbitrary orthogomal matrix &mdash; $O(n^2)$ operations\n",
    "    - if one knows structure if the orthogonal matrix (for example $A = I - 2uu^{\\top}$, $u$ is a vector) &mdash; $O(n)$ operations\n",
    "    \n",
    "**Q:** What geometrically means multiplication matrix $A = I - 2uu^{\\top}$ by any vector $x$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Factor-based method to solve system of linear equations $Ax = b$\n",
    "\n",
    "1. Represent matrix $A$ as product of $k$ \"simple\" matrices (diagonal, lower- and uppertriangular, and others...)\n",
    "$$\n",
    "A = A_1A_2\\ldots A_k\n",
    "$$\n",
    "2. To get $x$ solve $k$ systems of linear equations \n",
    "$$\n",
    "A_1x_1 = b \\quad A_2x_2 = x_1 \\quad \\ldots \\quad A_kx = x_{k-1}\n",
    "$$\n",
    "This can be done fast since matrices $A_i$ are \"simple\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "This method is appropriate to solve a $m$ systems of linear equations with constant matrix $A$ and different right-hand side $b_i, \\; i=1,\\ldots,m$:\n",
    "- Matrix $A$ factorization in product of simple matrices is performed only once\n",
    "- After that one can solve $m$ systems of linear equations for every right-hand side $b_i$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### LU factorization\n",
    "**Theorem.** Any nonsingular matrix $A$ can be represented in the following form\n",
    "$$\n",
    "A = PLU,\n",
    "$$\n",
    "where $P$ is a permutation matrix, $L$ is lowertriangular matrix and $U$ is uppertriangular matrix\n",
    "\n",
    "LU factorization requires $2n^3/3$ operations\n",
    "\n",
    "**Q:** What is complexity of solving system of linear equations $Ax=b$ given LU factorization of matrix $A$?\n",
    "\n",
    "**Q:** Why do we need permutation matrix $P$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Cholesky factorization\n",
    "\n",
    "**Theorem.** Any symmetrix and positive definite matrix $A$ can be represebted in the following form\n",
    "$$\n",
    "A = LL^{\\top},\n",
    "$$\n",
    "where $L$ is a lowertriangulat matrix.\n",
    "\n",
    "Cholesky factorization requires $n^3/3$ operations.\n",
    "\n",
    "**Q:** What is complexity of solving system of linear equations $Ax=b$ given Cholesky factorization of matrix $A$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## System of linear equations in the form $(A + BC)x = b$\n",
    "- $A$ is \"simple\" matrix, i.e. system $Ax = b$ can be solved fast\n",
    "- $BC$ is a representation of lowrank matrix\n",
    "\n",
    "How to solve such linear systems fast, you will describe in your homework :)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Eigenvectors and eigenvalues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Questions\n",
    "\n",
    "1. What are eigenvectors and eigenvalues?\n",
    "2. What matrices are diagonalized and unitary diagonalized?\n",
    "3. How to compute full and partial spectrum of the matrix?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Definition.** Nonzero vector $x$ is called *eigenvector* of a transformation given by matrix $A$ if\n",
    "$$\n",
    "Ax = \\lambda x,\n",
    "$$\n",
    "where $\\lambda$ is eigenvalue corresponding to the eigenvector $x$.\n",
    "\n",
    "If matrix $A$ has $n$ linear independent eigenvector, then it can be represented in the form of *spectral decomposition*:\n",
    "$$\n",
    "A = X\\Lambda X^{-1},\n",
    "$$\n",
    "where $\\Lambda = \\mathrm{diag}(\\lambda_1, \\ldots, \\lambda_n)$, and $X = [x_1, \\ldots, x_n]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Theorems\n",
    "\n",
    "1. Matrix is unitary diagonalized iff it is *normal*:\n",
    "$$\n",
    "AA^* = A^*A\n",
    "$$\n",
    "2. \n",
    "$$ \n",
    "\\mathrm{tr}(A) = \\sum_{i=1}^n \\lambda_i\n",
    "\\quad\n",
    "\\det(A) = \\prod_{i=1}^n \\lambda_i\n",
    "$$\n",
    "3. A matrix is positive definite iff all its eigenvalues are positive.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### How to compute eigenvectors and eigenvalues?\n",
    "\n",
    "1. Complexity of computing all eigenvectors and eigenvalues is $O(n^3)$ - [Jacobi eigenvalue algorithm](https://en.wikipedia.org/wiki/Jacobi_eigenvalue_algorithm), [QR-algorithm](https://en.wikipedia.org/wiki/QR_algorithm), using Schur decomposition...\n",
    "2. But full spectral decomposition is rarely needed. \n",
    "Usually only some leading eigenvalues-eigenvectors are required. \n",
    "To solve this problem, one can use [*power method*](https://en.wikipedia.org/wiki/Power_iteration) and [*inverse iteration method*](https://en.wikipedia.org/wiki/Inverse_iteration)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Recap\n",
    "\n",
    "1. Linear algebra is a main tool in investigating optimization methods\n",
    "2. Matrix and vector operations\n",
    "3. Solving system of linear equations\n",
    "4. Computing eigenvalues and eigenvectors"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python [conda env:cvxpy]",
   "language": "python",
   "name": "conda-env-cvxpy-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}