Week 2

Show your work and briefly explain what each numerical answer means in the context of the problem.

Problem 1

In lecture we used the matrices \(\bfA^\top\bfA\) and \(\bfA\bfA^\top\) to build the singular value decomposition. In this problem you will prove the facts about them that we relied on.

Recall that a symmetric matrix \(\bfM\in\Rbb^{n\times n}\) is positive semidefinite (PSD) if \(\bfx^\top\bfM\bfx\geq0\) for every \(\bfx\in\Rbb^n\). Throughout, let \(\bfA\in\Rbb^{m\times n}\) be any matrix.

  1. Show that \(\bfA^\top\bfA\) is symmetric and that \(\bfx^\top\bfA^\top\bfA\bfx=\|\bfA\bfx\|_2^2\) for every \(\bfx\in\Rbb^n\). Conclude that \(\bfA^\top\bfA\) is PSD.
  2. Explain why \(\bfA\bfA^\top\) is also PSD.
  3. Show that \(\operatorname{null}(\bfA^\top\bfA)=\operatorname{null}(\bfA)\).
  4. Conclude that \(\operatorname{rank}(\bfA^\top\bfA)=\operatorname{rank}(\bfA)\). Hint: see the rank–nullity theorem in the supplementary linear algebra notes.
NoteSolution sketch
  1. Since \((\bfA^\top\bfA)^\top=\bfA^\top(\bfA^\top)^\top=\bfA^\top\bfA\), the matrix is symmetric. For every \(\bfx\in\Rbb^n\), \[ \bfx^\top\bfA^\top\bfA\bfx =(\bfA\bfx)^\top(\bfA\bfx) =\|\bfA\bfx\|_2^2 \geq0, \] so \(\bfA^\top\bfA\) is PSD.
  2. Part 1 applies to any matrix. Applying it to \(\bfA^\top\) in place of \(\bfA\) shows that \((\bfA^\top)^\top\bfA^\top=\bfA\bfA^\top\) is PSD.
  3. If \(\bfA\bfx=\mathbf{0}\), then \(\bfA^\top\bfA\bfx=\bfA^\top\mathbf{0}=\mathbf{0}\). Conversely, if \(\bfA^\top\bfA\bfx=\mathbf{0}\), then by part 1, \[ \|\bfA\bfx\|_2^2=\bfx^\top(\bfA^\top\bfA\bfx)=0, \] so \(\bfA\bfx=\mathbf{0}\).
  4. Both \(\bfA\) and \(\bfA^\top\bfA\) have \(n\) columns, and by part 3 they have the same null space. By rank–nullity, \[ \operatorname{rank}(\bfA^\top\bfA) =n-\dim\operatorname{null}(\bfA^\top\bfA) =n-\dim\operatorname{null}(\bfA) =\operatorname{rank}(\bfA). \]

Problem 2

The SVD was stated in two forms, \[ \bfA=\bfU_r\Sigma_r\bfV_r^\top =\sum_{i=1}^r\sigma_i\bfu_i\bfv_i^\top. \] In lecture we proved the rank-one form by applying both sides to a vector \(\bfx\). In this problem you will check that the two forms agree by multiplying the matrices out directly. Write \(\bfe_1,\ldots,\bfe_r\in\Rbb^r\) for the standard basis vectors.

  1. Show that \[ \bfI_r=\sum_{k=1}^r\bfe_k\bfe_k^\top. \]
  2. Let \(\bfB\in\Rbb^{m\times r}\) have columns \(\bfb_1,\ldots,\bfb_r\) and let \(\bfC\in\Rbb^{r\times n}\) have rows \(\bfc_1^\top,\ldots,\bfc_r^\top\), so \(\bfb_i=\bfB\bfe_i\) and \(\bfc_i^\top=\bfe_i^\top\bfC\). Insert part 1 into \(\bfB\bfC=\bfB\bfI_r\bfC\) to conclude that \[ \bfB\bfC=\sum_{i=1}^r\bfb_i\bfc_i^\top. \] That is, a matrix product is the sum of the outer products of matching columns and rows.
  3. Apply part 2 to \(\bfB=\bfU_r\Sigma_r\) and \(\bfC=\bfV_r^\top\) to conclude that \(\bfU_r\Sigma_r\bfV_r^\top=\sum_{i=1}^r\sigma_i\bfu_i\bfv_i^\top\).
