Topological Signal Processing over Simplicial Complexes

I. INTRODUCTION

• Graph models capture pairwise relations but can miss multiway interactions; simplicial complexes impose face closure while providing algebraic structure for signal analysis.The paper focuses on simplicial complexes as a useful, though more restrictive, alternative to general hypergraphs.Source: §I · p. 1
• Topological signal processing (TSP) analyzes signals on vertices, edges, triangles, and higher-order simplices, whereas graph signal processing (GSP) focuses on graph vertices.The paper’s focus on signals over complexes complements topological data analysis, which emphasizes properties of complexes extracted from data.Source: §I · p. 1
• The paper contributes methods for triple-wise edge relations, sampling high-order signals, inferring complex structure, and analyzing edge signals and vector fields.It extends preliminary work with sampling theory across orders, noise-robust inference methods, and applications to wireless traffic and RNA velocity estimation.Source: §I · p. 2

II. REVIEW OF ALGEBRAIC TOPOLOGY TOOLS

• The algebraic-topology review introduces the principles needed for later signal-processing tools through an algebraic approach accessible to readers without a specific topology background.It also recalls discrete calculus.Source: §II · p. 2

A. Discrete domains: Simplicial complexes

• A simplicial complex is a face-closed collection of simplices; a graph is its order-one case, and the framework does not require embedding in real space.A k-simplex has k + 1 vertices, and its faces are the simplices formed by deleting one vertex.Source: A. Discrete domains: Simplicial… · p. 2
• Oriented simplices generate chain vector spaces, and the boundary operator maps each k-chain to a (k−1)-chain with the boundary of a boundary equal to zero.An oriented edge specifies the positive or negative direction of flow; it does not restrict flow to one direction.Source: A. Discrete domains: Simplicial… · p. 3

B. Algebraic representation

• Incidence matrices represent boundary operators and describe complex structure; an order-two complex uses vertex-edge and edge-triangle incidence matrices.Source: B. Algebraic representation · p. 3
• Intermediate-order combinatorial Laplacians combine lower and upper adjacency, while the graph vertex Laplacian contains only an upper-adjacency term.Edges are lower adjacent when they share a vertex and upper adjacent when they are faces of a common triangle.Source: B. Algebraic representation · p. 3

III. SPECTRAL SIMPLICIAL THEORY

• Signals on a simplicial complex are real-valued maps on simplices; the paper focuses on vertices, edges, and triangles for orders zero through two.The corresponding signal maps are s0 on vertices, s1 on edges, and s2 on triangles.Source: §III · p. 3
• Vertex signals smooth within graph clusters have sparse or approximately sparse representations in the basis of L0 eigenvectors.The graph Fourier transform is defined by projection onto that eigenvector basis.Source: §III · pp. 3–4
• The section generalizes graph Fourier representations by projecting each k-order signal onto eigenvectors of its corresponding high-order Laplacian.The section also sets out to recall Hodge decomposition and develop a topology-aware unitary basis from topological properties.Source: §III · p. 4

A. Relations between eigenvectors of different order

• Nonzero-eigenvalue eigenvectors of Bk^T Bk and Bk+1 Bk+1^T are orthogonal, and applying Bk^T maps an eigenvector of Bk Bk^T to one with the same eigenvalue.The proposition also gives the converse orthogonality relation between the two component matrices.Source: A. Relations between eigenvectors of… · p. 4
• For k-order Laplacians, nonzero eigenvectors and eigenvalues come from either Bk^T Bk or Bk+1 Bk+1^T.The proposition states that the eigenvectors and eigenvalues associated with nonzero Laplacian eigenvalues belong to one of these two component matrices.Source: A. Relations between eigenvectors of… · p. 4
• The smallest-eigenvalue eigenvectors of B1^T B1 are approximately null on within-cluster links and largest in modulus across clusters, highlighting inter-cluster edges.This follows by applying the eigenvector relation to k = 1 and the smoothness of the corresponding low-eigenvalue eigenvectors of L0.Source: A. Relations between eigenvectors of… · p. 4

B. Hodge decomposition

