论文标题
使用应用于快速图形傅立叶变换的快速近似本特征空间
Constructing fast approximate eigenspaces with application to the fast graph Fourier transforms
论文作者
论文摘要
我们研究了与对称和一般矩阵相关的特征空间的数值有效近似。本特征空间分为可以有效操纵的固定数量的基本组件（我们考虑扩展的正交式或缩放和剪切转换）。这些组件的数量控制了近似准确性与在特征空间投影的计算复杂性之间的权衡。我们为单个基本组件编写最小化问题，并提供封闭形式的解决方案。然后，我们提出算法迭代更新所有这些组件直至收敛。我们显示了随机矩阵的结果以及针对有向和无向图的图形傅立叶变换的近似值的应用。
We investigate numerically efficient approximations of eigenspaces associated to symmetric and general matrices. The eigenspaces are factored into a fixed number of fundamental components that can be efficiently manipulated (we consider extended orthogonal Givens or scaling and shear transformations). The number of these components controls the trade-off between approximation accuracy and the computational complexity of projecting on the eigenspaces. We write minimization problems for the single fundamental components and provide closed-form solutions. Then we propose algorithms that iterative update all these components until convergence. We show results on random matrices and an application on the approximation of graph Fourier transforms for directed and undirected graphs.