NoteSolution sketch
  1. \(\bfe_k\bfe_k^\top\) is the matrix with a \(1\) in the \((k,k)\) slot and zeros elsewhere, and summing over \(k\) fills in the diagonal.
  2. Using part 1 and associativity, \[ \bfB\bfC =\bfB\bfI_r\bfC =\bfB\left(\sum_{i=1}^r\bfe_i\bfe_i^\top\right)\bfC =\sum_{i=1}^r(\bfB\bfe_i)(\bfe_i^\top\bfC) =\sum_{i=1}^r\bfb_i\bfc_i^\top. \]
  3. Take \(\bfB=\bfU_r\Sigma_r\) and \(\bfC=\bfV_r^\top\) in part 2. Since \(\Sigma_r\bfe_i=\sigma_i\bfe_i\), the \(i\)-th column of \(\bfB\) is \(\bfb_i=\bfU_r\Sigma_r\bfe_i=\sigma_i\bfU_r\bfe_i=\sigma_i\bfu_i\), and the \(i\)-th row of \(\bfC\) is the transpose of the \(i\)-th column of \(\bfV_r\), namely \(\bfc_i^\top=\bfv_i^\top\). Hence \[ \bfU_r\Sigma_r\bfV_r^\top =\sum_{i=1}^r(\sigma_i\bfu_i)\bfv_i^\top =\sum_{i=1}^r\sigma_i\bfu_i\bfv_i^\top. \]

Problem 3

Let \(\bfQ\in\Rbb^{m\times m}\) be orthogonal, so \(\bfQ^\top\bfQ=\bfI_m\), and let \(\bfA\in\Rbb^{m\times n}\).

  1. Show that \(\|\bfQ\bfx\|_2=\|\bfx\|_2\) for every \(\bfx\in\Rbb^m\).
  2. What are the singular values of \(\bfQ\)?
  3. Show that \(\bfQ\bfA\) has the same singular values as \(\bfA\).
NoteSolution sketch
  1. \(\|\bfQ\bfx\|_2^2=\bfx^\top\bfQ^\top\bfQ\bfx=\bfx^\top\bfx=\|\bfx\|_2^2\).
  2. \(\bfQ^\top\bfQ=\bfI_m\) has every eigenvalue equal to \(1\), so every singular value of \(\bfQ\) is \(\sqrt1=1\).
  3. \((\bfQ\bfA)^\top(\bfQ\bfA)=\bfA^\top\bfQ^\top\bfQ\bfA=\bfA^\top\bfA\). Singular values are the square roots of the eigenvalues of this matrix, so they are unchanged.

Problem 4

Let \(\bfA\in\Rbb^{m\times n}\) have rank \(r\), and let \[ \bfA_k=\sum_{i=1}^k\sigma_i\bfu_i\bfv_i^\top \] be its rank-\(k\) truncated SVD for some \(0\leq k\leq r\). Storing a matrix means storing its entries, and storing \(\bfA_k\) means storing the factors \(\bfU_k\), \(\Sigma_k\), and \(\bfV_k\).

  1. How many numbers does it take to store \(\bfA\) itself? How many does it take to store \(\bfA_k\) in its rank-1 sum form? Explain where each term comes from.
  2. Write down the compression ratio \(\rho\), the storage for \(\bfA_k\) divided by the storage for \(\bfA\), in terms of \(m\), \(n\), and \(k\). Using this, derive a formula for selecting \(k\) given \(m\), \(n\), and a desired compression ratio \(\rho\).
NoteSolution sketch
  1. \(\bfA\) has \(mn\) entries, so it takes \(mn\) numbers. For \(\bfA_k\): \(\bfU_k\in\Rbb^{m\times k}\) contributes \(mk\) numbers, \(\bfV_k\in\Rbb^{n\times k}\) contributes \(nk\), and \(\Sigma_k\) is diagonal, so only its \(k\) diagonal entries \(\sigma_1,\ldots,\sigma_k\) need to be stored. The total is \[ mk+nk+k=k(m+n+1). \] Equivalently, each rank-one term \(\sigma_i\bfu_i\bfv_i^\top\) costs \(m+n+1\) numbers, and there are \(k\) of them.
  2. Dividing the two counts from part 1, \[ \rho=\frac{k(m+n+1)}{mn}. \] The ratio is linear in \(k\), so just invert. To hit a target compression ratio \(\rho\), take \[ k=\left\lfloor\frac{\rho\,mn}{m+n+1}\right\rfloor, \] the floor because \(k\) must be a whole number, and we round down so that the target is met rather than exceeded.