Terminology#

In this section, we outline some background terminology which will come up repeatedly throughout the book. This section attempts to standardize some background material that we think is useful going in. It is important to realize that many of the concepts discussed below are only crucial for understanding the advanced, starred sections. If you aren’t familiar with some (or any!) of the below concepts, we don’t think this would detract from your understanding of the broader content.

Mathematical Concepts#

Symbol

Definition

Description/Example

\(x\)

A number

\(x = 5\)

\(\vec x\)

A column vector

\(x = (5, 2)\)

\(x_{i}\)

The \(i^{th}\) element of a vector

\(x_2 = 2\)

\(\sum_{n = i}^j x_n\)

A sum from the \(i^{th}\) to \(j^{th}\) element of \(x\)

\(\sum_{n = 1}^2 x_n = 7\)

\(\prod_{n = i}^j x_n\)

A product from the \(i^{th}\) to the \(j^{th}\) element of \(x\)

\(\prod_{n = 1}^2 x_n = 10\)

\(X\)

A matrix

\(X = \begin{bmatrix}1 & 2 \\ 3 & 4\end{bmatrix}\)

\(x_{ij}\)

The \((i,j)^{th}\) element of a matrix

\(x_{2,2} = 4\)

\(nrow(X)\)

The number of rows of \(X\)

\(nrow(X) = 2\)

\(ncol(X)\)

The number of columns of \(X\)

\(ncol(X) = 2\)

Mathematical Operations#

Operation

Name

Definition

\(\vec x^\top \vec y\)

The euclidean inner product

\(\sum_{i = 1}^n x_i y_i\)

\(C = AB\)

Matrix multiplication

\(c_{ij} = \sum_k a_{ik}b_{kj}\)

\(\vert\vert\vec x\vert\vert_k\)

The \(k\)-norm of \(\vec x\)

$\left(\sum_{i = 1}^n

\(\vert\vert\vec x - \vec y\vert\vert_2\)

The Euclidean distance between \(\vec x\) and \(\vec y\)

\(\sqrt{\sum_{i = 1}^n (x_i - y_i)^2}\)

\(\vert\vert X\vert\vert_F\)

The Frobenius norm of \(X\)

\(\sqrt{\sum_{i = 1}^n \sum_{j = 1}^m x_{i,j}^2}\)

To understand the technical details of numerous sections in this book, it would be useful to be familiar with the concept of the singular value decomposition (svd), a technique for decomposing matrices. The linear algebra book “Numerical Linear Algebra” by Lloyd Trefethan [1] provides a succinct background in all of the properties of the svd, and many we will not touch on. We would recommend taking a look at Lectures 1 through 5 in that textbook if you haven’t seen the singular value decomposition before, which will refresh your memory on the basic properties of matrices, such as the concepts of matrix multipliplication and other manipulations, and give you some detailed background in the singular value decomposition.

Probability/Statistics Concepts#

Symbol/Concept

Explanation

Example

\(\mathbf x\)

A random variable

\(\mathbf x\) takes the value \(0\) or \(1\) each with probability \(0.5\)

\(\vec{\mathbf x}\)

A random vector

\(\vec{\mathbf x} = (\mathbf x_1, \mathbf x_2)\)

\(\mathbf X\)

A random matrix

\(\mathbf X = \begin{bmatrix} \mathbf x_{11} & \mathbf x_{12} \\ \mathbf x_{21} & \mathbf x_{22} \end{bmatrix}\)

\(Pr(A)\)

Probability that a statement \(A\) happens

\(Pr(\mathbf x = 1) = 0.5\)

\(Bern(p)\)

The Bernoulli distribution with probability \(p\)

If \(\mathbf x\) is a \(Bern(p)\) random variable, \(Pr(\mathbf x = 1) = p, Pr(\mathbf x = 0) = 1 - p\)

Conditional probability

the probability of one event, given that another event occurs

\(Pr(A \vert B) = \frac{Pr(A, B)}{Pr(B)}\)

For most of this work, we will assume a fairly limited background in probability and statistics, with two notable exceptions. To understand the technical details of Section 5 on the theoretical results, a working familiarity with the common notations and concepts from undergraduate and graduate statistics will be valuable. You should have some level of familiarity with the concepts of multivariate and matrix-valued random variables, and desirable properties of estimators for random quantities, such as unbiasedness and asymptotic consistency. If you are unfamiliar with these concepts and wish to tackle the appendix Section 12.1, it would be valuable to brush up on these ahead of time. For appendix Section 12.2, we would recommend a foundational background in high-dimensional statistical inference and concentration phenomena. The results in that section are largely provided for posterity to give you resources to understand why the techniques we focus on in this book work, and are neither strictly essential to having an intuitional understanding of the techniques and how to apply them nor essential to deriving value from this work. We believe that for many audience members, the entirety of Chapter 7 can be omitted without missing too much for most applications of network machine learning. We will provide a detailed background sheet of the concepts to brush up on as these chapters arise.

References#

1

Lloyd Nicholas Trefethen and David Bau. Numerical Linear Algebra. Society for Industrial and Applied Mathematics, 1997. ISBN 978-0-89871487-6. URL: https://books.google.com/books/about/Numerical_Linear_Algebra.html?id=5Y1TPgAACAAJ.