Sparse Randomized Approximation of Normal Cycles

1. Problem Statement

In computational anatomy and geometric learning, comparing shapes (curves and surfaces) often requires metrics that are independent of parametrisation. While currents and varifolds provide correspondence-free metrics by embedding shapes into the dual of a Reproducing Kernel Hilbert Space (RKHS), they are limited to first-order geometric information (tangent/normal directions). They fail to capture higher-order properties like curvature, boundaries, and branching points, which are critical for matching complex anatomical structures.

The normal cycle representation addresses this by integrating over the unit normal bundle, capturing curvature and boundary information. However, computing the normal cycle metric is computationally prohibitive for large-scale data:

• Complexity: The metric scales as $O(MN)$ for surfaces with $M$ and $N$ edges.
• Cost: Even with optimized libraries (e.g., KeOps), computing normal cycle metrics and their gradients is 3–5 times more expensive than currents/varifolds.
• Scalability: The method becomes intractable for high-resolution meshes ($N, M \sim 10^5$), limiting its use in Large Deformation Diffeomorphic Metric Mapping (LDDMM) frameworks.

The paper aims to develop a sparse randomised compression algorithm for normal cycles that reduces computational complexity while maintaining theoretical guarantees on approximation error.

2. Methodology

The proposed methodology extends the randomised projection algorithm (previously applied to currents/varifolds) to the more complex setting of normal cycles. The approach involves three main stages:

A. Dirac Delta Decomposition

To apply compression, the authors first derive an explicit Dirac delta decomposition for discrete embedded normal cycles under a constant normal kernel ($K_s = 1$).

• Decomposition: The normal cycle $N(T)$ of a triangulated surface is decomposed into three orthogonal components in the dual space $W^*$:
  1. Planar Component: Proven to be zero for $K_s=1$.
  2. Cylindrical Component: Associated with edges. It is approximated by a sum of Dirac deltas at edge centers with specific vector weights derived from edge vectors and adjacent triangle normals.
  3. Spherical Component: Associated with boundary vertices. It is represented as Dirac deltas at boundary vertices with weights derived from the sum of normalized boundary edges.
• Result: The normal cycle is expressed as a sparse sum:
  $$N(T) \approx \sum_{i} \delta_{c_i} \gamma_i + \sum_{k} \delta_{x_k} \alpha_k$$
  where $\gamma_i$ and $\alpha_k$ are vector-valued weights in $\Lambda^2(\mathbb{R}^3 \times \mathbb{R}^3)$.

B. Vector-Valued Embedding

The compression algorithm of [1] requires the RKHS to consist of vector-valued functions. Since the normal cycle weights lie in the exterior algebra $\Lambda^2(\mathbb{R}^6)$, the authors construct an isometric isomorphism mapping this space to $\mathbb{R}^{15}$.

• This allows the normal cycle to be treated as an element of the dual of an RKHS of $\mathbb{R}^{15}$-valued functions, enabling the direct application of existing randomised compression techniques.

C. Randomised Compression via Ridge Leverage Scores (RLS)

The core compression algorithm (Algorithm 1) uses Ridge Leverage Score (RLS) sampling to select a small subset of control points ($m \ll n$) from the original set of $n$ Dirac centers.

1. Sampling: $m$ control points are sampled from the original set based on their RLS, which prioritizes points that contribute most to the RKHS norm.
2. Projection: The weights for the new sparse representation are computed via an orthogonal projection (solving a linear system involving the kernel matrix of the sampled points).
3. Complexity: The compression reduces the metric computation complexity from $O(n^2)$ to $O(m^2)$ (or $O(mn)$ depending on implementation), where $m \ll n$.

3. Key Contributions

1. First Compression Algorithm for Normal Cycles: This is the first work to investigate and implement compression specifically for the normal cycle representation, extending previous work on currents and varifolds.
2. Explicit Decomposition: The authors derive a rigorous Dirac delta decomposition for discrete normal cycles under a constant normal kernel, separating cylindrical (edge) and spherical (boundary) contributions.
3. Theoretical Guarantees: The method inherits the theoretical error bounds from the underlying randomised approximation theory. For Gaussian kernels, the error decays exponentially:
   $$\|\mu - \hat{\mu}\|_{W^*}^2 \leq O(m \exp(-\alpha m^{1/d}))$$
   This ensures that high compression ratios result in negligible loss of geometric fidelity.
4. Scalability: The algorithm enables the application of normal cycle metrics to large-scale datasets ($N \sim 10^5$) that were previously computationally infeasible.

4. Experimental Results

The authors validated the method on modern geometry processing datasets (Cat, Head, Flamingo, Queen, PumpkinHead) using LDDMM registration tasks.

• Error Decay: The compression error decays rapidly as the number of control points $m$ increases, closely matching the theoretical trace bound and significantly outperforming uniform sampling.
• Compression Ratios:
  • Queen Surface: Compressed from 344,664 to 10,000 centers (>97% compression).
  • PumpkinHead Surface: Compressed from 591,765 to 5,000 centers (>99% compression).
• Registration Quality:
  • Accuracy: The Hausdorff distance between the compressed and uncompressed registration results was negligible (e.g., $d_H = 0.0442$ vs $0.0298$ for the Queen surface). In some cases, the compressed version yielded slightly better registration quality.
  • Visuals: Visual inspection of the registered shapes showed no discernible difference between full and compressed methods.
• Performance Speed-up:
  • Queen Surface: Runtime reduced from 2 hours 42 minutes to 17 minutes (~10x speed-up).
  • PumpkinHead Surface: Runtime reduced from 5 hours 37 minutes to 17 minutes (~20x speed-up).

5. Significance

• Enabling High-Fidelity Geometric Learning: By making the theoretically superior normal cycle metric computationally feasible for large-scale data, this work allows researchers to leverage curvature and boundary information in statistical shape modeling and medical imaging without the prohibitive cost.
• Efficiency in LDDMM: The method significantly accelerates the most expensive part of the LDDMM pipeline (metric and gradient computation), making high-resolution diffeomorphic registration practical.
• Theoretical Rigor: The work bridges the gap between geometric measure theory and practical machine learning by providing a sparse approximation with provable error bounds, ensuring that the compressed representation remains a faithful proxy for the true shape geometry.

Future Work: The authors note that extending this compression to linear and Gaussian normal kernels (to capture even more curvature sensitivity) is a promising direction for future research.