{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# GCV criterion\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Definition\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Generalized Cross Validation (GCV) criterion is a very similar method to the [PRESS method](press.ipynb).\n",
    "GCV is a rotation-invariant form of the PRESS method.\n",
    "The deriviation of the GCV from PRESS is shown in <cite data-footcite=Golub1979-gf>(Golub, et al. 1979)</cite>.\n",
    "\n",
    "GCV leads to choosing $\\lambda$ as the minimizer of the GCV function $\\mathcal{G}(\\lambda)$, defined by\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\mathcal{G}(\\lambda)\n",
    "\\equiv\n",
    "\\frac{ \\| (\\mathbf{I} - \\mathbf{A}_\\lambda)\\mathbf{B}\\mathbf{b} \\|^2 }\n",
    "     {\\text{tr}(\\mathbf{I} - \\mathbf{A}_\\lambda)^2},\n",
    "\\end{equation}\n",
    "$$\n",
    "     \n",
    "where $\\mathbf{A}_\\lambda \\equiv \\mathbf{B}\\mathbf{T}(\\mathbf{T}^\\mathsf{T}\\mathbf{Q}\\mathbf{T} + \\lambda\\mathbf{H})^{-1}\\mathbf{T}^\\mathsf{T}\\mathbf{B}^\\mathsf{T}$, $\\text{tr}(\\cdot)$ is the trace of a matrix, and\n",
    "$\\mathbf{Q}=\\mathbf{B}^\\mathsf{T}\\mathbf{B}$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using [series-expansion form of the solution](inversion.ipynb#Series-expansion-of-the-solution), $\\mathcal{G}(\\lambda)$ can be written as\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\mathcal{G}(\\lambda)\n",
    "=\n",
    "\\frac{\\rho}\n",
    "     {\\left(r - \\sum_{i=1}^r f_{\\lambda,i} \\right)^2}.\n",
    "\\label{eq:gcv_series}\n",
    "\\end{equation}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Deriviation of \\eqref{eq:gcv_series}\n",
    "\n",
    "Recalling the [Generalized Tikhonov regularized](./inversion.ipynb#Generalized-Tikhonov-Regularization) solution form and the [series expansion](./inversion.ipynb#Series-expansion-of-the-solution), we obtain the following:\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "\\mathbf{A}_\\lambda \\mathbf{B}\\mathbf{b}\n",
    "&=\n",
    "\\mathbf{B}\\mathbf{T} \\mathbf{x}_\\lambda\\\\\n",
    "&=\n",
    "\\mathbf{B}\\mathbf{T}\\tilde{\\mathbf{V}}\\mathbf{F}_\\lambda\\mathbf{S}^{-1}\\mathbf{U}^\\mathsf{T}\\hat{\\mathbf{b}}\\\\\n",
    "&=\n",
    "\\mathbf{U}\\mathbf{S}\\mathbf{F}_\\lambda\\mathbf{S}^{-1}\\mathbf{U}^\\mathsf{T}\\mathbf{B}\\mathbf{b}\\quad(\\because \\mathbf{B}\\mathbf{T}\\tilde{\\mathbf{V}} = \\mathbf{U}\\mathbf{S})\\\\\n",
    "&=\n",
    "\\mathbf{U}\\mathbf{F}_\\lambda\\mathbf{U}^\\mathsf{T}\\mathbf{B}\\mathbf{b}.\\\\\n",
    "\\therefore\n",
    "\\mathbf{A}_\\lambda &= \\mathbf{U}\\mathbf{F}_\\lambda\\mathbf{U}^\\mathsf{T}.\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we have\n",
    "$$\n",
    "\\begin{align*}\n",
    "\\text{numerator of } \\mathcal{G}(\\lambda)\n",
    "&=\n",
    "\\| (\\mathbf{I} - \\mathbf{A}_\\lambda)\\mathbf{B}\\mathbf{b} \\|^2 \\\\\n",
    "&=\n",
    "\\| \\mathbf{B}\\mathbf{b} - \\mathbf{B}\\mathbf{T}\\mathbf{x}_\\lambda \\|^2\\\\\n",
    "&=\n",
    "\\| \\mathbf{b} - \\mathbf{T}\\mathbf{x}_\\lambda\\|_\\mathbf{Q}^2 = \\rho.\\\\\\\\\n",
    "\\text{denominator of } \\mathcal{G}(\\lambda)\n",
    "&=\n",
    "\\text{tr}(\\mathbf{I} - \\mathbf{A}_\\lambda)^2\\\\\n",
    "&=\n",
    "\\left(\n",
    "    \\text{tr}(\\mathbf{I}) - \\text{tr}(\\mathbf{A}_\\lambda)\n",
    "\\right)^2\\\\\n",
    "&=\n",
    "\\left(\n",
    "    \\text{tr}(\\mathbf{I})  - \\text{tr}(\\mathbf{U}\\mathbf{F}_\\lambda\\mathbf{U}^\\mathsf{T})\n",
    "\\right)^2\\\\\n",
    "&=\n",
    "\\left(\n",
    "    \\text{tr}(\\mathbf{I})  - \\text{tr}(\\mathbf{F}_\\lambda)\n",
    "\\right)^2\n",
    "\\quad\\left(\n",
    "    \\because \\text{tr}(\\mathbf{U}\\mathbf{F}_\\lambda\\mathbf{U}^\\mathsf{T}) = \\text{tr}(\\mathbf{U}^\\mathsf{T}\\mathbf{U}\\mathbf{F}_\\lambda) = \\text{tr}(\\mathbf{F}_\\lambda)\n",
    "\\right)\\\\\n",
    "&=\n",
    "\\left(\n",
    "    \\sum_{i=1}^r 1 - \\sum_{i=1}^r f_{\\lambda,i}\n",
    "\\right)^2\\\\\n",
    "&=\n",
    "\\left(\n",
    "    r - \\sum_{i=1}^r f_{\\lambda,i}\n",
    "\\right)^2.\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example\n",
    "\n",
    "The example is shown in [notebooks/non-iterative/gcv.ipynb](../../notebooks/non-iterative/gcv.ipynb)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Limitation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "GCV is a good method when the noise is unknown and the noise is assumed to be white noise, however,\n",
    "it often fails to give a satisfactory result when the error is highly correlated.<br>\n",
    "See the [example case](../../notebooks/non-iterative/lcurve_vs_gcv.ipynb) for the limitation of GCV."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    ".. footbibliography::"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}