{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Theory of inversion problem"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Definition of the ill-posed linear equation"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The inversion problem is described as a linear equation:\n",
"\n",
"$$\n",
"\\begin{equation}\n",
"\\mathbf{T} \\mathbf{x} = \\mathbf{b},\n",
"\\label{eq:linear_equation}\n",
"\\end{equation}\n",
"$$\n",
"\n",
"where $\\mathbf{T}\\in\\mathbb{R}^{M\\times N}$ is a linear operator, $\\mathbf{x}\\in\\mathbb{R}^N$ is the\n",
"a solution vector of the inversion problem, and $\\mathbf{b}\\in\\mathbb{R}^M$ is the given data vector.\n",
"\n",
"Frequently, the above equation cannot be solved directly because of the following reasons:\n",
"\n",
"1. The number of data $M$ is less than the number of unknowns $N$.\n",
"2. The data $\\mathbf{b}$ is contaminated by noise.\n",
"3. The operator $\\mathbf{T}$ (or $\\mathbf{T}^\\mathsf{T}\\mathbf{T}$) is not full rank or not invertible.\n",
"\n",
"The above equation is called an ill-posed linear equation."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Generalized Tikhonov Regularization"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In order to solve the ill-posed linear equation \\eqref{eq:linear_equation}, we need to introduce a\n",
"objective (or penalty) functional: $O(\\mathbf{x})$ and minimize the following functional\n",
":\n",
"\n",
"$$\n",
"\\begin{equation}\n",
"\\|\\mathbf{T} \\mathbf{x} - \\mathbf{b} \\|_\\mathbf{Q}^2 + \\lambda \\cdot O(\\mathbf{x}),\n",
"\\label{eq:minimize-functional}\n",
"\\end{equation}\n",
"$$\n",
"\n",
"where $\\|\\mathbf{x}\\|_\\mathbf{Q}^2$ stands for the weighted norm squared $\\mathbf{x}^\\mathsf{T} \\mathbf{Q} \\mathbf{x}$\n",
"(compare with the [Mahalanobis distance](https://en.wikipedia.org/wiki/Mahalanobis_distance)) with\n",
"a symmetric positive semi-definite matrix $\\mathbf{Q}$.\n",
"$\\lambda$ is a regularization parameter that controls the trade-off between the data\n",
"misfit and the objective functional.\n",
"\n",
"The objective functional is often defined as a quadratic form:\n",
"$O(\\mathbf{x}) = \\mathbf{x}^\\mathsf{T} \\mathbf{H} \\mathbf{x} = \\|\\mathbf{x}\\|_\\mathbf{H}^2$,\n",
"where $\\mathbf{H}$ is called the regularization matrix.\n",
"Thus, the functional \\eqref{eq:minimize-functional} can be rewritten as:\n",
"\n",
"$$\n",
"\\begin{equation}\n",
"\\|\\mathbf{T}\\mathbf{x} - \\mathbf{b}\\|_\\mathbf{Q}^2 + \\lambda\\|\\mathbf{x}\\|_\\mathbf{H}^2.\n",
"\\label{eq: generalized-tikhonov}\n",
"\\end{equation}\n",
"$$\n",
"This regularization scheme is called the **Generalized Tikhonov Regularization**.\n",
"The conventional Tikhonov regularization is a special case for $\\mathbf{Q}$ and $\\mathbf{H}$ being\n",
"identity matrices.\n",
"Additionally, the first and second terms are called the residual and regularization terms, respectively.\n",
"\n",
"The solution $\\mathbf{x}$ can be obtained by differentiating the\n",
"functional \\eqref{eq: generalized-tikhonov} with respect to $\\mathbf{x}$ and setting it to zero as\n",
"follows:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\n",
"\\begin{align*}\n",
"\\frac{\\partial}{\\partial \\mathbf{x}}\\left[\n",
"\\|\\mathbf{T}\\mathbf{x} - \\mathbf{b}\\|_\\mathbf{Q}^2\n",
"+ \\lambda\\|\\mathbf{x}\\|_\\mathbf{H}^2\n",
"\\right]\n",
"&=\n",
"\\frac{\\partial}{\\partial \\mathbf{x}}\\left[\n",
"(\\mathbf{T}\\mathbf{x} - \\mathbf{b})^\\mathsf{T} \\mathbf{Q} (\\mathbf{T}\\mathbf{x} - \\mathbf{b})\n",
"+ \\lambda\\mathbf{x}^\\mathsf{T} \\mathbf{H} \\mathbf{x}\n",
"\\right]\\\\\n",
"&=\n",
"\\frac{\\partial}{\\partial \\mathbf{x}}\\left[\n",
"\\mathbf{x}^\\mathsf{T} \\left(\\mathbf{T}^\\mathsf{T} \\mathbf{Q} \\mathbf{T} + \\lambda \\mathbf{H}\\right) \\mathbf{x}\n",
"- 2\\mathbf{b}^\\mathsf{T} \\mathbf{Q} \\mathbf{T} \\mathbf{x}\n",
"+ \\mathbf{b}^\\mathsf{T} \\mathbf{Q} \\mathbf{b}\n",
"\\right]\n",
"\\quad\\left(\\because\n",
"\\mathbf{b}^\\mathsf{T} \\mathbf{Q} \\mathbf{T} \\mathbf{x} = \\mathbf{x}^\\mathsf{T} \\mathbf{T}^\\mathsf{T} \\mathbf{Q} \\mathbf{b}\\in \\mathbb{R}^1\n",
"\\right)\\\\\n",
"&=\n",
"2\\left(\\mathbf{T}^\\mathsf{T} \\mathbf{Q} \\mathbf{T} + \\lambda \\mathbf{H}\\right) \\mathbf{x}\n",
"- 2\\mathbf{T}^\\mathsf{T} \\mathbf{Q} \\mathbf{b}\n",
"\\end{align*}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Therefore, the solution $\\mathbf{x}$ is given by:\n",
"$$\n",
"\\begin{equation}\n",
"\\mathbf{x} = \\left(\\mathbf{T}^\\mathsf{T} \\mathbf{Q} \\mathbf{T} + \\lambda \\mathbf{H}\\right)^{-1} \\mathbf{T}^\\mathsf{T} \\mathbf{Q} \\mathbf{b}.\n",
"\\label{eq:solution}\n",
"\\end{equation}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Series expansion of the solution"
]
},
{
"cell_type": "markdown",
"metadata": {
"raw_mimetype": "text/restructuredtext"
},
"source": [
"Although a direct inverse calculation for \\eqref{eq:solution} is possible, it often needs a lot of\n",
"computational resources.\n",
"Additionally, to comprehend the solution, the cholesky decomposition and the\n",
"singular value decomposition are often used ."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 1. Cholesky decomposition\n",
"\n",
"Let $\\mathbf{Q}$ and $\\mathbf{H}$ be factorized as follows:\n",
"\n",
"$$\n",
"\\begin{equation}\n",
"\\begin{cases}\n",
" \\mathbf{P}_\\mathbf{Q}\\mathbf{Q}\\mathbf{P}_\\mathbf{Q}^\\mathsf{T} = \\mathbf{L}_\\mathbf{Q}\\mathbf{L}_\\mathbf{Q}^\\mathsf{T},\\\\\n",
" \\mathbf{P}_\\mathbf{H}\\mathbf{H}\\mathbf{P}_\\mathbf{H}^\\mathsf{T} = \\mathbf{L}_\\mathbf{H}\\mathbf{L}_\\mathbf{H}^\\mathsf{T},\n",
"\\end{cases}\n",
"\\label{eq:cholesky}\n",
"\\end{equation}\n",
"$$\n",
"\n",
"where $\\mathbf{P}_\\mathbf{Q}, \\mathbf{P}_\\mathbf{H}$ are fill-reducing permutation matrices and $\\mathbf{L}_\\mathbf{Q}, \\mathbf{L}_\\mathbf{H}$ are lower triangular matrices.\n",
"Let \\eqref{eq:cholesky} be simple as follows:\n",
"\n",
"$$\n",
"\\begin{equation}\n",
"\\begin{cases}\n",
" \\mathbf{Q} = \\mathbf{B}^\\mathsf{T}\\mathbf{B},\\quad(\\mathbf{B} \\equiv \\mathbf{L}_\\mathbf{Q}^\\mathsf{T}\\mathbf{P}_\\mathbf{Q}),\\\\\n",
" \\mathbf{H} = \\mathbf{C}^\\mathsf{T}\\mathbf{C},\\quad(\\mathbf{C} \\equiv \\mathbf{L}_\\mathbf{H}^\\mathsf{T}\\mathbf{P}_\\mathbf{H}).\n",
"\\end{cases}\n",
"\\label{eq:cholesky-simple}\n",
"\\end{equation}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 2. Singular Value Decomposition"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let us substitute the result of the cholesky decomposition \\eqref{eq:cholesky-simple} into \\eqref{eq:solution}:\n",
"\n",
"$$\n",
"\\begin{align*}\n",
"\\mathbf{x}\n",
"&=\n",
"\\left(\n",
" \\mathbf{T}^\\mathsf{T} \\mathbf{Q} \\mathbf{T} + \\lambda \\mathbf{H}\n",
"\\right)^{-1}\\mathbf{T}^\\mathsf{T} \\mathbf{Q} \\mathbf{b} \\\\\n",
"&=\n",
"\\left(\n",
" \\mathbf{T}^\\mathsf{T} \\mathbf{B}\\mathbf{B}^\\mathsf{T} \\mathbf{T}\n",
" + \\lambda \\mathbf{C}\\mathbf{C}^\\mathsf{T}\n",
"\\right)^{-1} \\mathbf{T}^\\mathsf{T} \\mathbf{b}\\\\\n",
"&=\n",
"\\left[\n",
" \\mathbf{C}^\\mathsf{T}\n",
" \\left(\n",
" \\mathbf{C}^\\mathsf{-T} \\mathbf{T}^\\mathsf{T} \\mathbf{B}^\\mathsf{T} \\mathbf{B} \\mathbf{T} \\mathbf{C}^{-1}\n",
" + \\lambda \\mathbf{I}_N\n",
" \\right)\n",
" \\mathbf{C}\n",
"\\right]^{-1}\n",
"\\mathbf{T}^\\mathsf{T}\\mathbf{B}^\\mathsf{T}\\mathbf{B} \\mathbf{b} \\qquad(\\mathbf{I}_N\\in\\mathbb{R}^{N\\times N}: \\text{identity matrix})\\\\\n",
"&=\n",
"\\mathbf{C}^{-1}\n",
"\\left(\n",
" \\mathbf{A}^\\mathsf{T}\\mathbf{A} + \\lambda \\mathbf{I}_N\n",
"\\right)^{-1}\n",
"\\mathbf{A}^\\mathsf{T} \\hat{\\mathbf{b}},\n",
"\\end{align*}\n",
"$$\n",
"\n",
"where $\\mathbf{A} \\equiv \\mathbf{B} \\mathbf{T} \\mathbf{C}^{-1}$ and $\\hat{\\mathbf{b}} \\equiv \\mathbf{B} \\mathbf{b}$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let us perform the singular value decomposition to $\\mathbf{A}$:\n",
"\n",
"$$\n",
"\\begin{equation}\n",
"\\mathbf{A} = \\mathbf{U}\\mathbf{S}\\mathbf{V}^\\mathsf{T},\n",
"\\label{eq:svd}\n",
"\\end{equation}\n",
"$$\n",
"\n",
"where $\\mathbf{U}\\in\\mathbb{R}^{M\\times r}$ and $\\mathbf{V}\\in\\mathbb{R}^{N\\times r}$ are the left\n",
"and right singular vectors, respectively, and $\\mathbf{S}\\in\\mathbb{R}^{r\\times r}$ is a diagonal\n",
"matrix with the singular values $\\sigma_i$. Here, $r$ is the rank of $\\mathbf{A}$ and $r\\leq\\min(M,N)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Hence, the solution $\\mathbf{x}$ can be written as:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\mathbf{x}\n",
"&=\n",
"\\mathbf{C}^{-1}\n",
"\\left(\n",
" \\mathbf{VS U}^\\mathsf{T} \\mathbf{US V}^\\mathsf{T} + \\lambda \\mathbf{I}_N\n",
"\\right)^{-1}\n",
"\\mathbf{VS}^\\mathsf{T} \\mathbf{U}^\\mathsf{T} \\hat{\\mathbf{b}}\\nonumber\\\\\n",
"&=\n",
"\\mathbf{C}^{-1}\\mathbf{V}^{-\\mathsf{T}}\n",
"\\left(\\mathbf{S}^2 + \\lambda \\mathbf{I}_r\\right)^{-1}\n",
"\\mathbf{V}^{-1}\\mathbf{V S U}^\\mathsf{T} \\hat{\\mathbf{b}} \\qquad(\\because \\mathbf{S}^\\mathsf{T} = \\mathbf{S})\\nonumber\\\\\n",
"&=\n",
"\\tilde{\\mathbf{V}}\n",
"\\left(\\mathbf{I}_r + \\lambda \\mathbf{S}^{-2}\\right)^{-1}\n",
"\\mathbf{S}^{-1} \\mathbf{U}^\\mathsf{T} \\hat{\\mathbf{b}}\n",
"\\qquad(\n",
" \\because \\tilde{\\mathbf{V}}\\equiv \\mathbf{C}^{-1}\\mathbf{V},\n",
" \\quad\\mathbf{V}^{-\\mathsf{T}} = \\mathbf{V}\n",
")\\nonumber\\\\\n",
"&=\n",
"\\tilde{\\mathbf{V}}\\mathbf{F}_\\lambda\\mathbf{S}^{-1}\\mathbf{U}^\\mathsf{T} \\hat{\\mathbf{b}}\n",
"\\qquad\\left(\\because \\mathbf{F}_\\lambda\\equiv \\left(\\mathbf{I}_r + \\lambda \\mathbf{S}^{-2}\\right)^{-1}\\right),\n",
"\\label{eq:sol-matrix}\n",
"\\end{align}\n",
"$$\n",
"\n",
"where $\\tilde{\\mathbf{V}}\\in\\mathbb{R}^{N\\times r}$ is called the inverted solution basis and\n",
"$\\mathbf{F}_\\lambda\\in\\mathbb{R}^{r\\times r}$ is a diagonal matrix, the element $f_{\\lambda, i}$ of\n",
"which plays the role of a filter that suppresses the small singular values.\n",
"The diagonal elements of $\\mathbf{F}_\\lambda$ are given by:\n",
"\n",
"$$\n",
"\\begin{equation}\n",
"f_{\\lambda, i} = \\left(1 + \\frac{\\lambda}{\\sigma_i^2}\\right)^{-1},\n",
"\\label{eq:filter}\n",
"\\end{equation}\n",
"$$\n",
"\n",
"where $\\sigma_i$ is the $i$-th diagonal element of $\\mathbf{S}$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If matrices have the following forms:\n",
"\n",
"$$\n",
"\\begin{align*}\n",
"&\\tilde{\\mathbf{V}} =\n",
" \\begin{bmatrix}\n",
" \\tilde{\\mathbf{v}}_1 & \\tilde{\\mathbf{v}}_2 & \\cdots & \\tilde{\\mathbf{v}}_r\n",
" \\end{bmatrix},\\\\\n",
"&\\mathbf{F}_\\lambda =\n",
" \\begin{bmatrix}\n",
" f_{\\lambda, 1} & & & \\\\\n",
" & f_{\\lambda, 2} & & \\\\\n",
" & & \\ddots & \\\\\n",
" & & & f_{\\lambda, r}\n",
" \\end{bmatrix},\\\\\n",
"&\\mathbf{S} =\n",
" \\begin{bmatrix}\n",
" \\sigma_1 & & & \\\\\n",
" & \\sigma_2 & & \\\\\n",
" & & \\ddots & \\\\\n",
" & & & \\sigma_r\n",
" \\end{bmatrix},\\\\\n",
"&\\mathbf{U} =\n",
" \\begin{bmatrix}\n",
" \\mathbf{u}_1 & \\mathbf{u}_2 & \\cdots & \\mathbf{u}_r\n",
" \\end{bmatrix},\\\\\n",
"\\end{align*}\n",
"$$\n",
"\n",
"then the \\eqref{eq:sol-matrix} can be calculated as follows:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\mathbf{x} &=\n",
"\\begin{bmatrix}\n",
" \\tilde{\\mathbf{v}}_1 & \\tilde{\\mathbf{v}}_2 & \\cdots & \\tilde{\\mathbf{v}}_r\n",
"\\end{bmatrix}\n",
"\\begin{bmatrix}\n",
" f_{\\lambda, 1}/\\sigma_1 & & & \\\\\n",
" & f_{\\lambda, 2}/\\sigma_2 & & \\\\\n",
" & & \\ddots & \\\\\n",
" & & & f_{\\lambda, r}/\\sigma_r\n",
"\\end{bmatrix}\n",
"\\begin{bmatrix}\n",
" \\mathbf{u}_1^\\mathsf{T} \\hat{\\mathbf{b}} \\\\\n",
" \\mathbf{u}_2^\\mathsf{T} \\hat{\\mathbf{b}} \\\\\n",
" \\vdots \\\\\n",
" \\mathbf{u}_r^\\mathsf{T} \\hat{\\mathbf{b}}\n",
"\\end{bmatrix}\\nonumber\\\\\n",
"&=\n",
"\\begin{bmatrix}\n",
" \\tilde{\\mathbf{v}}_1 & \\tilde{\\mathbf{v}}_2 & \\cdots & \\tilde{\\mathbf{v}}_r\n",
"\\end{bmatrix}\n",
"\\begin{bmatrix}\n",
" f_{\\lambda, 1} \\mathbf{u}_1^\\mathsf{T} \\hat{\\mathbf{b}} / \\sigma_1 \\\\\n",
" f_{\\lambda, 2} \\mathbf{u}_2^\\mathsf{T} \\hat{\\mathbf{b}} / \\sigma_2 \\\\\n",
" \\vdots \\\\\n",
" f_{\\lambda, r} \\mathbf{u}_r^\\mathsf{T} \\hat{\\mathbf{b}} / \\sigma_r\n",
"\\end{bmatrix}\\nonumber\\\\\n",
"&=\n",
"\\sum_{i=1}^r f_{\\lambda, i} \\frac{\\mathbf{u}_i^\\mathsf{T} \\hat{\\mathbf{b}}}{\\sigma_i} \\tilde{\\mathbf{v}}_i.\n",
"\\label{eq:sol-expansion}\n",
"\\end{align}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The solution of the ill-posed linear equation \\eqref{eq:solution} can be expressed as a\n",
"linear combination of the inverted solution basis vectors $\\tilde{\\mathbf{v}}_i$.\n",
"The weight of the $i$-th inverted solution basis vector is determined by the $f_{\\lambda, i}$.\n",
"The larger the index $i$ is, the smaller the singular value $\\sigma_i$ is and\n",
"the much smaller the $f_{\\lambda, i}$ is if $\\lambda$ is sufficiently large.\n",
"Therefore, the noisy components of the solution are suppressed by the regularization parameter $\\lambda$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Expression of the squared norm using the series expansion"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For the sake of futher discussion, let us derive the expression of the squared residual norm and the\n",
"squared regularization norm using the series expansion \\eqref{eq:sol-expansion}.\n",
"\n",
"Let each squared norm be $\\rho$ and $\\eta$ respectively:\n",
"\n",
"$$\n",
"\\begin{equation}\n",
"\\rho \\equiv \\| \\mathbf{T}\\mathbf{x}_\\lambda - \\mathbf{b} \\|_\\mathbf{Q}^2,\\quad\n",
"\\eta \\equiv \\| \\mathbf{x}_\\lambda \\|_\\mathbf{H}^2,\n",
"% \\label{eq:norms}\n",
"\\end{equation}\n",
"$$\n",
"where $\\mathbf{Q} = \\mathbf{B}^\\mathsf{T}\\mathbf{B}$ and $\\mathbf{H} = \\mathbf{C}^\\mathsf{T}\\mathbf{C}$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Firstly we transform $\\mathbf{B}\\mathbf{T}\\tilde{\\mathbf{V}}$ into the following form:\n",
"$$\n",
"\\begin{equation}\n",
"\\begin{split}\n",
"\\mathbf{B}\\mathbf{T}\\tilde{\\mathbf{V}}\n",
"&=\n",
"\\mathbf{B}\\mathbf{T}\\mathbf{C}^{-1}\\mathbf{V}\n",
"\\qquad(\\because \\tilde{\\mathbf{V}} = \\mathbf{C}^{-1}\\mathbf{V})\\\\\n",
"&=\n",
"\\mathbf{U}\\mathbf{S}\\mathbf{V}^\\mathsf{T}\\mathbf{V}\n",
"\\qquad(\\because \\mathbf{A} = \\mathbf{B}\\mathbf{T}\\mathbf{C}^{-1} = \\mathbf{U}\\mathbf{S}\\mathbf{V}^\\mathsf{T})\\\\\n",
"&=\\mathbf{U}\\mathbf{S}.\n",
"\\end{split}\n",
"\\label{eq:BTV}\n",
"\\end{equation}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Additionally, using $\\|\\mathbf{a}\\|_\\mathbf{Q}^2 = \\|\\mathbf{B}\\mathbf{a}\\|^2$ ($\\|\\cdot\\|$ is a Euclidean norm), the $\\rho$ is expressed as follows:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\rho\n",
"&=\n",
"\\| \\mathbf{T}\\mathbf{x}_\\lambda - \\mathbf{b} \\|_\\mathbf{Q}^2\\nonumber\\\\\n",
"&=\n",
"\\| \\mathbf{B}\\mathbf{T}\\tilde{\\mathbf{V}}\\mathbf{F}_\\lambda\\mathbf{S}^{-1}\\mathbf{U}^\\mathsf{T}\\mathbf{b}\n",
"- \\mathbf{B}\\mathbf{b} \\|^2\\nonumber\\\\\n",
"&=\n",
"\\| \\mathbf{U}\\mathbf{S}\\mathbf{F}_\\lambda\\mathbf{S}^{-1}\\mathbf{U}^\\mathsf{T}\\hat{\\mathbf{b}} - \\hat{\\mathbf{b}} \\|^2\\qquad(\\because \\eqref{eq:BTV})\\nonumber\\\\\n",
"&=\n",
"\\| \\mathbf{U}\\mathbf{F}_\\lambda\\mathbf{U}^\\mathsf{T}\\hat{\\mathbf{b}} - \\hat{\\mathbf{b}} \\|^2\n",
"\\qquad(\\because \\mathbf{S}\\mathbf{F}_\\lambda = \\mathbf{F}_\\lambda\\mathbf{S})\\nonumber\\\\\n",
"&=\n",
"\\| \\mathbf{U}(\\mathbf{F}_\\lambda - \\mathbf{I}_r)\\mathbf{U}^\\mathsf{T}\\hat{\\mathbf{b}} \\|_2\\label{eq:rho_in_norm}\\\\\n",
"&=\n",
"\\| (\\mathbf{F}_\\lambda - \\mathbf{I}_r)\\mathbf{U}^\\mathsf{T}\\hat{\\mathbf{b}} \\|_2\n",
"\\qquad(\\because \\| \\mathbf{Uy} \\|^2_2 = \\mathbf{y}^\\mathsf{T}\\mathbf{U}^\\mathsf{T}\\mathbf{U}\\mathbf{y} = \\| \\mathbf{y} \\|_2,\\; \\text{where } \\forall\\mathbf{y}\\in\\mathbb{R}^r)\\nonumber\\\\\n",
"&=\n",
"\\sum_{i=1}^r (f_{\\lambda, i} - 1)^2 (\\mathbf{u}_i^\\mathsf{T}\\hat{\\mathbf{b}})^2.\n",
"\\end{align}\n",
"$$\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Also the $\\eta$ is expressed as follows:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\eta\n",
"&=\n",
"\\|\\mathbf{x}_\\lambda\\|_\\mathbf{H}^2 = \\|\\mathbf{C}\\mathbf{x}_\\lambda\\|^2\n",
"\\qquad (\\because\\mathbf{H} = \\mathbf{C}^\\mathsf{T}\\mathbf{C})\\nonumber\\\\\n",
"&=\n",
"\\| \\mathbf{C}\\tilde{\\mathbf{V}}\\mathbf{F}_\\lambda\\mathbf{S}^{-1}\\mathbf{U}^\\mathsf{T}\\hat{\\mathbf{b}} \\|^2\\nonumber\\\\\n",
"&=\n",
"\\| \\mathbf{V}\\mathbf{F}_\\lambda \\mathbf{S}^{-1}\\mathbf{U}^\\mathsf{T}\\hat{\\mathbf{b}} \\|^2\n",
"\\qquad (\\because \\tilde{\\mathbf{V}} = \\mathbf{C}^{-1}\\mathbf{V})\\nonumber\\\\\n",
"&=\n",
"\\| \\mathbf{F}_\\lambda \\mathbf{S}^{-1}\\mathbf{U}^\\mathsf{T}\\hat{\\mathbf{b}} \\|^2\n",
"\\qquad(\\because\n",
"\\| \\mathbf{Vy} \\|^2\n",
"= \\mathbf{y}^\\mathsf{T}\\mathbf{V}^\\mathsf{T}\\mathbf{V}\\mathbf{y}\n",
"= \\| \\mathbf{y} \\|^2,\\; \\text{where } \\forall\\mathbf{y}\\in\\mathbb{R}^r\n",
")\\nonumber\\\\\n",
"&=\n",
"\\sum_{i=1}^r \\frac{f_{\\lambda, i}^2}{\\sigma_i^2} (\\mathbf{u}_i^\\mathsf{T}\\hat{\\mathbf{b}})^2.\n",
"\\end{align}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Lastly, we derive the series-expansion form of the vector:\n",
"$\\mathbf{T}\\mathbf{x}_\\lambda - \\mathbf{b}$ as follows:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\n",
"\\begin{align}\n",
"\\mathbf{T}\\mathbf{x}_\\lambda - \\mathbf{b}\n",
"&=\n",
"\\mathbf{U}(\\mathbf{F}_\\lambda - \\mathbf{I}_r)\\mathbf{U}^\\mathsf{T}\\hat{\\mathbf{b}}\\quad(\\because {\\eqref{eq:rho_in_norm}})\\nonumber\\\\\n",
"&=\n",
"\\sum_{i=1}^r (f_{\\lambda, i} - 1) (\\mathbf{u}_i^\\mathsf{T}\\hat{\\mathbf{b}}) \\mathbf{u}_i.\n",
"\\end{align}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## References"
]
},
{
"cell_type": "raw",
"metadata": {
"raw_mimetype": "text/restructuredtext"
},
"source": [
".. footbibliography::"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.10.12"
},
"widgets": {
"application/vnd.jupyter.widget-state+json": {
"state": {},
"version_major": 2,
"version_minor": 0
}
}
},
"nbformat": 4,
"nbformat_minor": 4
}