\(\newcommand{\abs}[1]{\left\lvert#1\right\rvert}\) \(\newcommand{\norm}[1]{\|#1\|}\) \(\newcommand{\inner}[1]{\left\langle#1\right\rangle}\) \(\DeclareMathOperator*{\argmin}{arg\,min}\) \(\DeclareMathOperator*{\argmax}{arg\,max}\) \(\DeclareMathOperator*{\E}{\mathbb{E}}\)

× This section is under development!

t

A

ssume that eigenvectors are normalized to unit \(\ell_2\)-norm and have a nonnegative first component. The sign convention guarantees uniqueness of the eigenvector associated with an eigenvalue with geometric multiplicity one.

Vector norms

For \(\mathrm{v} = (v_i)_{i=1}^n \in \mathbb{R}^n\)

\(\norm{\mathrm{v}}_p = (\sum_{i}^n\abs{v_i}^p)^{1/p},\) hence it is a norm for \(p=[1,\infty]\) \(\norm{\mathrm{v}}_0 =\) # of nonzero elements \(\norm{\mathrm{v}}_\infty = \underset{1\le i \le n}{\max} \abs{v_i}\)

Inequalities

\(\norm{\mathrm{v}}_2 \le \norm{\mathrm{v}}_1 \le \sqrt{n}\norm{\mathrm{v}}_2\) \(\norm{\mathrm{v}}_q \le \norm{\mathrm{v}}_p \le n^{1/p+1/q}\norm{\mathrm{v}}_q\) for $0\le p< q\le \infty$ (Pf by H"older’s inequality)

H"older’s inequality

\(\norm{fg}_1 \le \norm{f}_p \norm{g}_q \quad 1\le p,q \le \infty,\; \frac{1}{p} + \frac{1}{q} = 1,\; f\in L^p,\; g\in L^q\)

Minkowski’s inequality

\(\norm{f+g}_p \le \norm{f}_p + \norm{g}_p \quad 1\le p< \infty,\; f,g\in L^p\)

Matrix norms

For $A \in \mathbb{R}^{m \times n}, r = rank(A) \le \min(m,n)$, SVs sorted $s_1 \ge s_2 \ge \ldots$

Operator/Spectral norm

\(\norm{A} = \underset{x\in\mathbb{R}^n\backslash \{0\}}{\max} \frac{\norm{Ax}_2}{\norm{x}_2} = \underset{x\in S^{n-1}}{\max} \norm{Ax}_2 = \underset{x\in S^{n-1},\ y\in S^{m-1}}{\max} \inner{Ax,y} = s_1(A) = \norm{s}_\infty\)

Frobenius/Euclidean norm

\(\norm{A}_F = \sqrt{\sum_i^m\sum_j^n \abs{A_{ij}}^2} = \sqrt{\sum_i^r s_i^2(A_{i})} = \sqrt{tr(A'A)} = \sqrt{\inner{A,A}} = \norm{s}_2\)

\(\norm{AA'}_F = \norm{A'A}_F \le \norm{A}_F^2\) \(\norm{A+B}_F^2 = \norm{A}_F^2 + \norm{B}_F^2 + 2\inner{A+B}_F\) \(\norm{A}_F \le \norm{A} _* \le \sqrt{r}\norm{A}_F\) if \(A = U\Sigma V'\), then \(\norm{A}_F^2 = \norm{\Sigma}_F^2\) \(\norm{A}_F^2 = \sum_i^n \norm{\mathbb{a}_i}^2,\) where \(\mathbb{a}_i\) are columns

HS norm

For \(X,Y \in \mathbb{R}^{n\times n}\), the matrix inner product is \(\inner{X,Y} = tr(XY')\), which induces the Hilbert-Schmidt norm \(\norm{X}_{HS} = \sqrt{\inner{X,X}}\)

Inequalities

\(\norm{A} \le \norm{A}_F \le \sqrt{r} \norm{A}\) \(s_i \le \frac{1}{\sqrt{i}} \norm{A}_F\) \(\norm{s}_\infty \le \norm{s}_2 \le \sqrt{r} \norm{s} _\infty\)

To be added a lot more!

Asymptotic Notation

For functions \(f,g\):

  • \(f_n = \mathcal{O}(g_n)\) means \(\exists C\in (0,\infty)\) s.t. \(f_n \le Cg_n\)
  • \(f_n = \Omega(g_n)\) means \(\exists C\in (0,\infty)\) s.t. \(f_n \ge Cg_n\)
  • \(f_n = \Theta(g_n)\) means \(f_n = \mathcal{O}(g_n)\) and \(f_n = \Omega(g_n)\)
  • Note: no \(\cdot_p\) means \(C\) is deterministic, nonrandom

\(\mathcal{O}_p\) and \(\mathcal{o}_p\)

\(\boxed{X_n = \mathcal{O}_p(g_n) \Longleftrightarrow \forall \epsilon>0, \, \exists M>0 \; \text{ s.t. } \; \mathbb{P}(\abs{X_n/g_n}\ge M) < \epsilon}\) \(\boxed{X_n = \mathcal{o}_p(g_n) \Longleftrightarrow \forall \epsilon>0 \quad \underset{n\to\infty}{\lim} \mathbb{P}(\abs{X_n/g_n}\ge \epsilon) = 0}\)

if \(X_n = \mathcal{O}_p(f_n)\) and \(Y_n = \mathcal{O}_p(g_n)\):

  • \[X_n Y_n = \mathcal{O}_p(f_ng_n)\]
  • \[\abs{X_n}^s = \mathcal{O}_p(f_n^s), \quad s>0\]
  • \[X_n + Y_n = \max\{\mathcal{O}_p(f_n), \mathcal{O}_p(g_n)\}\]

if \(X_n = \mathcal{o}_p(f_n)\) and \(Y_n = \mathcal{o}_p(g_n)\):

  • \[X_n Y_n = \mathcal{o}_p(f_ng_n)\]
  • \[\abs{X_n}^s = \mathcal{o}_p(f_n^s), \quad s>0\]
  • \[X_n + Y_n = \max\{\mathcal{o}_p(f_n), \mathcal{o}_p(g_n)\}\]

if \(X_n = \mathcal{o}_p(f_n)\) and \(Y_n = \mathcal{O}_p(g_n)\):

  • \[X_n Y_n = \mathcal{o}_p(f_ng_n)\]
  • \[X_n + Y_n = \mathcal{O}_p(g_n)\]

Continuous mapping Thm

Given \(f: \mathbb{R}^k \to \mathbb{R}^m\) is “almost surely continuous”

  • \[X_n \overset{d}{\to} X \Longrightarrow f(X_n) \overset{d}{\to} f(X)\]
  • \[X_n \overset{d}{\to} X \Longrightarrow f(X_n) \overset{p}{\to} f(X)\]
  • \[X_n \overset{d}{\to} X \Longrightarrow f(X_n) \overset{as}{\to} f(X)\]

Slutsky’s Lemma

if \(X_n \overset{d}{\to} X\) and \(Y_n \overset{d}{\to} c\):

  • \[X_n + Y_n \overset{d}{\to} X + c\]
  • \[X_nY_n \overset{d}{\to} cX\]
  • \[X_n/Y_n \overset{d}{\to} X/c\]

SVD

Add skinny SVD!

\(\underset{n\times m}{A} = \sum_i^r s_i\mathrm{u}_i\mathrm{v}_i',\) where \(r=rank(A)\)

\[s_i(A) = \sqrt{\lambda_i(AA')} = \sqrt{\lambda_i(A'A)}\]

If \(A\) is symmetric, then also: \(s_i(A) = \abs{\lambda_i(A)}\)

Courant-Fisher min-max Thm

Courant–Fischer variational representation of max eigenvalue & eigenvector:

\[\mathrm{v}_1(\widehat{\Sigma}) = \underset{\norm{z}_2 = 1}{\argmax} \; z'\widehat{\Sigma}z\]

Alternative equivalent variational representation is in terms of the semidefinite program (SDP):

\[Z^* = \underset{Z\in\mathbb{S}^p_+, \, tr(Z)=1}{\argmax} \, tr(\widehat{\Sigma}Z)\]

Eckart-Young-Mirsky Thm

Johnson–Lindenstrauss

Given a set $Q$ of $q$ points in $\mathbb{R}^N$ with $N$ typically large, we would like to embed these points into a lower-dimensional Euclidean space $\mathbb{R}^n$ while approximately preserving the relative distances between any two of these points. The question is how small can we make $n$ (relative to $q$) and which types of embeddings work?

Given $\epsilon \in (0, 1),$ for every set $Q$ of $q$ points in $\mathbb{R}^N$, if $n$ is a positive integer such that \(n>n_0 = O(\ln(q)/\epsilon^2)\), there exists a Lipschitz f’n $f: \mathbb{R}^N \to \mathbb{R}^n$ s.t.
\((1-\epsilon)\norm{u-v}^2_2 \le \norm{f(u) - f(v)}^2_2 \le (1+\epsilon)\norm{u-v}^2_2, \quad \forall \; u,v\in Q.\)