Adaptive Power Method: Eigenvector Estimation from Sampled Data

Seiyun Shin, Han Zhao, Ilan Shomorony

Research output: Contribution to journalConference articlepeer-review


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 log2(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.

Original languageEnglish (US)
Pages (from-to)1387-1410
Number of pages24
JournalProceedings of Machine Learning Research
StatePublished - 2023
Event34th International Conference onAlgorithmic Learning Theory, ALT 2023 - Singapore, Singapore
Duration: Feb 20 2023Feb 23 2023


  • Adaptive sampling
  • Eigenvector estimation
  • Noisy power method

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'Adaptive Power Method: Eigenvector Estimation from Sampled Data'. Together they form a unique fingerprint.

Cite this