From matrix to insight
import Pkg; Pkg.activate("/Users/driscoll/Documents/GitHub/fnc")
using FNCFunctions
using Plots
default(
titlefont=(11,"Helvetica"),
guidefont=(11,"Helvetica"),
linewidth = 2,
markersize = 3,
msa = 0,
size=(500,320),
label="",
html_output_format = "svg"
)
using PrettyTables, LaTeXStrings, Printf
using LinearAlgebraproject at `~/Documents/GitHub/fnc`
7.1. From matrix to insight ¶ Any two-dimensional array of numbers may be interpreted as a matrix. Whether or not this is the only point of view that matters to a particular application, it does lead to certain types of analysis. The related mathematical and computational tools are universally applicable and find diverse uses.
7.1.1 Tables as matrices ¶ Tables are used to represent variation of a quantity with respect to two variables. These variables may be encoded as the rows and columns of a matrix.
A corpus is a collection of text documents. A term-document matrix has one column for each document and one row for each unique term appearing in the corpus. The ( i , j ) (i,j) ( i , j ) i i i j j j j j j
It turns out that by finding the singular value decomposition latent semantic analysis.
Each vote cast in the U. S. Congress is available for download . We can put members of Congress along the columns of a matrix and bills along the rows, recording a number that codes for “yea,” “nay,” “none,” etc. The singular value decomposition
In 2006 the online video service Netflix started an open competition for a $1 million prize. They provided a data set of 100,480,507 ratings (one to five stars) made by 480,189 users for 17,770 movies. Each rating is implicitly an entry in a 17,770-by-480,189 matrix. The object of the prize was to predict a user’s ratings for movies they had not rated. This is known as a matrix completion problem. (It took 6 days for a contestant to improve on Netflix’s private algorithm, and in 2009 the million-dollar prize was awarded to a team that had improved the performance by over 10%.)
7.1.2 Graphs as matrices ¶ A graph network consists of a set V V V nodes and a set E E E edges , each of which is an ordered pair of nodes. If there is an edge ( v i , v j ) (v_i,v_j) ( v i , v j ) i i i adjacent to node j j j undirected if for every edge ( v i , v j ) (v_i,v_j) ( v i , v j ) ( v j , v i ) (v_j,v_i) ( v j , v i ) directed .
The adjacency matrix n n n V V V E E E n × n n\times n n × n
A i j = { 1 if ( v i , v j ) ∈ E (i.e., node i is adjacent to node j ) , 0 otherwise . A_{ij} =
\begin{cases}
1 & \text{if $(v_i,v_j)\in E$ (i.e., node $i$ is adjacent to node $j$)},\\
0 & \text{otherwise}.
\end{cases} A ij = { 1 0 if ( v i , v j ) ∈ E (i.e., node i is adjacent to node j ) , otherwise . In an undirected graph, the edges ( v i , v j ) (v_i,v_j) ( v i , v j ) ( v j , v i ) (v_j,v_i) ( v j , v i )
Graphs are a useful way to represent the link structure of social networks, airline routes, power grids, sports teams, and web pages, to name a few examples. The natural interpretation is that the edge ( v i , v j ) (v_i,v_j) ( v i , v j ) i i i j j j i i i adjacent to node j j j
Here are some elementary results about adjacency matrices.
Part 1 follows immediately from the definitions. Part 2 is clearly true for k = 1 k=1 k = 1 k − 1 k-1 k − 1 k k k i i i j j j k − 1 k-1 k − 1 i i i p p p p p p j j j
∑ p = 1 n [ A k − 1 ] i p ⋅ A p j , \sum_{p=1}^n [\mathbf{A}^{k-1}]_{ip} \cdot A_{pj}, p = 1 ∑ n [ A k − 1 ] i p ⋅ A p j , which is the ( i , j ) (i,j) ( i , j ) A k \mathbf{A}^k A k
Here we create an adjacency matrix for a graph on four nodes.
A = [0 1 0 0; 1 0 0 0; 1 1 0 1; 0 1 1 0]4×4 Matrix{Int64}:
0 1 0 0
1 0 0 0
1 1 0 1
0 1 1 0
The graphplot function makes a visual representation of this graph.
using Plots, GraphRecipes
graphplot(A, names=1:4, markersize=0.2, arrow=6)Since this adjacency matrix is not symmetric, the edges are all directed, as indicated by the arrows. Here are the counts of all walks of length 3 in the graph:
4×4 Matrix{Int64}:
0 1 0 0
1 0 0 0
3 2 0 1
1 3 1 0
If the adjacency matrix is symmetric, the result is an undirected graph: all edges connect in both directions.
A = [0 1 1 0; 1 0 0 1; 1 0 0 0; 0 1 0 0]
graphplot(A, names=1:4, markersize=0.2)The representation of a graph by its adjacency matrix opens up the possibility of many kinds of analysis of the graph. One might ask whether the nodes admit a natural partition into clusters, for example. Or one might ask to rank the nodes in order of importance to the network as determined by some objective criteria—an application made famous by Google’s PageRank algorithm, and one which is mathematically stated as an eigenvalue
7.1.3 Images as matrices ¶ Computers typically represent images as rectangular arrays of pixels, each of which is colored according to numerical values for red (R), green (G), and blue (B) components of white light. Most often, these are given as integers in the range from zero (no color) to 255 (full color). Thus, an image that is m m m n n n m m m n n n m × n m\times n m × n
The Images package has many functions for image manipulation, and TestImages has some standard images to play with.
using Images, TestImages
img = testimage("mandrill")The variable img is a matrix.
However, its entries are colors, not numbers.
You can use eltype to find out the type of the elements of any array.
It’s possible to extract matrices of red, green, and blue intensities, scaled from 0 to 1.
R, G, B = red.(img), green.(img), blue.(img);
@show minB, maxB = extrema(B);(minB, maxB) = extrema(B) = (0.0N0f8, 1.0N0f8) Or we can convert the pixels to gray, each pixel again scaled from 0 to 1.
In order to do our usual operations, we need to tell Julia that we want to interpret the elements of the image matrix as floating-point values.
A = Float64.(Gray.(img))
A[1:4, 1:5]4×5 Matrix{Float64}:
0.568627 0.219608 0.192157 0.34902 0.537255
0.454902 0.396078 0.156863 0.262745 0.352941
0.301961 0.447059 0.180392 0.180392 0.384314
0.278431 0.533333 0.372549 0.188235 0.32549
┌ Warning: Timed out waiting for `Base.active_repl_backend.ast_transforms` to become available. Autoloads will not work.
└ @ BasicAutoloads ~/.julia/packages/BasicAutoloads/08hIo/src/BasicAutoloads.jl:117
[ Info: If you have a slow startup file, consider moving `register_autoloads` to the end of it.
We can use Gray to reinterpret a matrix of floating-point values as grayscale pixels.
Gray.(reverse(A, dims=1))Representation of an image as a matrix allows us to describe some common image operations in terms of linear algebra. For example, in Singular value decomposition Matrix-free iterations
7.1.4 Exercises ¶ ✍ Here is a graph adjacency matrix.
[ 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 ] \begin{bmatrix}
0 & 1 & 0 & 1 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0
\end{bmatrix} ⎣ ⎡ 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 ⎦ ⎤ (a) How many vertices are adjacent to vertex 5? (Assume node numbering starts at 1.)
(b) Is the graph directed or undirected?
(c) How many edges are in the graph?
(d) Draw the graph.
⌨ Refer to Example 7.1.5
(a) Display the test image upside-down.
(b) Display it mirror-reversed from left to right.
(c) Display the image so that it is cropped to isolate a part of the subject.
⌨ For this problem you need to download and import data:
Download actors.mat by clicking the link and saving (you may need to fix the file name).
using MAT
A = matread("actors.mat")["A"]Based on data provided by the Self-Organized Networks Database at the University of Notre Dame, the matrix A contains information about the appearances of 392,400 actors in 127,823 movies, as given by the Internet Movie Database . It has A i j = 1 A_{ij}=1 A ij = 1 j j j i i i
(a) What is the maximum number of actors appearing in any one movie?
(b) How many actors appeared in exactly three movies?
(c) Define C = A T A \mathbf{C}=\mathbf{A}^T\mathbf{A} C = A T A C \mathbf{C} C C i j C_{ij} C ij