Week 8

Problem 1

Work through the notebook Spectral Embeddings (live). Again, this will not be on the quiz.

Problem 2

Let \(G\) be a weighted graph with no isolated vertices, Laplacian \(\bfL=\bfD-\bfW\), and let \(\bfY\in\Rbb^{n\times m}\) have rows \(\bfy_1^\top,\ldots,\bfy_n^\top\) and columns \(\bfy^{(1)},\ldots,\bfy^{(m)}\). In Lecture 17 we measured how far apart an embedding places neighbours by its energy \[ E(\bfY)=\frac12\sum_{i,j=1}^nw_{ij}\|\bfy_i-\bfy_j\|_2^2, \] and minimized it subject to \(\bfY^\top\bfD\mathbf{1}=\mathbf{0}\) and \(\bfY^\top\bfD\bfY=\bfI_m\).

  1. Show that \(E(\bfY)=\operatorname{tr}(\bfY^\top\bfL\bfY)\). Start from \(\|\bfy_i-\bfy_j\|_2^2=\sum_{c=1}^m(Y_{ic}-Y_{jc})^2\) and use the Laplacian quadratic form on each column.
  2. Let \(\bfQ\in\Rbb^{m\times m}\) be orthogonal. Show that row \(i\) of \(\bfY\bfQ\) is the point \(\bfQ^\top\bfy_i\), and use this to show \(E(\bfY\bfQ)=E(\bfY)\) directly from the definition of \(E\).
  3. Show \(E(\bfY\bfQ)=E(\bfY)\) again, this time from part 1 and the cyclic property of the trace.
  4. Show that if \(\bfY\) satisfies both constraints, then so does \(\bfY\bfQ\). Conclude that the Laplacian eigenmap is only the smoothest embedding up to a rotation or reflection of \(\Rbb^m\).

Problem 3

Read the example Unshredding an Image with One Eigenvector first. Here is the ideal case. Suppose that, with the columns (or rows, however it was shredded) in their original order \(0,1,\ldots,n-1\), the nearest-neighbour graph is exactly the path. That is, an edge of weight \(1\) between \(j\) and \(j+1\) for each \(j<n-1\), and no others.

Two copies of a drawing of Jumbo the elephant, each cut into twelve horizontal strips. On the left the strips are in their original order and show the whole elephant, trunk raised. To the right of each strip is a numbered dot, numbered 0 to 11 from top to bottom and colored from dark red at 0 through pale at 5 and 6 to dark blue at 11, and each dot is joined to the next by a short arc, forming a chain. On the right the same strips are shuffled, so the elephant is scrambled, and the dots, still carrying their original numbers and colors, appear from top to bottom in the order 1, 0, 3, 9, 8, 10, 7, 6, 2, 5, 4, 11. The same chain of arcs now joins dots far apart, forming long, nested arcs, and the colors no longer change steadily from top to bottom.

Jumbo, cut into twelve strips. Each strip is a vertex, labelled by its position \(j\) in the picture and colored by \(u_j\) (red for \(u_j\) near \(1\), blue near \(-1\)), and the arcs are the edges of the path. Left: the original order. Right: the same strips, vertices, and edges after shuffling.

You may use that the second eigenvalue \(\lambda_2\) of its Laplacian \(\bfL\) has multiplicity one, with eigenvector \[ u_j=\cos\big(\pi(j+\tfrac12)/n\big),\qquad j=0,\ldots,n-1. \] Shuffling moves column/row \(j\) to position \(\sigma(j)\), for a permutation \(\sigma\) we do not know. This relabels vertex \(j\) as \(\sigma(j)\), so the shuffled graph has weight matrix \(\bfW'=\bfP\bfW\bfP^\top\), where \(\bfP\bfe_j=\bfe_{\sigma(j)}\). For any vector \(\bfv\), the entry of \(\bfP\bfv\) at vertex \(\sigma(j)\) is \(v_j\).

  1. Show that the Laplacian of the shuffled graph is \(\bfL'=\bfP\bfL\bfP^\top\), and that \(\bfP\bfu\) is an eigenvector of \(\bfL'\) for \(\lambda_2\). Hint: \(\bfP^\top\mathbf{1}=\mathbf{1}\), and \(\bfP^\top\bfP=\bfI\).

  2. Show that \(u_0>u_1>\cdots>u_{n-1}\). Then explain why, whatever \(\sigma\) is, the vector \(\bfP\bfu\) gives the strip that started at position \(j\) the number \(u_j\).

  3. Explain why sorting the shuffled strips by their numbers in \(\bfP\bfu\), largest first, puts them back in their original order, even though we never learn \(\sigma\). Why might the restored picture come out as its mirror image?

  4. Here is a picture whose graph is not a path: two copies of Jumbo, side by side, cut into columns. Column \(j\) of the left copy is identical to column \(j\) of the right copy, so besides the path (grey), the graph joins \(j\) and \(j+6\) for \(j=0,\ldots,5\) (orange, dashed). Each vertex is colored by a Fiedler vector of this graph, which is again unique up to sign.

    Two copies of a drawing of Jumbo the elephant, side by side, cut into twelve vertical strips, six per copy. Below each strip is a dot numbered 0 to 11 from left to right. Grey arcs join each dot to the next, and orange dashed arcs join each dot j to dot j plus 6. The dots are colored by the Fiedler vector: 0 and 1 are red, 2 is pale, 3, 4 and 5 are blue, then 6 and 7 are red again, 8 is pale, and 9, 10 and 11 are blue.

    Which assumption above fails for this graph? Using the colors, explain why sorting by this Fiedler vector does not put the strips back in order.