Matrix norms Given a matrix $X \in \mathbb{R}^{m \times n}$, $\sigma_{i}(X)$ denotes the $i$-th largest singular value of $X$ and is equal to the square root of the $i$-th largest eigenvalue of $XX'$. The rank of $X$, denoted as $\mathrm{rank}(X) = r$ is the number of non-zero singular values. Inner Product Given $X, Y \in \mathbb{R}^{m \times n}$, the inner product between $X$ and $Y$, denoted by $\langle X, Y\rangle$, is defined as
Read note →Estimating LP bounds Given an optimization problem $$ \begin{aligned} \max_{f, s} &\quad 12f + 9s \\ \st &\quad 4f + 2s \leq 4800 \\ &\quad f + s \leq 1750 \\ &\quad 0 \leq f \leq 1000 \\ &\quad 0 \leq s \leq 1500 \\ \end{aligned} $$ Suppose the maximum profit is $p^\star$. How can we bound $p^\star$? The lower bound of $p^\star$ can be found by picking any feasible point (since maximization). For example, $\{f=0, s=0\}$ is feasible. Therefore, $p^\star \geq 12f + 9s = 0$. Since any feasible point yields a lower bound of $p^\star$ and $p^\star$ itself is yielded by an feasible point, then finding the largest lower bound of $p^\star$ is equivalent to solving the LP.
Read note →