• For any signal order k, Hodge decomposition expresses the signal as three orthogonal components arising from adjacent-order signals and a harmonic component.The harmonic subspace is ker(Lk), and the decomposition reflects interplay between signals of different orders.Source: B. Hodge decomposition · p. 4
• The dimensions of the harmonic subspaces are Betti numbers and topological invariants: β0 counts connected components, β1 holes, and β2 cavities.Source: B. Hodge decomposition · p. 5
• For edge flows, curl maps edge signals to triangles and measures circulation, while divergence maps them to vertices and measures net flow, revealing sources or sinks.Source: B. Hodge decomposition · p. 5
• In the edge-flow decomposition, the gradient-derived component is curl-free, the triangle-derived component is divergence-free, and the harmonic component is both.Source: B. Hodge decomposition · p. 5

C. Topology-aware unitary basis

• The Lovász extension of a triple-wise coupling function measures the sum of absolute triangle curls, providing a topology-aware objective for constructing an edge-signal basis.The construction starts from a partition of the vertices into three sets and extends the coupling function to the edge space.Source: C. Topology-aware unitary basis · p. 6
• The unitary-basis objective is convex but non-convex under the unitarity constraint; retaining its ℓ1 form can yield sparser, more informative representations when computational complexity permits.Source: C. Topology-aware unitary basis · p. 6
• Relaxing the curl-based basis objective yields eigenvectors of B2 B2^T; a general edge-signal basis uses all eigenvectors of L1, including those in its kernel.The nonzero-eigenvalue components of L1 include the eigenvectors associated with B2 B2^T and B1^T B1.Source: C. Topology-aware unitary basis · p. 6

IV. EDGE FLOWS ESTIMATION

• The denoising problem uses vectors and Hodge decomposition to estimate noisy edge flows; it assumes zero-mean Gaussian noise with equal variance across entries.The section contrasts its vector formulation with an earlier approach that represented edge and triangle signals as skew-symmetric arrays [18].Source: §IV · p. 7
• Problem Q is convex, and multipliers λ1 ∈ RV and λ2 ∈ RT exist such that the associated tuple satisfies Q’s KKT conditions; s2 and λ2 differ only by a vector in the nullspace of BT.Slater’s constraint qualification is satisfied.Source: §IV · p. 7
• For connected graphs, L0 has rank V−1 and an all-ones nullspace, so irrotational-flow recovery uses the Moore-Penrose pseudoinverse.The edge-derived vector b admits a nontrivial solution for connected graphs.Source: §IV · p. 7
• The harmonic component is recovered by subtracting the estimated solenoidal and irrotational components from the observed flow, and the optimization’s s0 and s2 variables decouple.The decoupling means their optimal solutions coincide with those of separate problems.Source: §IV · p. 7
• Projecting observed network traffic onto the space orthogonal to nonzero-eigenvalue eigenvectors of B2B2^T highlights edges around the two anomalous source nodes in Fig. 2(b).The projection is proposed to detect nodes generating strong irrotational, or divergence-like, traffic.Source: §IV · pp. 7–8, Figure 2 · p. 8

Sampling and recovering of signal defined over simplicial complex

• For order K = 2, the section defines edge sampling with a diagonal limiter D_S that retains measured edges and zeros the rest.The focus is on signals defined over vertices, edges, and triangles.Source: §V · p. 8
• An edge signal is S-edge-limited when s_1=D_Ss_1 and F-bandlimited when F_Fs_1=s_1; D_S and F_F are orthogonal projectors.D_S projects onto the measured edge set S, while F_F projects onto the frequency set F.Source: §V · p. 8
• Perfect joint edge-frequency localization occurs iff F_F D_S F_F has eigenvalue 1; |S|+|F|>E is sufficient, while smaller sums may still work under condition (46).The condition for the smaller-sum case is given by equation (46).Source: §V · p. 8
• The section proceeds from single-layer edge sampling to multi-layer processing using samples of signals from different simplex layers.The single-layer case extracts samples from edge signals.Source: §V · p. 8

A. Single-layer sampling

• Theorem 2 makes edge-signal recovery from samples on S possible if and only if no F-bandlimited signal is perfectly localized on the complementary set.The condition is equivalent to the stated sampling criterion; the proof extends Theorem 4.1 in to edge signals.Source: A. Single-layer sampling · p. 8
• Full column rank of DSFF is required, so |S| ≥ |F| is necessary; when the recovery condition holds, an inverse-based reconstruction is available.The reconstruction uses QS = (I −¯DSFF)^−1, whose existence follows from the condition.Source: A. Single-layer sampling · p. 8
• If an edge signal is known to contain only one Hodge component, that component can be recovered across all edges under Theorem 2’s conditions.The components are solenoidal, irrotational, and harmonic.Source: A. Single-layer sampling · p. 9

