Abstract:We aim to learn a sparse and connected graph from sparse data, where the number of observations K can be substantially smaller than the signal dimension N for signals x in R^N, and the underlying distribution is unknown. In this severely ill-posed setting, we incorporate Fiedler number (the second eigenvalue of the graph Laplacian matrix that quantifies connectedness) as a robust regularization term in the sparse graph learning objective. We first develop a greedy algorithm that iteratively selects one edge globally for weakening/removal to reduce the objective, leveraging eigenvalue perturbation theorems that bound the adverse effect of an edge change to the Fiedler number. Next, we design a parallel variant, based on the Cheeger's inequality, that recursively partitions an input graph into two sub-graphs using an approximate Cheeger cut to distributedly find an optimal edge. Simulation experiments show that Fiedler number maximization robustifies sparse graph estimates, outperforming previous sparse graph learning algorithms.
| Subjects: | Signal Processing (eess.SP); Machine Learning (cs.LG) |
| Cite as: | arXiv:2604.26132 [eess.SP] |
| (or arXiv:2604.26132v1 [eess.SP] for this version) | |
| https://doi.org/10.48550/arXiv.2604.26132 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Bahar Oveisgharan [view email]
[v1]
Tue, 28 Apr 2026 21:40:39 UTC (78 KB)