Adaptive Power Method: Eigenvector Estimation from Sampled Data
Adaptive Power Method: Eigenvector Estimation from Sampled Data
复制标题
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Seiyun Shin;Hanfang Zhao;Ilan Shomorony
中科院分区：
文献类型：
--
作者：
Seiyun Shin;Hanfang Zhao;Ilan Shomorony
计算矩阵A的主特征向量有许多应用，例如主成分分析，谱嵌入和PageRank。然而，一般来说，该任务依赖于矩阵A的完整知识，其可能太大而无法存储或甚至在许多应用中无法观察，例如，大型社交网络。因此，一个自然的问题是如何准确地估计A的特征向量时，只有部分的意见，可以从A的抽样条目。为此，我们提出了自适应功率方法（APM），著名的功率方法的变体。在每次幂迭代时，APM基于顶部特征向量的当前估计自适应地选择A的条目的子集来观察。我们证明了APM可以通过观察一个n × n矩阵的大约O（n <$− 2 log 2（n/n））个元素来估计A的主特征向量，平方误差最多为λ。我们提出的实证结果的问题的特征向量中心计算两个现实世界的图，并表明APM显着优于非自适应估计算法使用相同数量的观察。此外，在特征向量中心性的上下文中，APM还可以自适应地分配观察预算，以选择性地细化图中具有高中心性得分的节点的估计。
Computing the dominant eigenvectors of a matrix A has many applications, such as principal component analysis, spectral embedding, and PageRank. However, in general, this task relies on the complete knowledge of the matrix A , which can be too large to store or even infeasible to observe in many applications, e.g., large-scale social networks. Thus, a natural question is how to accurately estimate the eigenvectors of A when only partial observations can be made by sampling entries from A . To this end, we propose the Adaptive Power Method (APM), a variant of the well-known power method. At each power iteration, APM adaptively selects a subset of the entries of A to observe based on the current estimate of the top eigenvector. We show that APM can estimate the dominant eigenvector(s) of A with squared error at most ϵ by observing roughly O ( nϵ − 2 log 2 ( n/ϵ )) entries of an n × n matrix. We present empirical results for the problem of eigenvector centrality computation on two real-world graphs and show that APM significantly outperforms a non-adaptive estimation algorithm using the same number of observations. Furthermore, in the context of eigenvector centrality, APM can also adaptively allocate the observation budget to selectively refine the estimate of nodes with high centrality scores in the graph.