Merge trees are a type of topological descriptors that record the connectivity among the sublevel sets of scalar fields. In this paper, we are interested in sketching a set of merge trees. That is, given a set T of merge trees, we would like to find a basis set S such that each tree in T can be approximately reconstructed from a linear combination of merge trees in S. A set of high-dimensional vectors can be sketched via matrix sketching techniques such as principal component analysis and column subset selection. However, up until now, topological descriptors such as merge trees have not been known to be sketchable. We develop a framework for sketching a set of merge trees that combines the Gromov-Wasserstein framework of Chowdhury and Needham with techniques from matrix sketching. We demonstrate the applications of our framework in sketching merge trees that arise from data ensembles in scientific simulations.
翻译:合并的树木是一种表层描述器, 记录了星标田子层各组的连接性。 在本文中, 我们有兴趣绘制一组合并的树木。 也就是说, 给一组合并的树, 我们想要找到一个基础设置 S, 这样T 中的每棵树都可以从S 中合并的树木的线性组合中大致地重建。 一组高维矢量可以通过矩阵草图技术, 如主构件分析和子子集选择来绘制。 但是, 至今为止, 像合并的树木这样的表层描述器还无法绘制出来。 我们开发了一个框架, 将乔杜里和尼达姆的格罗莫夫- 沃瑟斯坦框架与矩阵草图绘制的技术结合起来。 我们展示了我们框架在素描合并的树方面的应用情况, 这些树来自科学模拟中的数据组合。