UBC Theses and Dissertations
Variations on sparsifier constructions Xiao, Ke Han
We studied Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava's Twice-Ramanujan Sparsifiers. On this basis, we try to generalize their potential function. Inspired by the idea of non-backtracking matrices, we designed the new potential formula that puts all eigenvalues on the complex plane. Following the construction of the twice Ramanujan sparsifier, we conclude some obstacles must be encountered to improve their bound.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International