Graphs arising in statistical problems, signal processing, large networks, combinatorial optimization, and data analysis are often dense, which causes both computational and storage bottlenecks. One way of \textit{sparsifying} a \textit{weighted} graph, while sharing the same vertices as the original graph but reducing the number of edges, is through \textit{spectral sparsification}. We study this problem through the perspective of RandNLA. Specifically, we utilize randomized matrix multiplication to give a clean and simple analysis of how sampling according to edge weights gives a spectral approximation to graph Laplacians. Through the $CR$-MM algorithm, we attain a simple and computationally efficient sparsifier whose resulting Laplacian estimate is unbiased and of minimum variance. Furthermore, we define a new notion of \textit{additive spectral sparsifiers}, which has not been considered in the literature.
翻译:统计问题、信号处理、大规模网络、组合优化和数据分析中出现的图形通常非常密集,这导致计算和存储方面都面临瓶颈。稀疏化加权图形是通过保留原始图形相同的顶点,减少边数来完成的,是图形优化中的一个有效的工具。我们通过考察RandNLA的角度来研究这个问题。具体地,我们利用随机化矩阵乘法的方法,通过对边权值进行采样,给出了如何通过谱稀疏化限制图Laplacians为近似值的干净而简单的分析。通过$CR$ - MM算法,我们得出了一个简单而具有计算效率的稀疏器,其Laplacian估计是无偏且方差最小的。此外,我们定义了一种新的概念,即“附加谱稀疏化”,这在文献中尚未得到考虑。