talks/matrix_derivative.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d7260252",
   "metadata": {},
   "source": [
    "# A Short Tutorial on Matrix Derivative\n",
    "\n",
    "### [Liu, Yuezhang](mailto:lyz@utexas.edu)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84a5dd40",
   "metadata": {},
   "source": [
    "I notice that the matrix derivative technique might be useful for the contents of the course, and fortunately I know a good tutorial introducing the technique, but unfortunately the materials are in Chineses, therefore I translate and summarize the main idea of the tutorial and hope it could be helpful.\n",
    "\n",
    "The contents are heavily borrowed from the [post](https://zhuanlan.zhihu.com/p/24709748) by 长躯鬼侠 (ECE PhD at CMU) on Zhihu (Chinese Quora)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef24d044",
   "metadata": {},
   "source": [
    "### The relation between differential and matrix derivative\n",
    "\n",
    "Consider the matrix function $f(X): \\mathcal{X}\\to\\mathbb{R}$, which maps a matrix $X\\in\\mathbb{R}^{n\\times d}$ into **a real number**. This is the common setting for calculus of variantions (e.g., backpropagation of neural networks, optimal control), as the loss/control objective should always be a real number to be optimized and evaluated.\n",
    "\n",
    "Recall why we are good at calculating the usual derivative: we basically calculate the derivative based on the composition of simple rules. For the matrix case, the chain rule of derivatives could be error-prone, that's what makes the problem complicated. But fortunately, the **composition of differentials** still holds. Indeed, the matrix derivative and differential are connected by the following relation\n",
    "\n",
    "$$df = \\textrm{tr}\\left(\\dfrac{\\partial f}{\\partial X}^TdX\\right),$$\n",
    "\n",
    "where $df\\in\\mathbb{R}$ has the same shape with $f$ and $dX,\\dfrac{\\partial f}{\\partial X}\\in\\mathbb{R}^{n\\times d}$ has the same shape with $X$, $\\textrm{tr}$ donotes the trace operator. Note that since $df$ is a scalar, $\\textrm{tr}(df)=df$, thus we could add trace on both sides.\n",
    "\n",
    "In all, to calculate the matrix derivative $\\dfrac{\\partial f}{\\partial X}$, our plan would be:\n",
    "- Take the differential of $f$ w.r.t. $X$, by the **composition of differentials**.\n",
    "- Add trace on both sides, and arange the terms into the key relation by **trace tricks**.\n",
    "- Directly readout the derivative from the **relation between differential and matrix derivative**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99a9ffd0",
   "metadata": {},
   "source": [
    "### Composition of differentials\n",
    "\n",
    "1. Addition: $d(X\\pm Y) = dX\\pm dY$; Matrix multiplication: $d(XY)=(dX)Y + XdY$; Transpose: $d(X^T)=(dX)^T$; Trace: $d\\textrm{tr}(X)=\\textrm{tr}(dX)$.\n",
    "2. Inverse: $dX^{-1}=-X^{-1}dXX^{-1}$.\n",
    "3. Determinant: $d|X|=\\textrm{tr}(X^*dX)$, where $X^*=\\overline{X}^T$ denotes the conjugate transpose.\n",
    "4. Element-wise multiplication: $d(X\\odot Y)=dX\\odot Y + X\\odot dY$.\n",
    "5. Element-wise function: $d\\sigma(X)=\\sigma'(X)\\odot dX$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69b77baa",
   "metadata": {},
   "source": [
    "### Trace tricks\n",
    "\n",
    "1. Scalar: $a=\\textrm{tr}(a)$.\n",
    "2. Transpose: $\\textrm{tr}(A^T)=\\textrm{tr}(A)$.\n",
    "3. Linear: $\\textrm{tr}(A\\pm B)=\\textrm{tr}(A)\\pm \\textrm{tr}(B)$.\n",
    "4. Commutativity of matrix multiplication: $\\textrm{tr}(AB)=\\textrm{tr}(BA)$, where $A$ and $B^T$ have the same shape.\n",
    "5. Commutativity of matrix/element-wise multiplication: $\\textrm{tr}(A^T(B\\odot C))=\\textrm{tr}((A\\odot B)^TC)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e745d41d",
   "metadata": {},
   "source": [
    "### Example: non-linear regression\n",
    "\n",
    "Consider a system $Y=\\sigma(WX)$, $X\\in\\mathbb{R}^{d\\times n}$ consists of $n$ data points, each is a $d$-dimensional vector, $W\\in\\mathbb{R}^{m\\times d}$, $Y\\in\\mathbb{R}^{m\\times n}$, $\\sigma(\\cdot)$ is some nonlinear function. Denote the label matrix as $\\hat{Y}\\in\\mathbb{R}^{m\\times n}$, then the MSE loss\n",
    "\n",
    "$$L = \\frac{1}{2n}tr\\left[(Y-\\hat{Y})^T(Y-\\hat{Y})\\right].$$\n",
    "\n",
    "Calculate $\\dfrac{\\partial L}{\\partial W}$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be3cc3e2",
   "metadata": {},
   "source": [
    "By composition of differentials\n",
    "\n",
    "$$ dL = \\frac{1}{2n}\\textrm{tr}\\left[dY^T(Y-\\hat{Y})+(Y-\\hat{Y})^TdY\\right]=\\frac{1}{n}\\textrm{tr}\\left[(Y-\\hat{Y})^TdY\\right] $$\n",
    "$$ =\\frac{1}{n}\\textrm{tr}\\left[(Y-\\hat{Y})^Td\\sigma(WX)\\right] = \\frac{1}{n}\\textrm{tr}\\left[(Y-\\hat{Y})^T(\\sigma'(WX)\\odot (dW X))\\right]. $$\n",
    "\n",
    "By trace trick 5\n",
    "$$dL = \\frac{1}{n}\\textrm{tr}\\left[[(Y-\\hat{Y})\\odot\\sigma'(WX)]^TdW X\\right].$$\n",
    "\n",
    "By trace trick 4\n",
    "$$dL = \\frac{1}{n}\\textrm{tr}\\left[X[(Y-\\hat{Y})\\odot\\sigma'(WX)]^TdW\\right].$$\n",
    "\n",
    "Therefore, from the relation between differential and matrix derivative, we have\n",
    "\n",
    "$$\\dfrac{\\partial L}{\\partial W} = \\left[(Y-\\hat{Y})\\odot\\sigma'(WX)\\right]X^T. $$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}