B. Multi-layer sampling

• Multi-layer sampling proposes two alternatives for recovering an edge signal: combine vertex and edge samples, or use samples from vertices, edges, and triangles.The second strategy considers signals of orders 0, 1, and 2.Source: B. Multi-layer sampling · p. 9
• With bandlimited vertex and edge signals and the stated norm conditions, s1 is perfectly recoverable using N0 ≥ |F0| vertex samples and N1 ≥ |FsH| edge samples.The frequency set includes FsH and an irrotational set Firr with |Firr| = |F0| − c1.Source: B. Multi-layer sampling · p. 9
• With bandlimited vertex, edge, and triangle signals and the stated norm conditions, s1 is perfectly recoverable using N0 ≥ |F0| vertex, N1 ≥ |FH| edge, and N2 ≥ |F2| triangle samples.The frequency sets satisfy |Firr| = |F0| − c1 and |Fsol| = |F2| − c2, alongside FH.Source: B. Multi-layer sampling · p. 9

Method

• The method maps a vector field to an edge signal, filters that signal, then maps it back, with its main difference from prior approaches in the filtering step.The filtering incorporates metrics dictated by the initial vector-field-to-edge-signal mapping.Source: §VI · p. 10
• The construction assumes a flat, well-centered simplicial complex, uses a well-centered Delaunay triangulation, and interpolates vertex vectors with Whitney basis functions before projecting onto edges.The Whitney functions are affine piecewise hat functions, equal to one at their vertex and zero at other vertices.Source: §VI · p. 10
• Filtering seeks an edge flow close to the observed signal while promoting smoothness and sparsity through a regularized optimization problem.Positive coefficients control smoothness and sparsity; the Hodge Laplacian uses Whitney-induced metric matrices.Source: §VI · p. 10

Applications

• The proposed filter robustly reconstructs a mouse chromaffin-cell RNA velocity field after strong Gaussian noise at SNR = 0 dB is added.The reconstructed field is shown in Fig. 3(c), compared with the observed and noisy fields in Fig. 3(a–b).Source: §VI · p. 10, Figure 3 · p. 11

Topology inference framework

• Starting from a known or estimated graph topology, the hierarchical method infers triangle fillings from edge flows only when projected non-irrotational energy exceeds threshold η.The approach checks whether the B2B2^T term is needed after removing the irrotational component.Source: §VII · p. 11

Minimum Total Variation (MTV) Algorithm

• MTV selects a specified number of triangle fillings by minimizing total variation, choosing cliques with the smallest observed-flow curl; the target count is selected by cross-validation.The method is expected to work best when edge signals contain only harmonic components, whose curl on filled triangles is zero.Source: §VII · pp. 11–12

PCA-based Best Fitting with Minimum Total Variation (PCA-BFMTV)

• PCA-BFMTV uses leading covariance eigenvectors to denoise edge-flow data, then alternates between fitting the data and selecting triangle fillings to trade off fitting error and total variation.It is proposed to make MTV more robust when signals include solenoidal components or noise; each alternating step has a closed-form solution.Source: §VII · pp. 12–13

Performance on synthetic data

• For harmonic edge flows, recovery is error-free without noise; with noise, PCA-BFMTV significantly improves on MTV, and it also outperforms MTV for mixed harmonic-solenoidal flows, especially at low SNR.Both methods degrade when the solenoidal bandwidth is large; degradation is negligible when it is small. Figure 4 reports triangle error probability versus SNR.Source: §VII · pp. 12–13, Figure 4 · p. 13

Performance on real data

• On Milan call flows, the inferred order-2 basis gives lower MSE at fixed sparsity (or greater sparsity at fixed MSE) and lower reconstruction error at equal sample counts than graph-only bases.The inferred basis captures structure through the estimated triangle-boundary term B2B2^T.Source: §VII · pp. 13–14, Figure 5 · p. 14, Figure 6 · p. 14

VIII. CONCLUSION

