{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# The Singular Value Decomposition"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Often more important in today's world than the eigenvalue decomposition. Shows up in machine learning, image compression, and many discrete applications."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Definition\n",
"\n",
"For any $m \\times n$ matrix $A$ of rank $r$:\n",
"\n",
"$$A = U \\Sigma V^T = \\\\\n",
"\\begin{pmatrix} u_1 & \\cdots & u_r & \\cdots & u_m\\end{pmatrix} \\begin{pmatrix} \\sigma_1 & & & & & \\\\ & \\sigma_2 & & & & \\\\ & & \\ddots & & & \\\\ & & & \\sigma_r & & \\\\ & & & & 0 & \\\\ & & & & & \\ddots \\end{pmatrix} \\begin{pmatrix} v_1 & \\cdots & v_r & \\cdots & v_n\\end{pmatrix}^T \\\\\n",
"= \\sigma_1 u_1 v_1^T + \\cdots \\sigma_r u_r v_r^T\n",
"$$\n",
"\n",
"(more generally: $U \\Sigma V^H$ for complex matrices)\n",
"\n",
"* $U$ is $m\\times m$ orthogonal (unitary) matrix of **left singular vectors** $u_k$\n",
"* $V$ is $n \\times n$ orthogonal (unitary) of **right singular vectors** $v_k$\n",
"* $\\Sigma$ is $m\\times n$ diagonal matrix of r **singular values** (real) $\\sigma_k > 0$ (and $n-r$ columns / $m-r$ rows of zeros)\n",
"\n",
"The most basic SVD is a matrix decomposition of a matrix A into $U$ Diagonal($\\sigma$) $V^T$, where $U$ and $V$ are square orthogonal and $\\sigma$ is a vector of decreasing singular\n",
"values that are non-negative. The notation $\\Sigma$ denotes the diagonal matrix\n",
"\n",
"$$\n",
"\\Sigma = \\begin{pmatrix}\n",
"\\sigma_1 & 0 & \\cdots \\\\\n",
"0 & \\sigma_2 & \\cdots \\\\\n",
"& & \\ddots\n",
"\\end{pmatrix}\n",
"$$\n",
"\n",
"* The vectors $u_1, \\ldots, u_r$ form an **orthonormal basis for the column space** $C(A)$, and $v_1, \\ldots, v_r$ form an **orthonormal basis for the row space** $C(A^T)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Square Example"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Array{Float64,2}:\n",
" -0.837887 -0.00360708 -0.533729 0.073474 0.0875645\n",
" -0.228281 -0.261529 0.496507 0.0438725 0.794385 \n",
" 0.263465 -0.530214 -0.299503 0.746685 0.047111 \n",
" -0.298982 -0.682087 0.360215 -0.20127 -0.524502 \n",
" 0.295009 -0.430372 -0.499156 -0.628195 0.289765 "
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"5-element Array{Float64,1}:\n",
" 3.09077 \n",
" 2.47409 \n",
" 1.99544 \n",
" 1.3849 \n",
" 0.093338"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"5×5 Array{Float64,2}:\n",
" 0.581876 0.486551 -0.194982 0.21415 -0.583789\n",
" 0.575104 0.0718241 0.386774 -0.669107 0.258454\n",
" -0.499703 0.552859 -0.268021 -0.588264 -0.163567\n",
" 0.26899 0.0523952 -0.771478 0.0126204 0.574074\n",
" 0.0928225 -0.670605 -0.38128 -0.400278 -0.485876"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"A = randn(5,5)\n",
"U,σ,V = svd(A)\n",
"display(U), display(σ), display(V);"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Diagonal{Float64}:\n",
" 3.09077 ⋅ ⋅ ⋅ ⋅ \n",
" ⋅ 2.47409 ⋅ ⋅ ⋅ \n",
" ⋅ ⋅ 1.99544 ⋅ ⋅ \n",
" ⋅ ⋅ ⋅ 1.3849 ⋅ \n",
" ⋅ ⋅ ⋅ ⋅ 0.093338"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"σ\n",
"Σ = Diagonal(σ)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Array{Float64,2}:\n",
" 1.0 -0.0 -0.0 -0.0 0.0\n",
" -0.0 1.0 -0.0 -0.0 0.0\n",
" -0.0 -0.0 1.0 -0.0 -0.0\n",
" -0.0 -0.0 -0.0 1.0 -0.0\n",
" 0.0 0.0 -0.0 -0.0 1.0"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"round.(U'U,2)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Array{Float64,2}:\n",
" 1.0 0.0 0.0 -0.0 0.0\n",
" 0.0 1.0 0.0 0.0 -0.0\n",
" 0.0 0.0 1.0 -0.0 0.0\n",
" -0.0 0.0 -0.0 1.0 -0.0\n",
" 0.0 -0.0 0.0 -0.0 1.0"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"round.(V'V,2)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5-element Array{Float64,1}:\n",
" 3.09077 \n",
" 2.47409 \n",
" 1.99544 \n",
" 1.3849 \n",
" 0.093338"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"σ"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Array{Float64,2}:\n",
" -1.28656 -1.9679 1.51341 0.130546 0.126973\n",
" -0.948825 -0.0905405 -0.318564 -0.944703 -0.06968 \n",
" 0.170982 -0.547836 -1.58101 0.626952 0.767094\n",
" -1.53004 -0.200789 -0.491876 -0.923142 0.907201\n",
" 0.00459912 0.651771 -0.269987 0.962445 1.51355 "
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Σ=Diagonal(σ)\n",
"U*Σ*V'"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Array{Float64,2}:\n",
" -1.28656 -1.9679 1.51341 0.130546 0.126973\n",
" -0.948825 -0.0905405 -0.318564 -0.944703 -0.06968 \n",
" 0.170982 -0.547836 -1.58101 0.626952 0.767094\n",
" -1.53004 -0.200789 -0.491876 -0.923142 0.907201\n",
" 0.00459912 0.651771 -0.269987 0.962445 1.51355 "
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### \"tall-skinny\" full column rank example"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×5 Array{Float64,2}:\n",
" -0.295069 0.524511 0.116294 0.216986 0.759747 \n",
" -0.17686 -0.480732 0.640376 0.572305 0.00172267\n",
" -0.53255 0.407726 -0.212582 0.417509 -0.575018 \n",
" 0.383103 -0.194802 -0.60993 0.636647 0.194809 \n",
" 0.671772 0.538142 0.398985 0.213893 -0.23278 "
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"3-element Array{Float64,1}:\n",
" 3.47777\n",
" 1.94077\n",
" 1.13201"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"3×3 Array{Float64,2}:\n",
" -0.915755 0.0299677 -0.400617\n",
" 0.38762 0.327941 -0.861513\n",
" 0.105561 -0.944223 -0.31193 "
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"A = randn(5,3)\n",
"U,σ,V = svd(A,thin=false) # thin=false gives the basic svd, \n",
" # often the default (thin=true) is more useful\n",
"display(U), display(σ), display(V);"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5×3 Array{Float64,2}:\n",
" 0.9175 -0.177354 -1.11057 \n",
" 0.244891 -1.1689 0.589902\n",
" 1.81618 -0.251088 -0.867612\n",
" -0.954827 0.987286 0.712994\n",
" -2.28909 0.858984 -0.880423"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"5×3 Array{Float64,2}:\n",
" 0.9175 -0.177354 -1.11057 \n",
" 0.244891 -1.1689 0.589902\n",
" 1.81618 -0.251088 -0.867612\n",
" -0.954827 0.987286 0.712994\n",
" -2.28909 0.858984 -0.880423"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Σ = zeros(A) # Make Σ the size of A\n",
"for i=1:length(σ) Σ[i,i]=σ[i] end # put the singular values on the diagonal\n",
"\n",
"display(A)\n",
"U*Σ*V'"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"Σ"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### short fat matrix"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3×3 Array{Float64,2}:\n",
" -0.568528 -0.728401 -0.382373\n",
" 0.732342 -0.659857 0.168117\n",
" -0.374768 -0.184448 0.908586"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"3-element Array{Float64,1}:\n",
" 2.04826 \n",
" 1.45171 \n",
" 0.628441"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"5×5 Array{Float64,2}:\n",
" -0.058333 -0.324256 -0.802831 -0.218627 -0.446229 \n",
" 0.0418722 -0.121676 -0.292301 0.935612 0.150438 \n",
" 0.815484 -0.534919 0.206087 -0.0297624 -0.0740988\n",
" -0.504176 -0.535458 0.46349 0.172218 -0.46326 \n",
" -0.275022 -0.554256 -0.112819 -0.215144 0.747093 "
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"3×5 Array{Float64,2}:\n",
" 0.603724 0.150143 -0.433508 1.04194 0.933455\n",
" 0.138289 0.148483 1.75743 -0.194381 0.106473\n",
" -0.326809 -0.166463 -0.365076 0.795042 0.295105"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = randn(3,5)\n",
"U,σ,V = svd(A,thin=false) # thin=false gives the basic svd, \n",
" # often the default (thin=true) is more useful\n",
"display(U), display(σ), display(V)\n",
"Σ = zeros(A) # Make Σ the size of A\n",
"for i=1:length(σ) Σ[i,i]=σ[i] end # put the singular values on the diagonal\n",
"U*Σ*V'\n",
"A"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3×5 Array{Float64,2}:\n",
" 0.603724 0.150143 -0.433508 1.04194 0.933455\n",
" 0.138289 0.148483 1.75743 -0.194381 0.106473\n",
" -0.326809 -0.166463 -0.365076 0.795042 0.295105"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"Σ"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Thin: for tall skinny, U is the size of A, Σ is square
\n",
"Thin: for short fat, V is the size of A, Σ is square "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"A = randn(5,3)\n",
"U,σ,V = svd(A) # thin = true\n",
"display(U)\n",
"display(round(U'U,2))\n",
"display(A)\n",
"U*Diagonal(σ)*V'"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"A = randn(3,5)\n",
"U,σ,V = svd(A)\n",
"display(V)\n",
"display(round(V'V,2))\n",
"display(A)\n",
"U*Diagonal(σ)*V'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Data \"compression\""
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"