💻 computer science

Towards Scalable Persistence-Based Topological Optimization

This paper proposes a scalable framework for persistence-based topological optimization that combines random slicing for efficient subsampling with fast Nadaraya-Watson Gaussian convolution for smooth gradient extension, thereby overcoming computational bottlenecks and improving optimization performance in both 2D and 3D settings.

Original authors: Abderrahim Bendahi, Alexandre Duplessis, Arnaud Fickinger

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Abderrahim Bendahi, Alexandre Duplessis, Arnaud Fickinger

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, messy cloud of points (like a 3D model of a bunny made of thousands of tiny dots). Your goal is to gently push and pull these dots around to change the shape of the cloud, specifically to make certain "holes" or "tunnels" in the shape bigger or smaller. This is called topological optimization.

The problem is that figuring out exactly which dots to move is incredibly hard and slow. Here is the story of how this paper solves that problem, using simple analogies.

The Problem: The "Silent Majority"

Usually, when you calculate how to move the dots, the math only gives you a "push" instruction for a tiny handful of dots (the "anchors"). The rest of the thousands of dots get no instruction at all—they just sit there.

The Analogy: Imagine a conductor trying to lead an orchestra of 1,000 musicians. But the sheet music only tells 5 musicians what to play. The other 995 sit in silence. The music (the optimization) doesn't flow well, and it takes forever to get a good result because you keep having to re-calculate which 5 people need instructions.

The Old Solution: The "Expensive Translator"

A recent method tried to fix this by creating a smooth "wind" that blows across the whole cloud, carrying the instructions from the 5 active dots to the 995 silent ones.

The Analogy: This is like hiring a super-smart, expensive translator who writes a perfect, smooth speech for every single musician based on the 5 instructions.
The Catch: This translator is slow. Every time the conductor changes the music, the translator has to do a massive, complex math calculation (solving a "kernel system") to rewrite the speech for everyone. If you have a huge orchestra, this takes too long.

The New Solution: Two Simple Tricks

The authors propose a faster, smarter way to get the whole orchestra playing together. They use two main tricks:

Trick 1: The "Random Slice" (Better Sampling)

Instead of looking at the whole cloud or just picking dots randomly (which often ignores the sparse, quiet corners of the shape), they use a "Random Slice."

The Analogy: Imagine the cloud of dots is a loaf of bread. Instead of grabbing random crumbs from the top (which might just be the crust), you slice the loaf with a knife at a random angle. You then pick a few pieces of bread evenly spaced along that slice.
Why it helps: This ensures you get a good taste of the entire loaf, including the quiet, sparse edges, without needing to look at every single crumb. It stops the math from getting confused by crowded areas.

Trick 2: The "Nadaraya-Watson Smoother" (The Fast Wind)

Instead of hiring the expensive translator to solve a complex equation, they use a simple "voting" system to figure out how the wind should blow.

The Analogy: Imagine the 5 active dots are people shouting directions. The new method asks every silent dot: "Who are you closest to?" If a silent dot is near a dot shouting "Move Left," it moves Left. If it's halfway between "Move Left" and "Move Right," it takes a gentle average of both.
The Magic: This is done using a simple "Gaussian" formula (like a bell curve). It's incredibly fast because it doesn't require solving a hard math puzzle; it just does a quick weighted average. It creates a smooth, global wind that moves the whole cloud naturally, but it's much cheaper to compute than the old method.

The Results: Faster and Better

The authors tested this on a 3D model of a bunny (the "Stanford Bunny").

Speed: Their new method was almost as fast as doing nothing (just moving the 5 dots), but much, much faster than the old "expensive translator" method (which was 10 times slower).
Quality: Even though it was fast, it actually did a better job of shaping the bunny. It achieved a better "score" (lower loss) than the other methods.
Bonus: They even figured out how to teach the computer to automatically adjust the "wind strength" (a parameter called $\sigma$ ) while it works, so it doesn't have to guess the right settings manually.

Summary

The paper says: "Don't try to solve a hard math puzzle to move your 3D points. Instead, slice the data smartly to get a good view, and use a simple, fast 'voting' system to spread the movement instructions to the whole cloud. It's cheaper, faster, and works better."

Note: The paper focuses entirely on these mathematical improvements for 3D point clouds (like the bunny). It does not claim these methods are currently used for medical imaging, self-driving cars, or other real-world applications, though it suggests this makes the math more practical for future use.

Technical Summary: Towards Scalable Persistence-Based Topological Optimization

Problem Statement
Persistence-based topological optimization seeks to deform a point cloud $X \subset \mathbb{R}^d$ to minimize objectives of the form $L(X) = \ell(\text{Dgm}(X))$ , where $\text{Dgm}(X)$ is a persistence diagram. While theoretically sound due to the stability of persistent homology, practical implementation faces two coupled bottlenecks:

