Associate Professor (Reader) in Machine Learning
School of Mathematics, The University of Edinburgh
The Maxwell Institute for Mathematical Sciences
Alan Turing Institute | Bayes Centre | Gen AI Lab
School of Mathematics, Gran Sasso Science Institute
email: f dot tudisco at ed.ac.uk
Happy to share that our paper Efficient Sparsification of Simplicial Complexes via Local Densities of States has been accepted for publication in the SIAM Journal on Mathematics of Data Science (SIMODS).
Joint work with Anton Savostianov, Nicola Guglielmi, and Michael Schaub.
Simplicial complexes are a natural generalization of graphs that capture higher-order relations in data, but real-world complexes are often dense and expensive to analyze. In this paper we develop a probabilistic method to sparsify a simplicial complex — approximating it with a much sparser one that keeps a log-linear number of higher-order simplices while preserving a spectrum close to the original. The key ingredient is an efficient computation of sparsifying sampling probabilities through local densities of states, together with a “kernel-ignoring” decomposition that avoids pathological structures in the spectrum of the Hodge Laplacian. We back the method with error estimates on its asymptotic complexity and demonstrate it on Vietoris–Rips filtered complexes.