We define a new framework that unifies the filtration and the mapper approaches from topological data analysis, and present efficient algorithms to compute it. Termed the box filtration of a point cloud data (PCD), we grow boxes (hyperrectangles) that are not necessarily centered at each point (in place of balls centered at each point as done by most current filtrations). We grow the boxes non-uniformly and asymmetrically in different dimensions based on the distribution of points. We present two approaches to handle the boxes: a point cover where each point is assigned its own box at start, and a pixel cover that works with a pixelization of the space of the PCD. Any box cover in either setting automatically gives a mapper of the PCD. We show that the persistence diagrams generated by the box filtration using both point and pixel covers satisfy the classical stability based on the Gromov-Hausdorff distance. Using boxes, rather than Euclidean balls, also implies that the box filtration is identical for pairwise or higher order intersections whereas the Vietoris-Rips (VR) and Čech filtration are not the same.Growth in each dimension is computed by solving a linear program that optimizes a cost functional balancing the cost of expansion and benefit of including more points in the box. The box filtration algorithm runs in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$O(m|\mathcal {U}(0)|\log (m n\pi ) \mathfrak {L}(q))$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mo stretchy="false">|</mo> <mi mathvariant="script">U</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> <mo>log</mo> <mo stretchy="false">(</mo> <mi>m</mi> <mi>n</mi> <mi>π</mi> <mo stretchy="false">)</mo> <mi mathvariant="fraktur">L</mi> <mo stretchy="false">(</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time, where m is number of steps of increments considered for growing the box, <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$|\mathcal {U}(0)|$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi mathvariant="script">U</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> </mrow> </math></EquationSource> </InlineEquation> is the number of boxes in the initial cover (at most the number of points), <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\pi $</EquationSource> <EquationSource Format="MATHML"><math> <mi>π</mi> </math></EquationSource> </InlineEquation> is the step length by which each box dimension is incremented, each linear program is solved in <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O(\mathfrak {L}(q))$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi mathvariant="fraktur">L</mi> <mo stretchy="false">(</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time, <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$n$</EquationSource> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> </InlineEquation> is the dimension of the PCD, and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$q = n \times |X|$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>q</mi> <mo>=</mo> <mi>n</mi> <mo>×</mo> <mo stretchy="false">|</mo> <mi>X</mi> <mo stretchy="false">|</mo> </mrow> </math></EquationSource> </InlineEquation>. We also present a faster algorithm that runs in <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$O(m|\mathcal {U}(0)|k \mathfrak {L}(q))$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mo stretchy="false">|</mo> <mi mathvariant="script">U</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> <mi>k</mi> <mi mathvariant="fraktur">L</mi> <mo stretchy="false">(</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> where k is the number of steps allowed to find the optimal box. We demonstrate through multiple examples that the box filtration can produce more accurate results to summarize the topology of the PCD than VR and distance-to-measure (DTM) filtrations. Software for our implementation is available <a href="https://github.com/pragup/Box-Filteration/">here</a>.

Box Filtration

期刊论文
发表日期：

2025年10月8日

查看全文

Enrique Alvarado,
Prashant Gupta,
Bala Krishnamoorthy

摘要

We define a new framework that unifies the filtration and the mapper approaches from topological data analysis, and present efficient algorithms to compute it. Termed the box filtration of a point cloud data (PCD), we grow boxes (hyperrectangles) that are not necessarily centered at each point (in place of balls centered at each point as done by most current filtrations). We grow the boxes non-uniformly and asymmetrically in different dimensions based on the distribution of points. We present two approaches to handle the boxes: a point cover where each point is assigned its own box at start, and a pixel cover that works with a pixelization of the space of the PCD. Any box cover in either setting automatically gives a mapper of the PCD. We show that the persistence diagrams generated by the box filtration using both point and pixel covers satisfy the classical stability based on the Gromov-Hausdorff distance. Using boxes, rather than Euclidean balls, also implies that the box filtration is identical for pairwise or higher order intersections whereas the Vietoris-Rips (VR) and Čech filtration are not the same.

Growth in each dimension is computed by solving a linear program that optimizes a cost functional balancing the cost of expansion and benefit of including more points in the box. The box filtration algorithm runs in $O(m|\mathcal {U}(0)|\log (m n\pi ) \mathfrak {L}(q))$ $O (m | U (0) | log (m n π) L (q))$ time, where m is number of steps of increments considered for growing the box, $|\mathcal {U}(0)|$ $| U (0) |$ is the number of boxes in the initial cover (at most the number of points), $\pi $ $π$ is the step length by which each box dimension is incremented, each linear program is solved in $O(\mathfrak {L}(q))$ $O (L (q))$ time, $n$ $n$ is the dimension of the PCD, and $q = n \times |X|$ $q = n \times | X |$ . We also present a faster algorithm that runs in $O(m|\mathcal {U}(0)|k \mathfrak {L}(q))$ $O (m | U (0) | k L (q))$ where k is the number of steps allowed to find the optimal box. We demonstrate through multiple examples that the box filtration can produce more accurate results to summarize the topology of the PCD than VR and distance-to-measure (DTM) filtrations. Software for our implementation is available here.