Eigenvalues & Diagonalization
Eigenvalue equation
$A\vec{v} = \lambda\vec{v}$, $\vec{v} \neq \vec{0}$
$(A - \lambda I)\vec{v} = \vec{0}$
$\det(A - \lambda I) = 0$
Trace & determinant
$\text{tr}(A) = \sum a_{ii} = \sum \lambda_j$
$\det(A) = \prod \lambda_j$
Triangular: $\lambda_j = a_{jj}$
Diagonalization
$A = V\Lambda V^{-1}$
$V$ = eigenvector matrix (columns)
$\Lambda$ = diagonal eigenvalue matrix
Spectral decomposition
Symmetric $B = Q\Lambda Q^T$
$Q$ orthogonal ($Q^T = Q^{-1}$)
$B = \sum_j \lambda_j \vec{q}_j\vec{q}_j^T$
Positive definiteness
$B \succ 0$: all $\lambda_j > 0$, $\vec{u}^TB\vec{u} > 0$
$B \succeq 0$: all $\lambda_j \geq 0$, $\vec{u}^TB\vec{u} \geq 0$
$M^TM \succeq 0$ always
Eigenfacts
$A^T$: same eigenvalues as $A$
$A^{-1}$: eigenvalues $1/\lambda_j$
$A + cI$: eigenvalues $\lambda_j + c$
Graphs & Laplacian
Laplacian
$L = D - A$
$L_{ii} = d_i$ (degree)
$L_{ij} = -1$ if edge $(i,j)$, else $0$
Laplacian properties
$L \succeq 0$ (always PSD)
$L\vec{1} = \vec{0}$ → $\lambda_1 = 0$ always
dim(null($L$)) = # components
Fiedler vector: eigenvector of $\lambda_2$. Sign of entries → binary clustering.
Projection & Regression
Normal equation
$A^TA\vec{w} = A^T\vec{c}$
$\vec{w} = (A^TA)^{-1}A^T\vec{c}$
MATLAB: $\vec{w} = A \backslash \vec{c}$
Projection & error
$P = A(A^TA)^{-1}A^T$
$\vec{p} = A\vec{w} = P\vec{c}$
$\vec{e} = \vec{c} - \vec{p}$, $A^T\vec{e} = \vec{0}$
MATLAB: p = A*(A\c)
Hooke's Law (no intercept)
$c_i \approx k a_i$
$k = \frac{\vec{a}^T\vec{c}}{\vec{a}^T\vec{a}} = \frac{\sum a_ic_i}{\sum a_i^2}$
Standardization
Mean: $\bar{a} = \frac{1}{m}\sum a_i$
Zero-mean: $\vec{m} = \vec{a} - \bar{a}\vec{1}$
Std: $\sigma = \|\vec{m}\|/\sqrt{m-1}$
Z-score: $z = \vec{m}/\sigma$
RMS error
$\text{RMS}(\vec{e}) = \|\vec{e}\|/\sqrt{m}$
K-fold CV: $\text{RMS}(\vec{t}) > \text{RMS}(\vec{v})$
always (test > validation)
SVD
SVD factorization
$A = U\Sigma V^T$, $A \in \mathbb{R}^{m\times n}$
$U \in \mathbb{R}^{m\times m}$: orthogonal
$\Sigma$: "diagonal", $\sigma_1 \geq \sigma_2 \geq \cdots$
$V \in \mathbb{R}^{n\times n}$: orthogonal
Computing via eigenvalues
$\sigma_j = \sqrt{\lambda_j(A^TA)}$
Nonzero $\lambda$'s of $A^TA$ = $AA^T$
$AA^T$ has extra zero eigenvalues
Matrix spaces
Col($A$): first $r$ cols of $U$
Null($A$): last $n-r$ cols of $V$
Row($A$): first $r$ cols of $V$
rank($A$) = # nonzero $\sigma_j$
Eckart-Young
$A = \sum_{j=1}^r \sigma_j\vec{u}_j\vec{v}_j^T$
Best rank-$p$ approx: first $p$ terms
Explained variance: $\sum_{j=1}^p\sigma_j^2 / \sum_j\sigma_j^2$
PCA
Zero-mean & covariance
$M = A - \vec{1}\bar{A}$ (subtract col means)
$B = M^TM/(m-1)$ (covariance)
$S = M^TM$ (scatter)
PCA via SVD
$M = U\Sigma V^T$
Loading vectors = cols of $V$
$\lambda_j = \sigma_j^2/(m-1)$
Score $j$: $\vec{z}_j = \sigma_j\vec{u}_j$
Explained variance
$q_p = \frac{\sum_{j=1}^p \sigma_j^2}{\sum_{j=1}^n \sigma_j^2}$
Find smallest $p$ with $q_p \geq \theta$
Dimensionality reduction
Score matrix: $Z_p = [z_1 \cdots z_p]$
$Z_p = U_p\Sigma_p = MV_p$
Reduces $n$ variables to $p < n$
Classification & Clustering
Hyperplane from centroids
$\vec{m} = \vec{g}_1 - \vec{g}_2$
$\vec{h} = (\vec{g}_1+\vec{g}_2)/2$
$b = -\vec{h}^T\vec{m}$
Unit: $\vec{n} = \vec{m}/\|\vec{m}\|$, $c = b/\|\vec{m}\|$
Signed distance & logistic
$d = \vec{n}^T\vec{a} + c$ (signed distance)
$p(\vec{a}) = \frac{1}{1+e^{-d}}$ (probability)
Odds: $s = p/(1-p)$
Confusion matrix
| Class +1 | Class -1
Label +1 | TP | FN | P
Label -1 | FP | TN | N
TPR = TP/P, TNR = TN/N
FPR = FP/N, FNR = FN/P
ROC & AUC
ROC point: $[FPR, TPR]^T$ per $\theta$
AUC = area under ROC curve
Perfect: (0,1), Random: diagonal
Artificial Neuron
Feed-forward
Augmented: $\vec{x}_i = [\vec{a}_i \;\; 1]$
Linear: $u_i = \vec{x}_i\vec{w}$
Activation: $z_i = 1/(1+e^{-u_i})$
Residual: $r_i = y_i - z_i$
Backpropagation
$\psi_i = z_i(1-z_i) = \phi'(u_i)$
$b_i = r_i\psi_i$ (backprop factor)
$\vec{d}_i = b_i\vec{x}_i^T$ (descent vec)
$\vec{d} = \sum_i \vec{d}_i$
Weight update
$\vec{w}_{k+1} = \vec{w}_k + \eta\vec{d}_k$
$\eta > 0$: learning rate
$f = \frac{1}{2}\vec{r}^T\vec{r}$: objective
Kernel & Gram
Linear: $\kappa(u,v) = uv^T$
Quadratic: $\kappa(u,v) = (uv^T)^2$
Gaussian: $\kappa(u,v) = e^{-\gamma\|u-v\|^2}$
$K_{ij} = \kappa(\vec{a}_i,\vec{a}_j)$, $K \succeq 0$