la_34_condition_number.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    },
    "gpuClass": "standard"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "#### Sensitivity of linear equations to data error"
      ],
      "metadata": {
        "id": "CfWMiHIGCqu8"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Let $y=Ax$, $A\\in \\mathbf{R}^{n \\times n}$ is invertible\n",
        "\n",
        "Suppose we have noise in $y$ such that the measurement is $y+\\delta y$\n",
        "\n",
        "Then, estimated $x$ becomes $x+ \\delta x$ with $\\delta x = A^{-1} \\delta y$\n",
        "\n",
        "Hence\n",
        "\n",
        "$$\\|\\delta x\\|=\\|A^{-1}\\delta y\\| \\leq \\|A^{-1}\\|\\|\\delta y\\|$$\n",
        "\n",
        "where $\\|A^{-1}\\delta y\\| \\leq \\|A^{-1}\\|\\|\\delta y\\|$ is by definition of `matrix norm`\n",
        "\n",
        "$$\\|A^{-1}\\|=\\max \\frac{\\|A^{-1}\\delta y\\|}{\\|\\delta y\\|}$$"
      ],
      "metadata": {
        "id": "oQEv8JCxUA-m"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Therefore, if $\\|A^{-1}\\|$ is `large`\n",
        "\n",
        "* small error in $y$ can lead to large estimation error in $x$\n",
        "* $x$ is for practical purpose not solvable from $y$, even $A$ is invertible\n",
        "* $A$ may just as well be considered `non-invertible`\n",
        "\n",
        "This would be the case if $\\sigma_{\\min}(A)$ is tiny, as\n",
        "\n",
        "$$\\|A^{-1}\\|=\\frac{1}{\\sigma_{\\min}(A)}$$\n",
        "\n",
        "This is from the definition of SVD of invertible matrix $A$\n",
        "\n",
        "$$A^{-1}=(U\\Sigma V^T)^{-1}=V^{-T}\\Sigma^{-1}U^{-1}=V\\Sigma^{-1}U^T$$\n",
        "\n",
        "that the largest singular value in $A^{-1}$ corresponds to $\\frac{1}{\\sigma_{\\min}(A)}$"
      ],
      "metadata": {
        "id": "U2MAecAHU5N4"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Condition number of a matrix"
      ],
      "metadata": {
        "id": "S-W9aKssYcXr"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "If we have $y=Ax$, then by definition of matrix norm, we have\n",
        "\n",
        "$$\\|y\\| =\\|Ax\\|\\leq \\|A\\| \\|x\\|$$\n",
        "\n",
        "Move terms around and merge with\n",
        "\n",
        "$$\\|\\delta x\\|\\leq \\|A^{-1}\\|\\|\\delta y\\|$$\n",
        "\n",
        "we have\n",
        "\n",
        "$$\\frac{\\|\\delta x\\|}{\\|x\\|}\\leq \\|A\\| \\|A^{-1}\\| \\frac{\\|\\delta y\\|}{\\|y\\|} $$"
      ],
      "metadata": {
        "id": "mYlnfwvwZbCB"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "This gives a sense how different the `relative errors` are in $x$ compared to $y$, given the measurement system $A$"
      ],
      "metadata": {
        "id": "sZPUsoqlaDlz"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "The `condition number` is defined as\n",
        "\n",
        "$$\\kappa(A)=\\|A\\| \\|A^{-1}\\| = \\frac{\\sigma_{\\max}(A)}{\\sigma_{\\min}(A)}$$"
      ],
      "metadata": {
        "id": "Zl6cv1phamwX"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Essentially, condition number is what can `amplify relative error` from measurement $y$ to estimator of input $x$"
      ],
      "metadata": {
        "id": "uBlj9RAPa5uy"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "If $\\kappa(A)$ is moderate, then $A$ would not inflate error in $y$ disproportionally in certain directions when estimating $x$ (think of the ellipsoid)"
      ],
      "metadata": {
        "id": "FMqv3JIWhuiP"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Condition number of one"
      ],
      "metadata": {
        "id": "ZsZshZ48blDM"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "When $\\kappa(A)=1$, the it means `no information would be lost` when estimating $x$\n",
        "\n",
        "`Orthogonal matrices` have condition number of 1\n",
        "\n",
        "To see this, for an orthogonal matrix $Q$, its singular values are\n",
        "\n",
        "$$\\sigma_i = \\sqrt{\\lambda_i (Q^TQ)}$$\n",
        "\n",
        "As $Q^TQ=I$, therefore, all $\\lambda_i (Q^TQ)$ equal to 1"
      ],
      "metadata": {
        "id": "aLnFxPY3bmuW"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "If $\\kappa(A)=1$, then $\\sigma_{\\min}=\\sigma_{\\max}$ and $\\Sigma=\\sigma I$, then\n",
        "\n",
        "$$A=U\\Sigma V^T =\\sigma (UV^T)$$\n",
        "\n",
        "Therefore\n",
        "\n",
        "$$A^TA=AA^T=\\sigma^2I$$\n",
        "\n",
        "This means that if a matrix has condition number of 1, it must be a `scaled orthogonal matrix`\n",
        "\n",
        "The reverse is true as well"
      ],
      "metadata": {
        "id": "hrV7Nw0w6Qwv"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Tightness of condition number bound"
      ],
      "metadata": {
        "id": "PQrNWzKC7F9U"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Previously we have\n",
        "\n",
        "$$\\frac{\\|\\delta x\\|}{\\|x\\|}\\leq \\kappa(A) \\frac{\\|\\delta y\\|}{\\|y\\|} $$\n",
        "\n",
        "So, when does the `equality` hold?"
      ],
      "metadata": {
        "id": "VZxkPeKU7JGS"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Let $y=u_1$ and $\\delta y = u_n$, since $A^{-1}=V\\Sigma^{-1}U^T=\\sum \\frac{1}{\\sigma_i}v_iu_i^T$\n",
        "\n",
        "We have\n",
        "\n",
        "$$x=A^{-1}y=v_1/\\sigma_{\\max} \\Longrightarrow \\|x\\|=\\|v_1\\|/\\sigma_{\\max}=1/\\sigma_{\\max}$$\n",
        "\n",
        "$$\\delta x=A^{-1} \\delta y=v_n/\\sigma_{\\min} \\Longrightarrow \\|\\delta x\\|=\\|v_n\\|/\\sigma_{\\min}=1/\\sigma_{\\min}$$"
      ],
      "metadata": {
        "id": "aJhdIe8u7YVE"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Therefore, as $\\frac{\\|\\delta y\\|}{\\|y\\|}=1$ by construction\n",
        "\n",
        "$$\\frac{\\|\\delta x\\|}{\\|x\\|} = \\frac{\\sigma_{\\max}}{\\sigma_{\\min}} = \\kappa(A) = \\kappa(A) \\frac{\\|\\delta y\\|}{\\|y\\|} $$"
      ],
      "metadata": {
        "id": "3-P_H04j8v_Q"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "e1gbNmoWEFTE"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}