Shape Analysis Homeworks

Homeworks in MIT 6.838: Shape Analysis.

Homework 1: Discrete and Smooth Curves

Discrete Curvature of a Plane Curve

Gradient $\nabla_{x_{i}} s$

\nabla_{x_{i}} s = \frac{x_{i} - x_{i - 1}}{‖ x_{i} - x_{i - 1} ‖_{2}} + \frac{x_{i} - x_{i + 1}}{‖ x_{i} - x_{i + 1} ‖_{2}}

Discrete Curvature

κ = 2 \sin \frac{θ}{2}

Curve Shortening Flow

x_{i}^{'} = x_{i} - (\nabla_{x_{i}} s) h

Discrete Elastic Rods

Homework 2: Surfaces and Curvature

Mean Curvature Flow with Explicit Integrator

\frac{p (t + τ) - p (t)}{τ} = - M^{- 1} (p (t)) \cdot L (p (t)) \cdot p (t)

p (t + τ) = p (t) - τ M^{- 1} (p (t)) \cdot L (p (t)) \cdot p (t)

Mean Curvature Flow with (Semi-)Implicit Integrator

\frac{p (t + τ) - p (t)}{τ} = - M^{- 1} (p (t)) \cdot L (p (t)) \cdot p (t + τ)

p (t + τ) = (I + τ M^{- 1} (p (t)) \cdot L (p (t)))^{- 1} \cdot p (t)

Non-Singular Mean Curvature Flow

p (t + τ) = (I + τ M^{- 1} (p (t)) \cdot L (p (0)))^{- 1} \cdot 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 ζ = Δ ζ$
$\nabla \times W = V - \nabla ζ$

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 (p, q)$ measures the minimum cost of transporting $p$ to $q$ .

(b) Let $K_{α} = e^{- \frac{C}{α}}$ , then

\begin{aligned} α \cdot KL (T ‖ K_{α}) & = α \cdot \sum_{i j} T_{i j} (\ln \frac{T_{i j}}{(K_{α})_{i j}} - 1) = α \cdot (\sum_{i j} T_{i j} (\ln T_{i j} - 1) - \sum_{i j} T_{i j} \ln (K_{α})_{i j}) \\ = α \cdot (\sum_{i j} T_{i j} \ln T_{i j} - 1) + α \cdot \sum_{i j} T_{i j} \cdot (\frac{C_{i j}}{α}) \\ = \sum_{i j} T_{i j} \cdot C_{i j} + α \cdot (\sum_{i j} T_{i j} \ln T_{i j} - 1) \end{aligned}

(c) The Lagrange could be expressed as:

L (T; λ, μ) = \sum_{i j} T_{i j} \cdot C_{i j} + α \cdot (\sum_{i j} T_{i j} \ln T_{i j} - 1) + \sum_{i} λ_{i} \cdot (\sum_{j} T_{i j} - p_{i}) + \sum_{j} μ_{j} \cdot (\sum_{i} T_{i j} - q_{j})

where $λ_{i}$ and $μ_{j}$ are Lagrange multipliers.

Taking derivative of $T_{i j}$ , we have:

\frac{\partial L}{\partial T_{i j}} = C_{i j} + α (\ln T_{i j} + 1) + λ_{i} + μ_{j} = 0

which implies:

T_{i j} = \exp {- \frac{C_{i j} + λ_{i} + μ_{j}}{α} - 1} = e^{- \frac{λ_{i}}{α} - \frac{1}{2}} \cdot e^{- \frac{C_{i j}}{α}} \cdot e^{- \frac{μ_{j}}{α} - \frac{1}{2}}

Thus,

T = diag (v) \cdot K_{α} \cdot diag (w)

where

v_{i} = e^{- \frac{λ_{i}}{α} - \frac{1}{2}}

w_{j} = e^{- \frac{μ_{j}}{α} - \frac{1}{2}}

(d) When $α$ is small enough, we have

C_{i j} = d^{2} (x_{i}, x_{j}) \approx - 2 \times \frac{α}{2} \ln H_{\frac{α}{2}} (x_{i}, x_{j})

Thus,

H_{\frac{α}{2}} (x_{i}, x_{j}) \approx e^{- \frac{C_{i j}}{α}} = (K_{α})_{i j}

(e) If $k$ is odd, the Lagrange could be expressed as

\begin{aligned} L (T; λ) & = KL (T ‖ T^{(k - 1)}) + \sum_{i} λ_{i} \cdot (\sum_{j} T_{i j} - p_{i}) \\ = \sum_{i j} T_{i j} (\ln T_{i j} - \ln T_{i j}^{(k - 1)} - 1) + \sum_{i} λ_{i} \cdot (\sum_{j} T_{i j} - p_{i}) \\ = \sum_{i j} T_{i j} (\ln T_{i j} - \ln T_{i j}^{(k - 1)}) + \sum_{i} λ_{i} \cdot (\sum_{j} T_{i j} - p_{i}) - 1 \end{aligned}

Taking derivative of $T_{i j}$ , we have

\frac{\partial L}{\partial T_{i j}} = (\ln T_{i j} - \ln T_{i j}^{(k - 1)}) + 1 + λ_{i} = 0

Thus,

T_{i j} = \frac{T_{i j}^{(k - 1)}}{e^{1 + λ_{i}}}

This implies that

T^{(k)} = diag ({\tilde{v}}^{(k)}) \cdot T^{(k - 1)}

where

{\tilde{v}}_{i}^{(k)} = \frac{1}{e^{1 + λ_{i}}}

Similarly, when $k$ is even, we have

T_{i j} = \frac{T_{i j}^{(k - 1)}}{e^{1 + μ_{j}}}

where $μ_{j}$ is the Lagrange multiplier. Then,

T^{(k)} = T^{(k - 1)} \cdot diag ({\tilde{w}}^{(k)})

{\tilde{w}}_{j}^{(k)} = \frac{1}{e^{1 + μ_{j}}}

Putting these together, we derive the iteration

\begin{aligned} T^{(k)} & = diag (v^{(k)}) \cdot T^{(0)} \cdot diag (w^{(k)}) \\ = diag (v^{(k)}) \cdot H_{\frac{α}{2}} \cdot diag (w^{(k)}) \end{aligned}

Now we only need to determine the vectors $v^{(k)}$ and $w^{(k)}$ . Suppose $k$ is odd, the constraints of $p_{i}$ gives

p_{i} = \sum_{j} T_{i j}^{(k)} = {\tilde{v}}_{i}^{(k)} \cdot \sum_{j} T_{i j}^{(k - 1)}

Thus,

{\tilde{v}}_{i}^{(k)} = \frac{p_{i}}{\sum_{j} T_{i j}^{(k - 1)}} = \frac{p_{i}}{\sum_{j} T_{i j}^{(k - 2)} {\tilde{w}}_{j}^{(k - 1)}}

Similarly, when $k$ is even we have

q_{j} = \sum_{i} T_{i j}^{(k)} = {\tilde{w}}_{j}^{(k)} \cdot \sum_{i} T_{i j}^{(k - 1)}

{\tilde{w}}_{j}^{(k)} = \frac{q_{j}}{\sum_{i} T_{i j}^{(k - 1)}} = \frac{q_{j}}{\sum_{i} T_{i j}^{(k - 2)} {\tilde{v}}_{i}^{(k - 1)}}

Now we derive the Sinkhorn iteration step:

v \leftarrow p ⊘ (T \cdot w)

w \leftarrow q ⊘ (v \cdot T)

where $⊘$ is the elementwise division operator.

(f)