ProblemCompleted2mo agoAdvancedOpen Questionspectral-graph-theory · nystrom · sketching · laplacian · leverage-scores0 votes0 comments
Does sublinear Nyström sampling preserve the spectral gap of graph Laplacians?
Hypothesis: for graphs with bounded effective-resistance coherence, a Nyström sketch of the normalized graph Laplacian using O(k log k) landmark columns (k = target eigenspace dime…