اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFinite Impulse Response Filters for Simplicial Complexes
128
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper, we study linear filters to process signals defined on simplicial complexes, i.e., signals defined on nodes, edges, triangles, etc. of a simplicial complex, thereby generalizing filtering operations for graph signals. We propose a finite impulse response filter based on the Hodge Laplacian, and demonstrate how this filter can be designed to amplify or attenuate certain spectral components of simplicial signals. Specifically, we discuss how, unlike in the case of node signals, the Fourier transform in the context of edge signals can be understood in terms of two orthogonal subspaces corresponding to the gradient-flow signals and curl-flow signals arising from the Hodge decomposition. By assigning different filter coefficients to the associated terms of the Hodge Laplacian, we develop a subspace-varying filter which enables more nuanced control over these signal types. Numerical experiments are conducted to show the potential of simplicial filters for sub-component extraction, denoising and model approximation.
قيم البحث
اقرأ أيضاً
This note reveals an explicit relationship between two representative finite impulse response (FIR) filters, i.e. the newly derived and popularized Kalman-Like unbiased FIR filter (UFIR) and the receding horizon Kalman FIR filter (RHKF). It is pointe
d out that the only difference of the two algorithms lies in the noise statistics ignorance and appropriate initial condition construction strategy in UFIR. The revelation can benefit the performance improvement of one by drawing lessons from the other. Some interesting conclusions have also been drawn and discussed from this revelation.
We study the realizability of simplicial complexes with a given pair of integer sequences, representing the node degree distribution and facet size distribution, respectively. While the $s$-uniform variant of the problem is $mathsf{NP}$-complete when
$s geq 3$, we identify two populations of input sequences, most of which can be solved in polynomial time using a recursive algorithm that we contribute. Combining with a sampler for the simplicial configuration model [Young $textit{et al.}$, Phys. Rev. E $textbf{96}$, 032312 (2017)], we facilitate efficient sampling of simplicial ensembles from arbitrary degree and size distributions. We find that, contrary to expectations based on dyadic networks, increasing nodes degrees reduces the number of loops in simplicial complexes. Our work unveils a fundamental constraint on the degree-size sequences and sheds light on further analysis of higher-order phenomena based on local structures.
Focusing on coupling between edges, we generalize the relationship between the normalized graph Laplacian and random walks on graphs by devising an appropriate normalization for the Hodge Laplacian -- the generalization of the graph Laplacian for sim
plicial complexes -- and relate this to a random walk on edges. Importantly, these random walks are intimately connected to the topology of the simplicial complex, just as random walks on graphs are related to the topology of the graph. This serves as a foundational step towards incorporating Laplacian-based analytics for higher-order interactions. We demonstrate how to use these dynamics for data analytics that extract information about the edge-space of a simplicial complex that complements and extends graph-based analysis. Specifically, we use our normalized Hodge Laplacian to derive spectral embeddings for examining trajectory data of ocean drifters near Madagascar and also develop a generalization of personalized PageRank for the edge-space of simplicial complexes to analyze a book co-purchasing dataset.
In the spirit of topological entropy we introduce new complexity functions for general dynamical systems (namely groups and semigroups acting on closed manifolds) but with an emphasis on the dynamics induced on simplicial complexes. For expansive sys
tems remarkable properties are observed. Known examples are revisited and new examples are presented.
We present the `Basic S* algorithm for computing shortest path through a metric simplicial complex. In particular, given a metric graph, $G$, which is constructed as a discrete representation of an underlying configuration space (a larger continuous
space/manifold typically of dimension greater than one), we consider the Rips complex, $mathcal{R}(G)$, associated with it. Such a complex, and hence shortest paths in it, represent the underlying metric space more closely than what the graph does. While discrete graph representations of continuous spaces is convenient for motion planning in configuration spaces of robotic systems, the metric induced in them by the ambient configuration space is significantly different from the metric of the configuration space itself. We remedy this problem using the simplicial complex representation. Our algorithm requires only an abstract graph, $G=(V,E)$, and a cost/length function, $d:Erightarrow mathbb{R}_+$, as inputs, and no global information such as an embedding or a global coordinate chart is required. The complexity of the Basic S* algorithm is comparable to that of Dijkstras search, but, as the results presented in this paper demonstrate, the shortest paths obtained using the proposed algorithm represent/approximate the geodesic paths in the original metric space significantly more closely.
الأسئلة المقترحة
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
