Computational Intelligence Lab FS26

Frobenius Norm

$$||A||_F = \sqrt{\sum_{i=1}^{n} \sum_{j=1}^{m} |a_{ij}|^{2} } = \sqrt{tr(A^{\top} A)} = \sqrt{\sum_{i = 1}^{r} \sigma_{i}^{2}}$$

Spectral Norm

$$||A||_2 = \sqrt{\lambda_{max}(A^{H}A)} = \sigma_{max}(A)$$

Nuclear Norm

$$||A||_* = \sum_{i = 1}^{r} \sigma_{i}$$

Other matrix norms (1-norm and $\infty - \mathrm{norm}$)

1-norm (Maximum absolute columns sum):

$$||A||_1 = \max_{j}{\sum_{i=1}^{n} |a_{ij}|}$$

$\infty - \mathrm{norm}$ (Maximum absolute row sum):

$$||A||_\infty = \max_{i}{\sum_{j=1}^{m} |a_{ij}|}$$

Eckart-Young Theorem

The Eckart-Young theorem is fundamental to many low-rank approximation problems.

It states that by pruning the singular values below $\sigma_k$ in the SVD representation, we get an optimal rank k approximation of a matrix.

This means that approximations for any k can directly be read-off the SVD.

Given $A \in \mathbb{R}^{n \times m}$ with SVD $A = U \Sigma V^{\top}$. Then for all $1 \le k \le min\{n,m\}$ we have

$$A_{k} := U diag(\sigma_{1}, … , \sigma_{k}) V^{\top} \in \text{arg min}\{||A-B||_{F}: rank(B)\le k\}$$

Convex Envelope of a function

The convex envelope of a function $f: R \rightarrow \mathbb{R}$ is the largest convex function $g$ for which $g \le f$ on $R$.

Convex Envelope of the rank function (rank is NOT convex!)

Theorem (Fazel et al)

The convex envelope of $rank(A)$ on $R = \{||A||_2 \le 1\}$ is $||A||_*$

Sigmoid Activation Function

Sigmoid

$$\sigma(z)=\frac{1}{1+e^{-z}}$$

Derivative

$$\sigma’(z)=\sigma(x)(1-\sigma(x))$$

Tanh Activation Function

Tanh

$$\tanh(z) = \frac{e^z - e^{-z}}{e^z + e^{-z}}$$

Derivative

$$\tanh'(z) = 1 - \tanh^2(z)$$

ReLU Activation function

ReLU

$$\text{ReLU}(z) = \max(0, z)$$

Derivative

$$\text{ReLU}'(z) = \begin{cases} 1 & \text{if } z > 0 \\ 0 & \text{if } z \leq 0 \end{cases}$$