Efficient persistence landscape generation

Using topological summary tools such as persistence landscapes have greatly enhanced the practical usage of topological data analysis to analyze large-scale, noisy, and complex datasets. A central element of persistence landscape usage involves computing the top- <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>k</mml:mi> </mml:math> landscapes. This article presents a novel output-sensitive plane sweep algorithm for computing the top- <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>k</mml:mi> </mml:math> persistence landscapes in optimal time and space: significantly outperforming previous algorithms. Our algorithm can determine in optimal <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>*</mml:mo> <mml:mrow> <mml:mi mathvariant="normal">log</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> </mml:math> if a given birth-death pair appears in the top- <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>k</mml:mi> </mml:math> landscapes. The runtime performance of the approach on a botnet dataset and several synthetically generated point cloud topologies, showing that the algorithm can achieve significant speedups for these datasets due to its better algorithmic design. The speedups seen range from slightly worse (in some extreme examples) to equal compared to previous works while returning exactly the same output and is significantly faster when filtering is used (15x for birth-death pairs when removing 75% of birth-death pairs). Filtering is shown to maintain machine learning performance on both synthetically generated and real world datasets while providing orders of magnitude speedup depending on how intensive of filtering is done. Due to the introduced algorithm’s algorithmic design, the speedup seen is greater when filtering using the introduced birth-death filtering algorithm. The software is freely provided in Rust with Python bindings online.