Review-03-Linear-Least-Squares.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Review-03-Linear-Least-Squares"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Answers to review questions from Chapter 3: Linear Least Squares <cite data-cite=\"heath2018scientific\">(Heath, 2018)</cite>.\n",
    "\n",
    "---\n",
    "Questions marked with $\\bigtriangledown$ are considered more difficult."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.1. True or false: A linear least squares prob- lem always has a solution.\n",
    "\n",
    "True."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.3. True or false: At the solution to a linear least squares problem Ax ∼= b, the residual vector r = b − Ax is orthogonal to span(A).\n",
    "\n",
    "True.  The residual vector $r$ is the difference between $b$ and $Ax$ eg $r = b - Ax$.  The vectors $b$ and $Ax$ are closest when the residual vector is orthogonal to the span(A)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.5. True or false: In solving a linear least squares problem Ax ∼= b, if the vector b lies in span(A), then the residual is 0.\n",
    "\n",
    "True.  When b is in the span(A), then there exists an exact solution and the residual will be 0.\n",
    "* In other words, the vector b is a linear combination of the columns of A."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.7. True or false: The product of a Householder transformation and a Givens rotation is always an orthogonal matrix.\n",
    "\n",
    "True. The product of orthogonal matrices is orthogonal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.9. True or false: Methods based on orthogonal factorization are generally more expensive com- putationally than methods based on the normal equations for solving linear least squares problems.\n",
    "\n",
    "True. Methods based on normal equations eg Cholesky factorization cost $O(n^3/6)$ but are numerically unstable.  Methods based on orthogonal factorization eg Householder QR factorization have higher cost $O(n^3/3)$ but are more numerically stable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.11. In a linear least squares problem Ax ∼= b, where A is an $m \\times n$ matrix, if $\\text{rank}(A) < n$,then which of the following situations are possible?\n",
    "(a) There is no solution.\n",
    "(b) There is a unique solution.\n",
    "(c) There is a solution, but it is not unique.\n",
    "\n",
    "(c) There is a solution (there is always a solution to linear least squares), but the solution is not unique.\n",
    "* A solution is unique only when $\\text{rank}(A) = n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.13. In an overdetermined linear least squares problem with model function $f(t, x) = x_1 \\phi_1(t) + x_2 \\phi_2(t) + x_3 \\phi_3(t)$ what will be the rank of the resulting least squares matrix $A$ if we take $\\phi_1(t) = 1$, $\\phi_2(t) = t$, and $\\phi_3(t) = 1 - t$?\n",
    "\n",
    "$\\text{rank}(A) = n - 1 = 2$ since one of the columns is a constant value, thus linearly dependent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 3.15. List two ways in which use of the normal equations for solving linear least squares problems may suffer loss of numerical accuracy.\n",
    "\n",
    "1. Forming $A^TA$ introduces roundoff.\n",
    "2. Sensitivity is worsened: $\\text{cond}(A^TA) = [\\text{cond}(A)]^2$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.17. Which of the following properties of an $m \\times n $ matrix $A$ with $m > n$, indicate that the minimum residual solution of the least squares problem Ax ∼= b is not unique?\n",
    "(a) The columns of A are linearly dependent. (b) The rows of A are linearly dependent. (c) The matrix $A^TA$ is singular.\n",
    "\n",
    "(a) The solution to $Ax \\approxeq b$ is unique IFF $\\text{rank}(A) = n$ which occurs only when the columns are linearly **independent**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.19. (a) What is meant by two vectors x and y being orthogonal to each other? (b) Prove that if two nonzero vectors are orthogo- nal to each other, then they must also be linearly independent.\n",
    "(c) Give an example of two nonzero vectors in R2 that are orthogonal to each other.\n",
    "(d) Give an example of two nonzero vectors in R2 that are not orthogonal to each other.\n",
    "(e) List two ways in which orthogonality is impor- tant in the context of linear least squares prob- lems.\n",
    "\n",
    "(a) Vectors $v$ and $w$ are orthogonal when $v^T w = 0$.  In other words, the angle between $v$ and $w$ is $\\pi/2$.\n",
    "\n",
    "(b) \n",
    "\n",
    "(c) Vectors $v = [1 \\quad 0]^T$ and $w = [0 \\quad 1]^T$ are orthogonal unit vectors and correspond to x and y axis ($\\theta = \\pi / 2$).\n",
    "\n",
    "(d) Vectors $v = [1 \\quad 0]^T$ and $w = [1 \\quad 1]^T$ are not orthogonal vectors and correspond to vector pointing along x axis and another vector pointing between x and y axis ($\\theta = \\pi / 4$).\n",
    "\n",
    "(e) \n",
    "1. Solution to least squares problem $x$ occurs when residual vector $r = b - Ax$ is orthgonal to the $\\text{span}(A)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.21. What is meant by an orthogonal projec- tor? How is this concept relevant to linear least squares?\n",
    "\n",
    "P is an orthogonal projector IFF:\n",
    "* P is idempotent eg $P = P^2$\n",
    "* P is symmetric eg $P = P^T$\n",
    "\n",
    "For least squares P is the orthogonal proejctor onto span(A):\n",
    "* $P = A (A^T A)^{-1} A^T$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.23 Which of the following matrices are orthog- onal?\n",
    "\n",
    "Definition of orthogonal: $Q^T Q = I$.\n",
    "\n",
    "(a) Yes\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "0 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "(b) Yes\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "1 & 0 \\\\\n",
    "0 & -1\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "(c) No\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "2 & 0 \\\\\n",
    "0 & 1/2\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "(d) Yes\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "\\sqrt{2}/2 & \\sqrt{2}/2 \\\\\n",
    "-\\sqrt{2}/2 & \\sqrt{2}/2\n",
    "\\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 3.25. Which of the following types of matrices are necessarily orthogonal?\n",
    "(a) Permutation\n",
    "(b) Symmetric positive definite\n",
    "(c) Householder transformation (d) Givens rotation\n",
    "(e) Nonsingular\n",
    "(f ) Diagonal\n",
    "\n",
    "Definition of orthogonal: $Q^T Q = I$.\n",
    "\n",
    "(a) Yes, permutation matrices are orthogonal.\n",
    "\n",
    "(b) No, not all symmetric positive definite matrices are orthogonal.\n",
    "\n",
    "(c) Yes, Householder transformation is orthogonal.\n",
    "\n",
    "(d) Yes, Givens rotation is orthogonal.\n",
    "\n",
    "(e) No, not all nonsingular matrices are orthogonal.\n",
    "\n",
    "(f) No, not all diagonal matrices are orthogonal.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.27. What condition must a nonzero n-vector w satisfy to ensure that the matrix $H = I - 2ww^T$ is orthogonal?\n",
    "\n",
    "H must be orthogonal $H^T H = I$ and symmetric $H^T = H$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.29. How many scalar multiplications are re- quired to multiply an arbitrary n-vector by an n × n Householder transformation matrix $H = I - 2ww^T$, where w is an n-vector with $||w||_2 = 1$?\n",
    "\n",
    "Not sure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.31. List one advantage and one disadvantage of Givens rotations for QR factorization compared with Householder transformations.\n",
    "\n",
    "Givens rotations are expensive to compute, but unlike the householder transformations they can be parallelized."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.33. In addition to the input array containing the matrix A, which can be overwritten, how much additional auxiliary array storage is required to compute and store the following?\n",
    "(a) The LU factorization of A by Gaussian elimi- nation with partial pivoting, where A is n × n\n",
    "(b) The QR factorization of A by Householder transformations, where A is m × n\n",
    "\n",
    "(a) No additional storage is required to compute LU factorization of A.\n",
    "\n",
    "(b) An additional n-vector of storage is required, since each Householder vector has one more nonzero component than the subdiagonal portion of the corresponding column of A will accommodate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.35. Compared to the classical Gram-Schmidt procedure, which of the following are advantages of modified Gram-Schmidt orthogonalization?\n",
    "(a) Requires less storage\n",
    "(b) Requires less work\n",
    "(c) Is more stable numerically\n",
    "\n",
    "The work required is the same, but the modified Gram-Schmidt **requires less storage** (b) than CGS and is **more stable numerically** (c) since R is built up row-by-row."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.37. Explain why the Householder method re- quires less storage than the modified Gram- Schmidt method for computing the QR factoriza- tion of a matrix A.\n",
    "\n",
    "In the Householder method, the Q and R can share the same space as A.  In the modified Gram-Schmidt some additional extra storage is required."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 3.39. Explain why column pivoting can be used with the modified Gram-Schmidt orthogonaliza- tion procedure but not with the classical Gram- Schmidt procedure.\n",
    "\n",
    "The modified Gram-Schmidt method scans ahead eg subtract from succeeding columns the components in current.  As a result, R is built up row-by-row and this permits column pivoting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}