• The algebraic framework exploits the full structure of an order-two complex for edge signals, while its tools can translate to higher-order signals despite lacking a visual interpretation of their Laplacian eigenvectors.The paper does not analyze higher-order signals; solenoidal or irrotational interpretations do not apply there.Source: §VIII · p. 14
• On real wireless traffic data, the proposed flow-based method for inferring a second-order simplicial complex significantly outperforms methods based only on graph representations.The conclusion does not report quantitative values for this comparison.Source: §VIII · p. 14
• For RNA velocity field recovery, eigenvectors of L1 highlight irrotational and solenoidal behaviors that would be difficult to highlight using only eigenvectors of L0.The application uses the recovered field to predict the evolution of living cells.Source: §VIII · p. 14
• Future developments should address statistical modeling of random variables on simplicial complexes and generalize the methods to higher-order structures.Source: §VIII · p. 14

• A set function is submodular exactly when its Lovász extension is convex, and minimizing the extension on [0, 1]^A is equivalent to minimizing the set function on 2^A.Source: Appendix A · p. 14
• The edge-triangle incidence matrix applied to the oriented-edge indicator is nonzero exactly for triangles spanning all three partition sets.In the example, B2 1ET = [0, 1, 0]^T, so the triangle-cut size is 1.Source: Appendix A · p. 15
• For a node tri-partition, G on oriented edges equals F1, the number of triangles with one vertex in each partition set.The edge set ET encodes the partition through oriented edges whose vertices lie in differently ordered sets.Source: Appendix A · pp. 14–15
• For each triangle term, the Lovász extension is x_i0 − x_i1 + x_i2 regardless of the ordering of its three edge variables.The proof checks the orderings and then uses additivity to extend the expression to the full edge signal.Source: Appendix A · p. 15
• The proof concludes that f1 is the Lovász extension of the triangle-cut function F1, completing Theorem 1.It derives this by identifying F1 with the edge-set function G.Source: Appendix A · p. 15

APPENDIX B SUPPORTING MATERIAL

• Section A presents Proposition 2 and its proof as tools for proving Theorems 3 and 4 in Sections B and C.Source: Appendix B · p. 17

A. Proposition 2

• Proposition 2 addresses the relationship between the bandwidth of an edge signal’s irrotational part and that of a vertex signal.Source: A. Proposition 2 · p. 17
• For an F0-bandlimited vertex signal, its irrotational edge-signal part is Firr-bandlimited, with |Firr| = |F0| − c1.Source: A. Proposition 2 · p. 17
• The correction c1 counts the eigenvectors in the vertex signal’s bandwidth that belong to ker(L0).Source: A. Proposition 2 · p. 17
• The proof relates vertex-Laplacian eigenvectors to edge-Laplacian eigenvectors through B1^T, preserving their eigenvalue.Source: A. Proposition 2 · p. 17
• Using the vertex signal’s bandlimited expansion and multiplying the eigenvector relation by B1, the proof establishes the stated edge-signal bandlimitedness.Source: A. Proposition 2 · p. 17

B. Proof of Theorem 3

• The proof of Theorem 3 begins from the sampled edge signals s1.Source: B. Proof of Theorem 3 · p. 17

" DAF0

• When both stated norm conditions are below 1, G is invertible, enabling recovery of s0 and the complementary edge signal via the partitioned-matrix inverse [68].Source: " DAF0 · p. 17
• The edge signal s1 is F-bandlimited with F = FsH ∪ Firr and bandwidth |F| = |FsH| + |F0| − c1.Source: " DAF0 · p. 17
• At least |FsH| samples are needed to recover the solenoidal and harmonic parts of s1, and at least |F0| to recover the vertex signal s0.Source: " DAF0 · p. 17

C. Proof of Theorem 4

• Theorem 4’s proof begins from the sampled vertex signals s0.Source: C. Proof of Theorem 4 · p. 18

H + DSBT

• The proof fragment records F0, FH, DSF, and DSB2F2 in its derivation.Source: H + DSBT · p. 18

O O DMF2

• Under the stated norm condition, the matrix Ḡ is invertible, allowing the proof to apply the inverse of partitioned matrices [68].Source: O O DMF2 · p. 18
• The proof derives s1_sol = B2s2 from a bandlimited s2 and uses eigenvectors of the second-order Laplacian L2 = B2ᵀB2.Source: O O DMF2 · p. 18

• The edge signal is F-bandlimited, with F = Fsol ∪ FH ∪ Firr and bandwidth |F| = |F0| + |FH| + |F2| − (c1 + c2).Source: §2 · p. 18
• Perfect recovery requires N1 ≥ |FH| edge samples for the harmonic part, N0 ≥ |F0| node samples for s0, and N2 ≥ |F2| triangle samples for s1_sol.Source: §2 · p. 18