\n",
"| Data Type | Rows | Columns | Elements |
|---|
\n",
"| Network Traffic | Sources | Destinations | Number of Bytes |
\n",
"| Social Media | Users | time bins | Number of Posts/Tweets/Likes |
\n",
"| Web Browsing | Users | Content Categories | Visit Counts/Bytes Downloaded |
\n",
"| Web Browsing | Users | time bins | Visit Counts/Bytes Downloaded |
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Matrix Rank"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Let's briefly review some definitions.\n",
"\n",
"We'll consider an $m\\times n$ real matrix $A$.\n",
"\n",
"The __rank__ of $A$ is the __dimension of its column space.__ \n",
"\n",
"The dimension of a space is the smallest number of (linearly independent) vectors needed to span the space.\n",
"\n",
"So the dimension of the column space of $A$ is the __smallest number of vectors that suffice to construct the columns of $A$.__"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Then the rank of $A$ is the size of the smallest set $\\{\\mathbf{u}_1, \\mathbf{u}_2, \\dots, \\mathbf{u}_p\\}$ such that every column $\\mathbf{a}_i$ can be expressed as:\n",
"\n",
"$$\\mathbf{a}_i = c_{i1}\\mathbf{u}_1 + c_{i2}\\mathbf{u}_2 + \\dots + c_{ip}\\mathbf{u}_p\\;\\;\\;\\;i=1,\\dots,n.$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The largest value that a matrix rank can take is $\\min(m,n)$.\n",
"\n",
"However it can happen that the rank of a matrix is __less__ than $\\min(m,n)$."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Now to store a matrix $A \\in \\mathbb{R}^{m\\times n}$ we need to store $m n$ values.\n",
"\n",
"However, if $A$ has rank $k$, it can be factored as $A = UV$,\n",
"\n",
"where $U \\in \\mathbb{R}^{m\\times k}$ and $V \\in \\mathbb{R}^{k \\times n}$.\n",
"\n",
"This only requires $k(m+n)$ values, which could be much smaller than $mn$."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$ \\mbox{$m$ data objects}\\left\\{\\begin{array}{c}\\;\\\\\\;\\\\\\;\\\\\\;\\\\\\;\\end{array}\\right.\\;\\;\\overbrace{\\left[\\begin{array}{ccccc}\n",
"\\begin{array}{c}a_{11}\\\\\\vdots\\\\a_{i1}\\\\\\vdots\\\\a_{m1}\\end{array}&\n",
"\\begin{array}{c}\\dots\\\\\\ddots\\\\\\dots\\\\\\ddots\\\\\\dots\\end{array}&\n",
"\\begin{array}{c}a_{1j}\\\\\\vdots\\\\a_{ij}\\\\\\vdots\\\\a_{mj}\\end{array}&\n",
"\\begin{array}{c}\\dots\\\\\\ddots\\\\\\dots\\\\\\ddots\\\\\\dots\\end{array}&\n",
"\\begin{array}{c}a_{1n}\\\\\\vdots\\\\a_{in}\\\\\\vdots\\\\a_{mn}\\end{array}\n",
"\\end{array}\\right]}^\\mbox{$n$ features} =\n",
"\\overbrace{\\left[\\begin{array}{cc}\\vdots&\\vdots\\\\\\vdots&\\vdots\\\\\\mathbf{u}_1&\\mathbf{u}_k\\\\\\vdots&\\vdots\\\\\\vdots&\\vdots\\end{array}\\right]}^{\\large k}\n",
"\\times\n",
"\\left[\\begin{array}{ccccc}\\dots&\\dots&\\mathbf{v}_1&\\dots&\\dots\\\\\\dots&\\dots&\\mathbf{v}_k&\\dots&\\dots\\end{array}\\right]$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Low Effective Rank"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"In many situations we may wish to __approximate__ a data matrix $A$ with a low-rank matrix $A^{(k)}.$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"To talk about when one matrix \"approximates\" another, we need a norm for matrices. \n",
"\n",
"We will use the __Frobenius norm__ which is just the usual $\\ell_2$ norm, treating the matrix as a vector.\n",
"\n",
"The definition of the Frobenius norm of $A$, denoted $\\Vert A\\Vert_F$, is:\n",
"\n",
"$$\\Vert A\\Vert_F = \\sqrt{\\sum a_{ij}^2}.$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"To quantify when one matrix is \"close\" to another, we use distance in Euclidean space:\n",
"\n",
"$$\\mbox{dist}(A,B) = \\Vert A-B\\Vert_F.$$\n",
"\n",
"(where the Euclidean space is the $mn$-dimensional space of $m\\times n$ matrices.)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Now we can define the __rank-$k$ approximation__ to $A$:\n",
"\n",
"When $k < \\operatorname{Rank} A$, the rank-$k$ approximation to $A$ is the closest rank-$k$ matrix to $A$, i.e., \n",
"\n",
"$$A^{(k)} =\\arg \\min_{\\{B\\;|\\;\\operatorname{Rank} B = k\\}} \\Vert A-B\\Vert_F.$$\n",
"\n",
"This can also be considered the best rank-$k$ approximation to $A$ in a least-squares sense."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Let's say we have $A^{(k)}$, a rank-$k$ approximation to $A$. \n",
"\n",
"By definition, there is a set $\\mathcal{U}$ consisting of $k$ vectors such that each column of $A^{(k)}$ can be expressed as a linear combination of vectors in $\\mathcal{U}$. "
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Let us call the matrix formed by those vectors $U$.\n",
"\n",
"So \n",
"\n",
"$$A^{(k)} = UV^T$$\n",
"\n",
"for some set of coefficients $V^T$ that describe the linear combinations of $U$ that yield the columns of $A^{(k)}$. \n",
"\n",
"So $U$ is $m\\times k$ and $V$ is $n\\times k$."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"If we approximate $A$ by $A^{(k)}$, then the error we incur is:\n",
"\n",
"$$\\Vert A-A^{(k)}\\Vert_F.$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Hence, a rank-$k$ approximation $A^{(k)}$ is valuable if \n",
"\n",
"* $\\Vert A-A^{(k)}\\Vert_F$ is small compared to $\\Vert A\\Vert_F$, and \n",
"* $k$ is small compared to $m$ and $n$.\n",
"\n",
"In that case we have achieved a simplification of the data without a great loss in accuracy."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Finding Rank-$k$ Approximations"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"There is a celebrated method for finding the best rank-$k$ approximation to any matrix: the __Singular Value Decomposition (SVD).__"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"> SVD is \"the Rolls-Royce and the Swiss Army Knife of Numerical Linear Algebra.”\n",
"\n",
"Dianne O’Leary, MMDS ’06"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The singular value decomposition of a rank-$r$ matrix $A$ has the form:\n",
"\n",
"$$A = U\\Sigma V^T$$\n",
"\n",
"where \n",
"\n",
"1. $U$ is $m\\times r$\n",
"2. The columns of $U$ are mutually orthogonal and unit length, ie., $U^TU = I$.\n",
"3. $V$ is $n\\times r$.\n",
"4. The columns of $V$ are mutually orthogonal and unit length, ie., $V^TV = I$.\n",
"5. The matrix $\\Sigma$ is an $r\\times r$ diagonal matrix, whose diagonal values are $\\sigma_1 \\geq \\sigma_2 \\geq \\dots \\geq \\sigma_r > 0$."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
" \n",
"$$ \\left[\\begin{array}{cccc}\\begin{array}{c}\\vdots\\\\\\vdots\\\\{\\bf a_1}\\\\\\vdots\\\\\\vdots\\end{array}&\\begin{array}{c}\\vdots\\\\\\vdots\\\\{\\bf a_2}\\\\\\vdots\\\\\\vdots\\end{array}&\\dots&\\begin{array}{c}\\vdots\\\\\\vdots\\\\{\\bf a_n}\\\\\\vdots\\\\\\vdots\\end{array}\\\\\\end{array}\\right] =\n",
"\\overbrace{\\left[\\begin{array}{cc}\\vdots&\\vdots\\\\\\vdots&\\vdots\\\\\\mathbf{u}_1&\\mathbf{u}_r\\\\\\vdots&\\vdots\\\\\\vdots&\\vdots\\end{array}\\right]}^{\\large r}\n",
"\\times\n",
"\\left[\\begin{array}{cc}\\sigma_1&~\\\\~&\\sigma_r\\\\\\end{array}\\right]\n",
"\\times\n",
"\\left[\\begin{array}{ccccc}\\dots&\\dots&\\mathbf{v}_1&\\dots&\\dots\\\\\\dots&\\dots&\\mathbf{v}_r&\\dots&\\dots\\end{array}\\right]$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Npw, the SVD is _incredibly useful_ for finding matrix approximations.\n",
"\n",
"In particular, for an $m\\times n$ matrix $A$, the SVD does two things:\n",
"\n",
"1. It gives the best rank-$k$ approximation to $A$ for __every__ $k$ up to the rank of $A$.\n",
"2. It gives the __distance__ of the best approximation $A^{(k)}$ from $A$ for each $k$."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"In terms of the singular value decomposition, \n",
"\n",
"The best rank-$k$ approximation to $A$ is formed by taking \n",
"\n",
" * $U' = $ the $k$ leftmost columns of $U$, \n",
" * $\\Sigma' = $ the $k\\times k$ upper left submatrix of $\\Sigma$, and \n",
" * $V'= $ the $k$ leftmost columns of $V$, and constructing \n",
"\n",
"$$ A^{(k)} = U'\\Sigma'(V')^T.$$\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Furthermore, the distance (in Frobenius norm) of the best rank-$k$ approximation $A^{(k)}$ from $A$ is equal to $\\sqrt{\\sum_{i=k+1}^r\\sigma^2_i}$.\n",
"\n",
"That is, if you construct $A^{(k)}$ as shown above, then:\n",
"\n",
"$$\\Vert A-A^{(k)}\\Vert_F^2 = \\sum_{i=k+1}^r\\sigma^2_i$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Low Effective Rank"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Almost any data matrix $A$ that one encounters will usually be __full rank__,\n",
"\n",
"meaning that $\\operatorname{Rank} A = \\min(m, n)$."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"However, it is often the case that data matrices have __low effective rank.__\n",
"\n",
"By this we mean that one can usefully approximate $A$ by some $A^{(k)}$ for which $k \\ll \\min(m,n)$."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"For any data matrix, we can judge when this is the case by looking at its singular values, because the singular values tell us the distance to the nearest rank-$k$ matrix."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Empirical Evidence\n",
"\n",
"Let's see how this theory can be used in practice, and investigate some real data."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"We'll look at data traffic on the Abilene network:\n",
"\n",
"![\"Figure\"](\"figs/L10-William-of-Ockham.png\")
\n",
" \n",
"
\n",
"\n",
"Source: Internet2, circa 2005"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"scrolled": false,
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/html": [
"
\n",
"
\n",
"![\"Figure\"](\"figs/L10-Movie-Latent-Space.png\")
\n",
" \n",
"![\"Figure\"](\"figs/L10-Netflix-Latent-Factors.png\")
\n",
" \n",
"