> Detailanzeige

Bhattacharjee, Rajarshi [VerfasserIn]; Dexter, Gregory [VerfasserIn]; Drineas, Petros [VerfasserIn]; Musco, Cameron [VerfasserIn]; Ray, Archan [VerfasserIn] ; Rajarshi Bhattacharjee and Gregory Dexter and Petros Drineas and Cameron Musco and Archan Ray [MitwirkendeR]

Sublinear Time Eigenvalue Approximation via Random Sampling

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: Sonstige Veröffentlichung; Elektronischer Konferenzbericht; E-Artikel
  • Titel: Sublinear Time Eigenvalue Approximation via Random Sampling
  • Beteiligte: Bhattacharjee, Rajarshi [VerfasserIn]; Dexter, Gregory [VerfasserIn]; Drineas, Petros [VerfasserIn]; Musco, Cameron [VerfasserIn]; Ray, Archan [VerfasserIn]
  • Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023
  • Sprache: Englisch
  • DOI: https://doi.org/10.4230/LIPIcs.ICALP.2023.21
  • Schlagwörter: randomized linear algebra ; sublinear algorithms ; eigenvalue approximation
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: We study the problem of approximating the eigenspectrum of a symmetric matrix A ∈ ℝ^{n×n} with bounded entries (i.e., ‖A‖_∞ ≤ 1). We present a simple sublinear time algorithm that approximates all eigenvalues of A up to additive error ±εn using those of a randomly sampled Õ((log³ n)/ε³)×Õ((log³ n)/ε³) principal submatrix. Our result can be viewed as a concentration bound on the complete eigenspectrum of a random submatrix, significantly extending known bounds on just the singular values (the magnitudes of the eigenvalues). We give improved error bounds of ± ε √{nnz(A)} and ±ε‖A‖_F when the rows of A can be sampled with probabilities proportional to their sparsities or their squared 𝓁₂ norms respectively. Here nnz(A) is the number of non-zero entries in A and ‖A‖_F is its Frobenius norm. Even for the strictly easier problems of approximating the singular values or testing the existence of large negative eigenvalues (Bakshi, Chepurko, and Jayaram, FOCS '20), our results are the first that take advantage of non-uniform sampling to give improved error bounds. From a technical perspective, our results require several new eigenvalue concentration and perturbation bounds for matrices with bounded entries. Our non-uniform sampling bounds require a new algorithmic approach, which judiciously zeroes out entries of a randomly sampled submatrix to reduce variance, before computing the eigenvalues of that submatrix as estimates for those of A. We complement our theoretical results with numerical simulations, which demonstrate the effectiveness of our algorithms in practice.
  • Zugangsstatus: Freier Zugang