Exterior powers play important roles in persistent homology in computational geometry. In the present paper we study the problem of extracting the K longest intervals of the exterior-power layers \(\varLambda ^i M\) of a tame persistence module M, directly from the barcode \(B(M)\) , without enumerating the entire \(B(\varLambda ^i M)\) . We prove a structural decomposition theorem that organizes \(B(\varLambda ^i M)\) into monotone per-anchor streams with explicit multiplicities, enabling a best-first algorithm. We provide an \(O\bigl ((M+K)\log M\bigr )\) time algorithm for any fixed \(i \ge 2\) , obtained via a grouped best-first search. We also show that the Top-K length vector is 2-Lipschitz under bottleneck perturbations of the input barcode, and prove a comparison-model lower bound implying the \(O(M\log M)\) preprocessing is information-theoretically unavoidable. Our experiments confirm the theory, showing speedups over full enumeration in high overlap cases. By enabling efficient extraction of the most prominent features, our approach makes higher-order persistence feasible for large datasets and thus broadly applicable to machine learning, data science, and scientific computing.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Top-K Exterior Power Persistent Homology: Algorithm, Structure, and Stability

  • Yoshihiro Maruyama

摘要

Exterior powers play important roles in persistent homology in computational geometry. In the present paper we study the problem of extracting the K longest intervals of the exterior-power layers \(\varLambda ^i M\) of a tame persistence module M, directly from the barcode \(B(M)\) , without enumerating the entire \(B(\varLambda ^i M)\) . We prove a structural decomposition theorem that organizes \(B(\varLambda ^i M)\) into monotone per-anchor streams with explicit multiplicities, enabling a best-first algorithm. We provide an \(O\bigl ((M+K)\log M\bigr )\) time algorithm for any fixed \(i \ge 2\) , obtained via a grouped best-first search. We also show that the Top-K length vector is 2-Lipschitz under bottleneck perturbations of the input barcode, and prove a comparison-model lower bound implying the \(O(M\log M)\) preprocessing is information-theoretically unavoidable. Our experiments confirm the theory, showing speedups over full enumeration in high overlap cases. By enabling efficient extraction of the most prominent features, our approach makes higher-order persistence feasible for large datasets and thus broadly applicable to machine learning, data science, and scientific computing.