Sparse Randomised Approximation of Normal Cycles
Allen Paul, Neill Campbell, Tony Shardlow · 2025
Read Sparse Randomised Approximation of Normal Cycles by Allen Paul, Neill Campbell, Tony Shardlow (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-01057.txt.
Introduction
Allen Paul, Neill Campbell, and Tony Shardlow present a method to compress a shape representation used in medical image analysis, in work from 2025. The representation, called a normal cycle, captures the geometry of a surface for tasks like aligning shapes across scans. Full representations are large and slow to use.
Their algorithm builds a sparse stand-in using sampling rules from kernel methods, picking the most informative points. They prove bounds on how fast the compression error falls. The stand-ins still work well for shape registration in a standard mapping framework, even at very high compression ratios. Tests on large modern shape datasets show big speed gains for registration. The method extends the team's earlier compression work on related shape objects.
Catalog record
| CREATOR | Allen Paul, Neill Campbell, Tony Shardlow |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-01057
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sparse Randomised Approximation of Normal Cycles Allen Paul, Neill Campbell, Tony Shardlow Abstract We extend our work (2026) for compression of currents and varifolds to a compression algorithm for the embedded normal cycles representation of shape, restricted to the constant normal kernel case, using the Nystrom approximation in Reproducing Kernel Hilbert Spaces (RKHS) and Ridge Leverage Score (RLS) sampling. Our method comes with theoretical guarantees on the compression error decay, and the approximations are shown to be effective for downstream tasks such as nonlinear shape registration in the Large Deformation Diffeomorphic Metric Mapping (LDDMM) framework, even for very high compression ratios. The performance of our algorithm is demonstrated on large-scale shape data from modern geometry processing datasets and is shown to accelerate downstream registration tasks significantly. keywords normal cycles, compression, Nystrom approximation, randomised approximation, shape registration, LDDMM 1 Introduction In many real-world geometric learning applications — for example, in computational anatomy — one wishes to build statistical models of shape variation, where the shape data are available as discrete curves and surfaces representing anatomical structures Younes (2010) . In order to fit such models, one requires a fidelity metric on shapes in order to compare the data to shapes generated by the model and tune the model parameters. In the majority of such applications, shapes do not have a consistent parametrisation, meaning that simple fidelity metrics relying on known correspondences cannot be used. A large literature has been developed on point-cloud metrics Dubuisson and Jain (1994) ; Wu et al. (2021) such as Chamfer and Hausdorff distance, as well as methods for extracting dense correspondences van Kaick et al. (2011) between shapes. However, in general, point-cloud distances are not geometric and do not account for the underlying structure of the shapes. Furthermore, dense correspondences may not be well defined or unique, which introduces a bias in subsequent shape learning applications. In the case where shape data are available as submanifolds of \mathbb{R}^{d} , one can deal with the lack of parametric correspondences in a more principled manner, using techniques from geometric measure theory Charon et al. (2020) . In particular, the so-called currents Vaillant and Glaunès (2005) and varifolds Charon and Trouvé (2013) representations view shapes as objects that integrate a family of continuous differential forms on the underlying domain, effectively embedding the shapes into the dual space of a space of differential forms. By restricting to differential forms lying in a Reproducing Kernel Hilbert space (RKHS) Aronszajn (1950) , one may use the dual metric on the embeddings in order to compare shapes in terms of their action on forms, independent of their parametrisations. The computation of the dual metric between submanifolds can be written down in closed form in terms of the positive semidefinite kernel function k\colon\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R} associated to the RKHS. One may compute the RKHS embeddings and metrics between discrete shape data in a way that is consistent as the discrete shapes tend to the underlying continuous submanifold. This framework and the resulting shape metrics have been used extensively in the Large Deformation Diffeomorphic Metric Mapping (LDDMM) framework Charon et al. (2020) for matching shapes with diffeomorphisms. While currents and varifolds metrics allow for geometric comparison of shapes in a correspondence-less manner, these representations only take into account first-order geometric information, such as tangent and normal vector directions. The structures typically present in real-world applications have regions of high curvature, branching points or distinguished boundaries; in such cases, currents and varifolds metrics are limited as they do not capture ‘higher-order’ properties of the underlying submanifold. Indeed, undesirable features may be generated during diffeomorphic registration when these metrics are used as discrepancy terms for matching complex shapes with the aforementioned features Charon et al. (2020) . A theoretically grounded solution is the normal cycles representation, which originates in geometric measure theory Federer (1996) ; Federer (1959) and has been applied to computational anatomy and LDDMM Roussillon (2017) ; Roussillon and Glaunès (2019) . Whereas the current associated to a surface integrates test differential forms over the surface itself, the normal cycle integrates them over the surface’s unit normal bundle , yielding an enriched representation that is sensitive not only to the surface but also to the rate of change of its normal vectors. As a consequence, the normal cycle locally encodes the mean and Gaussian curvatures of the surface Roussillon (2017) . In a similar manner to currents and varifolds, one may compute the distance between two shapes in terms of the dual metric between their normal cycles, embedded into the dual of a suitable RKHS of forms. The advantages of comparing shapes with normal cycles instead of currents or varifolds are evidenced numerically on shapes with high curvature regions, boundaries and branching points in Roussillon and Glaunès (2019) . However, the practical computation of the normal cycles metric is costly in terms of both memory and computational complexity. The normal cycles metric complexity scales as \mathcal{O}(MN) when comparing triangulated surfaces with M,N edges, respectively. While tools such as the KeOps library Charlier et al. (2021) exist for large-scale metric (and gradients) computation, it is observed empirically in Roussillon and Glaunès (2019) that even with these tools, the normal cycles representation is at least 3 – 5 times more expensive to compute and take gradients of than currents and varifolds and can become very slow for large-scale problems with resolution past 10^{5} . 1.1 Contribution In this work, we extend the randomised projection algorithm of (2026) from currents and varifolds to normal cycles. Building on Roussillon and Glaunès (2019) , we derive an explicit Dirac delta basis form for the discrete embedded normal cycle in the constant normal kernel case (as in Roussillon and Glaunès (2019) ), which lets us apply the main theorem of (2026) and compress a target normal cycle of size M to a sparse approximation of size m\ll M . Post-compression, the metric between two compressed normal cycles can be computed in \mathcal{O}(m^{2}) rather than \mathcal{O}(M^{2}) , with the corresponding gain in gradient cost. To our knowledge this is the first compression algorithm for normal cycles, allowing the metric to scale to problems with resolution M\sim 10^{5} . The theoretical guarantees of (2026) carry over directly, yielding exponential error-decay bounds (for Gaussian RKHS kernels) of the form \displaystyle\left\lVert\mu-\hat{\mu}\right\rVert_{W^{*}}^{2}\leq\mathcal{O}(m\exp(-\alpha m^{\frac{1}{d}})), where \hat{\mu} is the approximation of size m\ll M to the original normal cycle \mu\in W^{*} and \alpha>0 . The practical benefits are demonstrated in Section 4 , where we obtain order-of-magnitude acceleration of LDDMM registration on heavily over-sampled real-world surface data; the downstream utility of Algorithm 1 is further demonstrated in the companion work Hartshorne et al. (2025b) , where it is the core matching metric in a learning-based pipeline. 1.2 Existing work Compression of currents and varifolds has been studied previously in Durrleman et al. (2009) ; Hsieh and Charon (2021) , but the methods of those works are substantially slower than the ridge-leverage-score scheme of (2026) on which we build, and do not readily extend to the normal cycles setting. Other work on normal cycles Roussillon (2017) ; Roussillon and Glaunès (2019) ; Cohen-Steiner and Morvan (2003) has focused on formulation and on applications to surface registration and curvature estimation, not on