Shape Analysis Homeworks
Homeworks in MIT 6.838: Shape Analysis.
Homework 1: Discrete and Smooth Curves
Discrete Curvature of a Plane Curve
Gradient \(\nabla_{\mathbf{x}_i} s\)
\[\nabla_{\mathbf{x}_i} s =\frac{\mathbf{x}_i - \mathbf{x}_{i-1}}{\Vert \mathbf{x}_i - \mathbf{x}_{i-1} \Vert_2} + \frac{\mathbf{x}_i - \mathbf{x}_{i+1}}{\Vert \mathbf{x}_i - \mathbf{x}_{i+1} \Vert_2}\]
Discrete Curvature
\[\kappa = 2 \sin \frac{\theta}{2}\]
Curve Shortening Flow
\[\mathbf{x}_i' = \mathbf{x}_i - (\nabla_{\mathbf{x}_i} s) h\]
Discrete Elastic Rods
Homework 2: Surfaces and Curvature
Mean Curvature Flow with Explicit Integrator
\[\frac{\mathbf{p} (t+\tau) - \mathbf{p} (t)}{\tau} = - \mathbf{M}^{-1} (\mathbf{p} (t)) \cdot \mathbf{L} (\mathbf{p} (t)) \cdot \mathbf{p} (t)\] \[\mathbf{p} (t+\tau) = \mathbf{p} (t) - \tau \mathbf{M}^{-1} (\mathbf{p} (t)) \cdot \mathbf{L} (\mathbf{p} (t)) \cdot \mathbf{p} (t)\]
Mean Curvature Flow with (Semi-)Implicit Integrator
\[\frac{\mathbf{p} (t+\tau) - \mathbf{p} (t)}{\tau} = - \mathbf{M}^{-1} (\mathbf{p} (t)) \cdot \mathbf{L} (\mathbf{p} (t)) \cdot \mathbf{p} (t+\tau)\] \[\mathbf{p} (t+\tau) =\bigg(\mathbf{I} + \tau \mathbf{M}^{-1} (\mathbf{p} (t)) \cdot \mathbf{L} (\mathbf{p} (t)) \bigg)^{-1} \cdot \mathbf{p} (t)\]
Non-Singular Mean Curvature Flow
\[\mathbf{p} (t+\tau) = \bigg(\mathbf{I} + \tau \mathbf{M}^{-1} (\mathbf{p} (t)) \cdot \mathbf{L} (\mathbf{p} (0)) \bigg)^{-1} \cdot \mathbf{p} (t)\]
Homework 3: Geodesics, Distance, and Metric Embedding
Swiss-Roll DataSet
Maximum Variance Unfolding
Homework 4: Laplacian and Vector Fields
Helmholtz Decomposition
- \[\nabla \cdot V = \nabla \cdot \nabla \zeta = \Delta \zeta\]
- \[\nabla \times W = V - \nabla \zeta\]
Geodesic Distance from the Laplacian
Heat Kernel & Normalized Gradient
Divergences
Geodesic Distances
Parallel Transport from the Connection Laplacian
Operator Approach to Tangent Vector Fields
Scalar Field Advection
Manifold Optimization and Optimal Transport
Optimal Transport
(a) \(W(\mathbf{p}, \mathbf{q})\) measures the minimum cost of transporting \(\mathbf{p}\) to \(\mathbf{q}\).
(b) Let \(K_\alpha = e^{-\frac{C}{\alpha}}\), then
\[\begin{aligned} \alpha \cdot \text{KL} (T \Vert K_\alpha) &= \alpha \cdot \sum_{ij} T_{ij} \bigg( \ln{\frac{T_{ij}}{(K_\alpha)_{ij}}} -1 \bigg) = \alpha \cdot \bigg( \sum_{ij} T_{ij} \big( \ln{T_{ij}}-1 \big) - \sum_{ij} T_{ij} \ln{(K_\alpha)_{ij}} \bigg) \\ &= \alpha \cdot \bigg( \sum_{ij} T_{ij} \ln{T_{ij}} - 1 \bigg) + \alpha \cdot \sum_{ij} T_{ij} \cdot \bigg( \frac{C_{ij}}{\alpha} \bigg) \\ &= \sum_{ij} T_{ij} \cdot C_{ij} + \alpha \cdot \bigg( \sum_{ij} T_{ij} \ln{T_{ij}} - 1 \bigg) \end{aligned}\](c) The Lagrange could be expressed as:
\[\mathcal{L} (T; \lambda, \mu) = \sum_{ij} T_{ij} \cdot C_{ij} + \alpha \cdot \bigg( \sum_{ij} T_{ij} \ln{T_{ij}} - 1 \bigg) + \sum_i \lambda_i \cdot \bigg( \sum_j T_{ij} - p_i \bigg) + \sum_j \mu_j \cdot \bigg( \sum_i T_{ij} - q_j \bigg)\]where \(\lambda_i\) and \(\mu_j\) are Lagrange multipliers.
Taking derivative of \(T_{ij}\), we have:
\[\frac{\partial \mathcal{L}}{\partial T_{ij}} = C_{ij} + \alpha ( \ln{T_{ij}} + 1 ) + \lambda_i + \mu_j = 0\]which implies:
\[T_{ij} = \exp \bigg\{ - \frac{C_{ij} + \lambda_i + \mu_j}{\alpha} - 1 \bigg\} = e^{-\frac{\lambda_i}{\alpha}-\frac{1}{2}} \cdot e^{-\frac{C_{ij}}{\alpha}} \cdot e^{-\frac{\mu_j}{\alpha}-\frac{1}{2}}\]Thus,
\[T = \text{diag}(\mathbf{v}) \cdot K_\alpha \cdot \text{diag}(\mathbf{w})\]where
\[\mathbf{v}_i = e^{-\frac{\lambda_i}{\alpha}-\frac{1}{2}}\] \[\mathbf{w}_j = e^{-\frac{\mu_j}{\alpha}-\frac{1}{2}}\](d) When \(\alpha\) is small enough, we have
\[C_{ij} = d^2(x_i, x_j) \approx -2 \times \frac{\alpha}{2} \ln \mathcal{H}_{\frac{\alpha}{2}} (x_i, x_j)\]Thus,
\[\mathcal{H}_{\frac{\alpha}{2}} (x_i, x_j) \approx e^{-\frac{C_{ij}}{\alpha}} = (K_\alpha)_{ij}\](e) If \(k\) is odd, the Lagrange could be expressed as
\[\begin{aligned} \mathcal{L} (T; \lambda) &= \text{KL} (T \Vert T^{(k-1)}) + \sum_i \lambda_i \cdot \bigg( \sum_j T_{ij} - p_i \bigg) \\ &= \sum_{ij} T_{ij} \bigg( \ln{T_{ij}} - \ln{T^{(k-1)}_{ij}} -1 \bigg) + \sum_i \lambda_i \cdot \bigg( \sum_j T_{ij} - p_i \bigg) \\ &= \sum_{ij} T_{ij} \bigg( \ln{T_{ij}} - \ln{T^{(k-1)}_{ij}} \bigg) + \sum_i \lambda_i \cdot \bigg( \sum_j T_{ij} - p_i \bigg) - 1 \end{aligned}\]Taking derivative of \(T_{ij}\), we have
\[\frac{\partial \mathcal{L}}{\partial T_{ij}} = \bigg( \ln{T_{ij}} - \ln{T^{(k-1)}_{ij}} \bigg) + 1 + \lambda_i = 0\]Thus,
\[T_{ij} = \frac{T^{(k-1)}_{ij}}{e^{1+\lambda_i}}\]This implies that
\[T^{(k)} = \text{diag}(\mathbf{\tilde{v}}^{(k)}) \cdot T^{(k-1)}\]where
\[\mathbf{\tilde{v}}^{(k)}_i = \frac{1}{e^{1+\lambda_i}}\]Similarly, when \(k\) is even, we have
\[T_{ij} = \frac{T^{(k-1)}_{ij}}{e^{1+\mu_j}}\]where \(\mu_j\) is the Lagrange multiplier. Then,
\[T^{(k)} = T^{(k-1)} \cdot \text{diag}(\mathbf{\tilde{w}}^{(k)})\] \[\mathbf{\tilde{w}}^{(k)}_j = \frac{1}{e^{1+\mu_j}}\]Putting these together, we derive the iteration
\[\begin{aligned} T^{(k)} &= \text{diag}(\mathbf{v}^{(k)}) \cdot T^{(0)} \cdot \text{diag}(\mathbf{w}^{(k)}) \\ &= \text{diag}(\mathbf{v}^{(k)}) \cdot \mathcal{H}_{\frac{\alpha}{2}} \cdot \text{diag}(\mathbf{w}^{(k)}) \end{aligned}\]Now we only need to determine the vectors \(\mathbf{v}^{(k)}\) and \(\mathbf{w}^{(k)}\). Suppose \(k\) is odd, the constraints of \(p_i\) gives
\[p_i = \sum_j T^{(k)}_{ij} = \mathbf{\tilde{v}}^{(k)}_i \cdot \sum_j T^{(k-1)}_{ij}\]Thus,
\[\mathbf{\tilde{v}}^{(k)}_i = \frac{p_i}{\sum_j T^{(k-1)}_{ij}} = \frac{p_i}{\sum_j T^{(k-2)}_{ij} \tilde{\mathbf{w}}^{(k-1)}_j}\]Similarly, when \(k\) is even we have
\[q_j = \sum_i T^{(k)}_{ij} = \mathbf{\tilde{w}}^{(k)}_j \cdot \sum_i T^{(k-1)}_{ij}\] \[\mathbf{\tilde{w}}^{(k)}_j = \frac{q_j}{\sum_i T^{(k-1)}_{ij}} = \frac{q_j}{\sum_i T^{(k-2)}_{ij} \tilde{\mathbf{v}}^{(k-1)}_i}\]Now we derive the Sinkhorn iteration step:
\[\mathbf{v} \leftarrow \mathbf{p} \oslash (T \cdot \mathbf{w})\] \[\mathbf{w} \leftarrow \mathbf{q} \oslash (\mathbf{v} \cdot T)\]where \(\oslash\) is the elementwise division operator.
(f)