Subsampling Necessity: Computing persistent homology on large point clouds is computationally prohibitive, necessitating subsampling. However, standard uniform subsampling introduces density bias, often oversampling dense regions while missing sparse boundary areas critical for topological features.
Gradient Sparsity: The topological gradient is highly sparse; only a small set of "anchor" points (those involved in critical birth/death simplices) receive non-zero updates. Most points have zero gradients, slowing optimization.
Scalability of Smoothing: A recent remedy, diffeomorphic interpolation (Carrière et al., 2024), extends sparse gradients to a smooth ambient vector field using Reproducing Kernel Hilbert Space (RKHS) interpolation. However, this requires solving a kernel linear system at every iteration, which becomes computationally dominant ( $O(|I|^3)$ ) in large-scale settings.

Methodology
The authors propose a scalable pipeline that addresses both subsampling and gradient extension issues through two main components:

Subsampling via Random Slicing:
Instead of uniform sampling, the authors introduce a structured sampler inspired by sliced optimal transport.
- Mechanism: In each iteration, a random direction $u$ is drawn. Points are projected onto this 1D line ( $t_i = \langle x_i, u \rangle$ ) and sorted. The subsample is formed by selecting points at evenly spaced ranks in this sorted list.
- Benefit: This ensures global geometric coverage and mitigates density bias. By enforcing rank stratification, the method prevents dense clusters from monopolizing the sample budget, ensuring that sparse regions (e.g., boundaries between clusters) are consistently represented.
Nadaraya-Watson (NW) Gaussian Convolution:
To replace the costly RKHS kernel solve, the authors propose using a fast NW estimator to smooth the sparse anchor gradients into a global vector field.
- Mechanism: Given anchor points $x_i$ with gradients $g_i$ , the field at any point $x$ is defined as a weighted average: $\bar{v}(x) = \sum_{i \in I} w_i(x) g_i$ , where weights $w_i(x)$ are normalized Gaussian affinities $\exp(-\|x-x_i\|^2 / 2\sigma^2)$ .
- Advantages:
  - Computational Efficiency: It avoids solving a linear system, reducing the cost significantly.
  - Geometric Behavior: Unlike RKHS interpolation, which uses unnormalized kernels and can cause the field magnitude to vanish far from anchors, NW smoothing enforces a convex combination ( $\sum w_i = 1$ ). This ensures the field remains non-zero and behaves as a local barycentric average, providing a more robust propagation of sparse signals across the domain.
- Theoretical Guarantees: The paper provides bounds on anchor approximation error and establishes global Lipschitz continuity for the NW field, showing that the Lipschitz constant scales with $1/\sigma^2$ .
Adaptive Bandwidth Learning:
Recognizing that the bandwidth parameter $\sigma$ critically impacts performance, the authors propose learning $\sigma$ online via backpropagation. They parameterize $\sigma(\theta) = \sigma_0 \exp(\theta)$ and update $\theta$ to minimize a look-ahead loss, allowing the smoothing scale to adapt to the local optimization regime.

Key Contributions

Random Slicing: A lightweight subsampling scheme that improves geometric coverage and reduces density bias without requiring clustering or farthest-point sampling.
NW Smoothing: A replacement for exact kernel interpolation that offers a fast, normalized Gaussian convolution for extending sparse topological gradients, avoiding cubic-time linear solves.
Theoretical Analysis: Proofs of anchor approximation bounds and global Lipschitz estimates for the NW smoothing operator.
Empirical Validation: Demonstration of speedups and improved objective values on 2D and 3D tasks.

Experimental Results
The authors evaluated their method on a 3D topological augmentation task using the Stanford Bunny point cloud ( $n \approx 36,000$ ), aiming to strengthen 2D topological features (cavities).

Baselines: Compared against (i) Vanilla sparse gradient descent (no smoothing), (ii) Exact Kernel Diffeomorphic Interpolation, and (iii) The proposed NW-Convolution method.
Performance:
- Objective Value: The NW-Convolution method achieved a significantly lower loss ($-0.01869$) compared to both Vanilla ($-0.00026$) and Kernel ($-0.00151$) methods.
- Runtime: The NW method maintained a runtime per epoch ($2.573$s) comparable to the Vanilla baseline ($2.044$s) and was an order of magnitude faster than the Kernel method ($19.979$s).
Sensitivity: Experiments on a noisy 2D circle demonstrated high sensitivity to the bandwidth $\sigma$ , motivating the use of the proposed adaptive learning strategy.

Significance and Claims
The paper claims to address a central practical bottleneck in persistence-based optimization: the trade-off between the sparsity of topological gradients and the computational cost of smoothing them. By combining random slicing with NW smoothing, the authors provide a pipeline that is both scalable and effective.

The authors maintain a modest tone regarding their contribution. They state that their work is primarily a step toward making persistence-driven optimization more scalable and practical for settings involving large point sets and repeated PH computations. They explicitly note that their current evaluation is limited to controlled synthetic and standard geometry benchmarks (Stanford Bunny, 2D shapes) and that they do not yet demonstrate end-to-end impact on downstream real-world tasks. The work is positioned as a methodological improvement to the optimization loop itself rather than a new application domain.