Feb, 2015

随机行走矩阵多项式的谱稀疏化

PDF
TL;DR本论文解决了计算矩阵多项式的谱稀疏矩阵的基本算法问题，在最近线性时间内构造了一个带有少量非零元的拉普拉斯矩阵，近似于给定的矩阵多项式；该算法可用于多步时间可逆马尔可夫模型的有效电阻的构建，以及网络分析中的其他任务。
spectral graph theoryspectral sparsifiermatrix polynomialslaplacian matrixrandom-walk
发现论文，激发创造
  • 图的频谱稀疏化

    本文提出了一种基于图拉普拉斯矩阵谱相似性的新型图稀疏化方法，证明了任何图都有近乎线性大小的谱稀疏化，并给出了一个可在几乎线性时间内构建谱稀疏化的算法，该方法的关键组成部分之一是对具有强保证的近乎线性时间图划分算法的使用。

    Aug, 2008

  • 动态流中的单遍谱稀疏化

    我们提出了一种动态半流模型下用于计算图形谱稀疏化的首个单趟算法，该算法使用线性素描将 G 的入射矩阵维护为 O ((1/epsilon^2) n*.polylog (n)) 维，可以输出高概率下 G 的 (1+/-epsilon) 谱稀疏化。该方法利用了 G 的粗略稀疏器和 G 的入射矩阵的线性素描，通过等效电阻抽样边缘以得到任意精度的谱稀疏化。

    Jul, 2014

  • Twice-Ramanujan Sparsifiers

    这篇论文证明了每个图形都有一个谱稀疏器，其边数与其顶点数成线性关系。特别地，通过 Laplacian matrices 构造的谱稀疏器提供了对图形的光谱映射，令其成为扩展图的推广。此外，该论文提供了一个简单的确定性多项式时间算法来构造这种稀疏器。

    Aug, 2008

  • 基于 SDP 的线性大小谱稀疏化算法

    本篇研究将提出一种计算效率更高的算法来构建图的 $(1 + ϵ)$- 频谱稀疏子图，该算法基于三种新技术，并使用新的潜力函数，通过半定规划求解构造单侧频谱稀疏子图。

    Feb, 2017

  • 构建线性规模的谱稀疏化算法

    本研究提出了第一个近乎线性时间的算法，用于构建具有线性大小的图谱稀疏化。该算法采用文献中用于构建光谱稀疏化的两种技术的新组合：基于有效电阻的随机采样和基于障碍函数的自适应构造。

    Aug, 2015

  • 随机元素级矩阵稀疏化注释

    本文提出一种基于随机采样的算法用于对矩阵进行稀疏处理，同时利用分布与矩阵元素平方和绝对值相关的信息提高了近似精度。

    Apr, 2014

  • 马尔科夫链的近线性时间算法和有向图的新谱基元

    本文提出了一种面向有向图的射影逼近概念，并利用该方法构建了一个广泛启发自 Peng-Spielman 的对称线性系统求解框架，通过结合近乎线性时间的稀疏化算法，得到求解定向 Laplacian 线性系统的近乎线性时间算法，本算法的时间复杂度优于现有最优解。

    Nov, 2016

  • 核范数中的快速谱密度估计与稀疏化

    利用一种随机算法和核稀疏化的方法，该研究提出了一种新的图谱估计方法，可在线性时间和多项式查询复杂度下，准确估计归一化邻接矩阵的谱密度。这一方法在复杂度和准确性方面均具有优势，且创造性地解决了图的稀疏化和添加谱稀疏化的相关问题。

    Jun, 2024

  • GRASS：基于可扩展的谱扰动分析的图谱稀疏化算法

    本文提出了一种相似性感知的谱图稀疏化框架，利用有效的谱偏树边嵌入和过滤方案构建谱稀疏化，实现了保证谱相似度（相对条件数）水平的过滤，同时介绍了迭代图密度增加方案以促进高度病态问题的有效过滤。该方法已验证了各种公共领域稀疏矩阵收集到的图表，包括与 VLSI CAD、有限元分析、社会和数据网络频繁研究的许多机器学习和数据挖掘应用相关的图表。

    Nov, 2019

  • 通过随机张量谱范数的界限进行张量稀疏化

    该研究提出了一种元素稀疏化算法，基于张量的幂次进行，以及使用了一个用于较好的随机张量估计的不等式，旨在解决张量稀疏化问题并获得新的精度界限以改善算法性能。

    May, 2010