CSE 535: Homework #0

Linear algebra

• Let $A \in \mathbb{R}^{m \times n}$ and $B \in \mathbb{R}^{n \times m}$ be two rectangular matrices. Prove that $\mathrm{Tr}(AB)=\mathrm{Tr}(BA)$.

• If $1 \leq p \leq q < \infty$, show that

  $$\|x\|_q \leq \|x\|_p \leq n^{1/p-1/q} \|x\|_q, \quad \forall x \in \mathbb{R}^n,$$

  where $\|x\|_p$ denotes the $\ell_p$ norm of a vector $x \in \mathbb{R}^n$.

• Show that $M(M+I)^{-1} M \succeq \frac12 I$ for a symmetric matrix $M$ satisfying $M \succeq I$ (hint: use the eigenvector decomposition of $M$).

Calculus

• Consider a differentiable function $f : \mathbb{R} \to \mathbb{R}$ and an $m \times n$ matrix $A$. Define $\Phi(x) = \sum_{i=1}^m f(\sum_{j=1}^n A_{ij} x_j)$. Show that the gradient is given by

  $$\nabla \Phi(x) = A^{\top} f'(Ax),$$

  and the Hessian is given by

  $$\nabla^2 \Phi(x) = A^{\top} \mathrm{diag}(f''(Ax)) A,$$

  where $\mathrm{diag}(u)$ is defined as the diagonal matrix with the entries of the vector $u$ on the diagonal, and we use $f’(Ax)$ to denote the vector $f’(Ax)_i = f’((Ax)_i)$.

• Consider the function $f : \mathbb{R}^n \to \mathbb{R}$ defined by

  $$f(x) = \log \left(\sum_{i=1}^m \exp(a_i^{\top} x + b_i)\right),$$

  where $a_1,a_2,\ldots,a_m \in \mathbb{R}^n$ and $b_1,b_2,\ldots,b_m \in \mathbb{R}$. Define the vector $z \in \mathbb{R}^m$ with $z_i = \exp(a_i^{\top} x + b_i)$.

  Show that

  $$\nabla f(x) = \frac{A^{\top} z}{\mathbf{1}^{\top} z},$$

  and

  $$\nabla^2 f(x) = A^{\top} \left(\frac{\mathrm{diag}(z)}{\mathbf{1}^{\top} z} - \frac{zz^{\top}}{(\mathbf{1}^{\top} z)^2}\right).$$