information theorem 1
Information theory Definition. The entropy of a random variable X with a probability mass function $p(x)$ is defined by $$H(x) = -\sum_{x} p(x) \log_2 p(x)$$ Definition. Let $X$ be a discrete r.v. with pmf $P_X(x), x \in \mathcal{X}$. For the event $X=x$, the self-information is $$I(x) = -\log P_X(x)$$ The entropy is the average of the self-information $$H(x) = -\sum_{x \in \mathcal{X}} P_X(x) \cdot \log_2 P_X(x) = E\left[\log_2 \frac{1}{P_X(x)}\right]$$ Remark. $1^\circ$ $I(x) \ge 0$, s...
independent system
Independence set systems Definition. $S=(X,\mathcal{F})$ is called independence system if $X$ is finite set (ground set) $\mathcal{F}$ is a collection of subset then $\forall A\in\mathcal{F}$ under inclusion which means $A\in\mathcal{F}\ A'\subseteq A \Rightarrow A'\in\mathcal{F}$ Theorem1. Let $S=(E,\mathcal{F})$ be independent system, then the following are equivalent (A): $\forall w:E\to\mathbb{R}_{\ge0}$. GREEDY correctly solves the problem (B): $\forall F,F'\in\mathcal{F}$ if $|F'|=|...
CO—αβ algorithm
Co-αβ algorithmFor the balance transportation problem $\sum_{i}a_{i}=\sum_{j}b_{j}$ $$P:\quad \min \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}x_{ij}$$ $$s.t.\quad \sum_{j=1}^{n} x_{ij}=a_i \quad i\in \{1\cdots m\}$$ $$\sum_{i=1}^{m} x_{ij}=b_j \quad j\in \{1\cdots n\}$$ $$x_{ij}\ge 0$$ the dual problem is $$DP:\quad \max \sum_{i=1}^{m} a_i\alpha_i +\sum_{j=1}^{n} b_j\beta_j$$ $$\alpha_i+\beta_j \le c_{ij} \quad i\in \{1\cdots m\}\quad j\in \{1\cdots n\}$$ Set the initial solution of the dual problem ...
CO—Ford and Fulkerson algorithm
The Ford and Fulkerson Algorithm Definition. augmenting path For a network $(N=(V,E,s,t,b))$ and a flow $f$, an augmenting path is an $s$-$t$ path in the undirected graph from $(V,E)$ and follow properties $1^\circ,2^\circ$. $1^\circ$ A forward arc $(i,j)$: $f(i,j)<b(i,j)$ $2^\circ$ A backward arc $(i,j)$: $f(i,j)>0$ So by augmenting path we can find a new flow whose value greater than the current flow. So each iteration can increase $\delta$ flow. $$ \delta=\min_{(i,j)} \begin{cases} ...
CO—Primal dual algorithm
Theorem1. Complementary slackness Suppose $x\in M_p\ \ \pi\in M_D$ then $x\in M_p^{opt}\ \ \pi\in M_D^{opt}$ iff $$\forall i,j \quad \big(c_j-(A^\top\pi)_j\big)\cdot x_j=0=\pi_i\big((Ax)_i-b_i\big)$$ proof By the rules of dualisation $$\min f(x)=c^\top x \qquad \max g(\pi)=b^\top\pi$$ $$(Ax)_i=b_i \quad i\in I \qquad \pi_i\lessgtr0$$ $$(Ax)_i\ge b_i \quad i\in \bar I \qquad \pi_i\ge0$$ $$x_j\ge0 \quad j\in J \qquad (A^\top\pi)_j\le c_j$$ $$x_j\lessgtr0 \quad j\in \bar J \qquad (A^\top\pi)_j...
FISTA
FISTA Definition ($L$-smoothness). Let $L\ge0$. A function $f:E\to(-\infty,+\infty]$ is said to be $L$-smooth over a set $D\subseteq E$ if it is differentiable over $D$ and satisfies $$\|\nabla f(x)-\nabla f(y)\|\le L\|x-y\| \quad \forall x,y\in D$$ lemma4 (descent lemma): Let $f:E\to(-\infty,\infty]$ be $L-$smooth function over a given convex set $D$. Then $$\forall x,y\in D \quad f(y)\le f(x)+\langle\nabla f(x),y-x\rangle+\frac{L}{2}\|x-y\|_2^2$$ proof Set $h(t)=f\big(x+t(y-x)\big)$ $$\i...
ISTA
ISTA algorithm : Iterative Shrinkage‑Thresholding Algorithm Set $x\in\mathbb{R}^n\quad y\in\mathbb{R}^n\quad n\ll m\quad y=\phi x$ Given $y$ and $\phi$, we want to get $x$, if we use the LASSO regression model $$\mathrm{argmin}\ \|y-\phi x\|_2^2+\lambda\|x\|_1$$ We can use iteration $$x^{k+1}=\mathrm{prox}_{\beta\lambda\|\cdot\|_1}\left(x^{k}-2\beta\phi^T(\phi x^{k}-y)\right)$$ to solve it That is the ISTA algorithm, to derive this expression, we need to introduce the following concepts Defi...
Analysis Practice Problems
Problem 1Let $n$ be a positive integer. Denote by $(M(n))$ the largest integer $m$ satisfying the inequality $$\binom{m}{n-1}>\binom{m-1}{n}.$$ Evaluate the limit $$\lim_{n\rightarrow\infty}\frac{(M(n))}{n}.$$ Solution: $$ \binom{m}{n-1}>\binom{m-1}{n} \iff \frac{m!}{(n-1)!\,(m-n+1)!} > \frac{(m-1)!}{n!\,(m-n-1)!} $$ $$ \iff \frac{m}{(m-n+1)(m-n)}>\frac{1}{n} $$ $$ \iff mn > (m-n)(m-n+1) $$ $$ mn > m^2-2mn+m+n^2-n $$ $$ \iff m^2-3mn+n^2+m-n<0 $$ Rewrite as a quadratic in...
Vectors and Their Linear Operations
1. Vector Addition Definition (Vector). $\boldsymbol{a},\boldsymbol{b}\quad\boldsymbol{a}:=\overrightarrow{AB}\quad\boldsymbol{b}:=\overrightarrow{BC}\quad\boldsymbol{c}:=\overrightarrow{AC}$ $\boldsymbol{c}=\boldsymbol{a}+\boldsymbol{b}$. If $|\boldsymbol{a}|=0$ then $\boldsymbol{a}=\vec{0}$. $-\boldsymbol{a}$ has opposite direction with $\boldsymbol{a}$ and $|-\boldsymbol{a}|=|\boldsymbol{a}|$. Rules of Vector Addition1. Associativity $$(\boldsymbol{a}+\boldsymbol{b})+\boldsymbol{c}=\bolds...
高代练习题
题目 Problem. 给定数域 $K$ 上的矩阵$A=\begin{pmatrix} 3 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 3 & 3 \\ 0 & 0 & 3 & 11 \end{pmatrix}$，设$C(A)=\{B \in M_4(K)\mid AB = BA\}$，定义线性映射$\varphi:C(A) \to M_4(K)$为$X \mapsto \varphi(X)=AX^T - XA$。求$C(A)$和$\mathrm{Im}(\varphi)$的维数。 $$ A=\begin{bmatrix} 3 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 3 & 3 \\ 0 & 0 & 3 & 11 \end{bmatrix},\quad C(A)=\{ B \in M_4(K) \mid AB=BA...