用矩阵分解加速从流信号推断细胞复形，提升效率且保持精度。
Faster Inference of Cell Complexes from Flows via Matrix Factorization
- 基于矩阵分解设计新启发式算法，高效求解流信号的细胞复形扩展问题。
- 计算实验显示，新方法在多数场景下速度更快，性能仅轻微下降。
- 特别在噪声环境下，效果优于现有最优方法，适合高噪声数据处理。
给定图上观测到的边流信号，目标是将该图升维为一个细胞复形，使得观测到的边流信号能表示为该细胞复形上梯度流与旋度流的稀疏组合。具体而言，通过添加一组2-胞腔（由闭合非交叉路径围成的多边形），使关联细胞复形的霍德奇拉普拉斯算子的特征向量能提供对图上边流信号的稀疏、可解释表示。已有研究表明此问题一般为NP难，本文提出一种新的基于矩阵分解的启发式方法。通过计算实验表明，新方法相比先前启发式显著降低计算开销，且在大多数情形下性能仅略有下降；事实上，在特定噪声设置下，新方法在解质量与计算速度上均优于当前最优方法。
原文摘要 · Abstract (English)
We consider the following inference problem: Given a set of edge-flow signals observed on a graph, lift the graph to a cell complex, such that the observed edge-flow signals can be represented as a sparse combination of gradient and curl flows on the cell complex. Specifically, we aim to augment the observed graph by a set of 2-cells (polygons encircled by closed, non-intersecting paths), such that the eigenvectors of the Hodge Laplacian of the associated cell complex provide a sparse, interpretable representation of the observed edge flows on the graph. As it has been shown that the general problem is NP-hard in prior work, we here develop a novel matrix-factorization-based heuristic to solve the problem. Using computational experiments, we demonstrate that our new approach is significantly less computationally expensive than prior heuristics, while achieving only marginally worse performance in most settings. In fact, we find that for specifically noisy settings, our new approach outperforms the previous state of the art in both solution quality and computational speed.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。