CIL Important Points

eigenvalues of $X^{T}X$ are singular values of $X$ squared

• Norms:
  • Nuclear Norm:
    • is convex envelope of rank function
      $||A|{|}_{\ast }=\sum _{i=1}^{\text{rank}(A)}{\sigma }_i$
  • Frobenius Norm
  • l2 norm
    $||A|{|}_2=\sum _{j=1}^n||a_j|{|}_2$
    $||A|{|}_2={\sigma }_1$

General

• sample variance: $\frac{1}{N}\sum _{i=0}^N(x_i-\mu {)}^2$
• Reconstruction Error: $\frac{1}{N}||P-\hat{P}|{|}_F^2$
• ${\cos }^2(x)+{\sin }^2(x)=1$
• For centered data, $x$, the reconstruction loss of a projection matrix is $\frac{1}{2}(\text{Var}(x)-\text{Var}(Px))$
  • $\text{Var}(Px)=\text{trace}(PE[x{x}^T])$
• Normalize data $X$ with variance $1$: $Z=\frac{X-\mathit{E}[X]}{\text{Var}[X]}$

Latent Variable Models

• conditional independence assumption
  • $p(w|d,z)=p(w|z)$
  • prob of a word is only dependent on the topic and not on the document
• K-means:
  • deterministic assignments to clusters
  • clusters are spherical
• GMM:
  • probabilistic assignments to clusters
  • clusters are ellipsoid
• Adam:
  • $g_i^k=\beta g_i^{k-1}+(1-\beta )d_{i}l({\mathrm{\Theta }}^k)$
  • $h_i^k=\alpha h_i^{k-1}+(1-\alpha )(d_{i}l({\mathrm{\Theta }}^k){)}^2$
  • $\Rightarrow$ ${\mathrm{\Theta }}_i^{k+1}={\mathrm{\Theta }}_i^k-{\eta }_i^k{g}_i^k$, with ${\eta }_i^k=\frac{\eta }{\sqrt{h_i^k}+\delta }$

Linalg Stuff

• If $f1(x),f2(x),...,fk(x)$ are convex functions defined on a convex set $C\subset R^n$, then $f(x)=f1(x)+f2(x)+···+fk(x)$ is convex on C.
• Furthermore, if at least one of the functions $fi(x),i=1,2,...,k$ is strictly convex on C, then f (x) is strictly convex on C.
• If f (x) is convex on a convex set $C\subset R^n$, and if $\alpha >0$, then $\alpha f(x)$ is convex on C.
• If f (x) is strictly convex on a convex set $C\subset R^n$, and if $\alpha >0$, then $\alpha f(x)$ is strictly convex on C.
• If f (x) is convex on a convex set $C\subset R^n$, and if g(y) is an increasing convex function defined on the range of f (x, then the composition g(f (x)) is convex on C.
• If f (x) is strictly convex on a convex set $C\subset R^n$, and if g(y) is a strictly increasing convex function defined on the range of f (x, then the composition g(f (x)) is strictly convex on C
• sum of two symmetric matrices is symmetric
• principal components are always normalized (they stem from an orthonormal matrix)
• symmetric matrices have orthogonal eigenvectors: $u^{T}v=0$
• Orthogonal matrixes preserve euclidean norm
• idempotence of projection: $P^2=P$
• Self-adjoint: $⟨P(x),y⟩=⟨x,P(y)⟩$
  • projection over Hilbert space is orthogonal if it is self-adjoint
• ${\mathrm{\nabla }}_R\frac{1}{2}||R|{|}_F^2=R$
• $\text{tr}(R^{T}R)=||R|{|}_F^2$
• two linear maps $L:V\to V^{\prime }$, $L^{\prime }:V^{\prime }\to V^{″}$:
  • $\text{rank}(L^{\prime }\circ L)\le min\{\text{rank}(L),\text{rank(L’)}\}$
  • if $\text{im}(L)\cap \text{ker}(L^{\prime })=\{0\}$, then equality holds
• $\text{rank}(AB)=min(\text{rank}(A),\text{rank}(B))$
• $\mid ⟨u,x⟩\mid =\mid \cos (u,x)\mid ||x||||u||$
• $V^T=(V^{T}V{)}^{-1}{V}^T$
  • for any $V:V^T=\arg \underset{w}{min}R(W,V)$
• Spectral theorem:
  • For $\mathrm{\Sigma }$ symmetric and positive semidefinite:
  • $\mathrm{\Sigma }=Q\mathrm{\Lambda }{Q}^T,\mathrm{\Lambda }=\text{diag}({\lambda }_{1,\dots ,{\lambda }_n},{\lambda }_1\ge {\lambda }_n\ge 0$
• Definitheit:
  • positive: $x^{T}Ax>0,\mathrm{\forall }x\ne 0$
  • positive semi: $x^{T}Ax\ge 0,\mathrm{\forall }x\ne 0$
  • negative: $x^{T}Ax<0,\mathrm{\forall }x\ne 0$
  • negative semi: $x^{T}Ax\le 0,\mathrm{\forall }x\ne 0$
  • indefinite: else
• if $A$ is symmetric:
  • eigenvalues are real
  • positive $⟺{\lambda }_i>0$
  • positive semi $⟺{\lambda }_i\ge 0$
  • negative $⟺{\lambda }_i<0$
  • negative semi $⟺{\lambda }_i\le 0$
• Convexity:
  • $f(tx+(1-t)y)\le tf(x)+(1-t)f(y)$
  • if $f$ is differentiable:
    • $f(x)\ge f(y)+\mathrm{\nabla }f(y)(x-y)$
  • if $f$ is twice differentiable:
    • ${\mathrm{\nabla }}^{2}f(x)⪰0$ positive semi definite
• $||A|{|}_F^2=\sum _{i=1}^{min(n,m)}{\sigma }_i^2$
• $||A|{|}_2=sup\{||Ax||:||x||=1\}={\sigma }_1$
• $\text{trace}(A^{T}B)=\text{trace}(A{B}^T)=\text{trace}(B^{T}A)=\text{trace}(B{A}^T)$
• $\text{trace}(AB)=\text{trace}(BA)$
• $\text{trace}(ABC)=\text{trace}(CAB)$, but $\text{trace}(ABC)\ne \text{trace}(ACB)$
• $\text{trace}(A)=\sum _{i=1}^n{\lambda }_i$ if $A\in {\mathbb{R}}^{n\times n}$
• if $A=UD{V}^T\to ||A|{|}_{\ast }=\text{trace}(D)$
• $\mu$-strongly convex (for differentiable function $f$)
  • $f(b)\ge f(a)+⟨f(a),b-a⟩+\frac{\mu }{2}||b-a|{|}^2,\mathrm{\forall }b,a$
  • positive definite quadratic function is strongly convex with $\mu ={\lambda }_{min}$
• twice differentiable:
  • $0\prec \mu I⪯{\mathrm{\nabla }}^{2}f(b)⪯fI,\mathrm{\forall }b$
  • $f$ is $\mu$-strongly convex $\Rightarrow$ $f$ satisfies PL-condition with $\mu$
• PL-condition
  • $\frac{1}{2}||\mathrm{\nabla }f(\mathrm{\Theta })|{|}^2\ge \mu (f(\mathrm{\Theta })-f^{\ast }),\mathrm{\forall }\mathrm{\Theta }$
  • $l^{\ast }=\underset{\mathrm{\Theta }}{min}f(\mathrm{\Theta })$