AI & ML
Finding accurate eigenvalues and eigenvectors of positive semi-definite matrices given a subspace
arXiv cs.NA0 views
arXiv:2605.05043v2 Announce Type: replace Abstract: We revisit a classical problem in numerical linear algebra: given a $k$-dimensional subspace $\mathcal{Q}$ with orthonormal basis $Q$ that approximates the leading eigenspace of an $n\times n$ positive semi-definite matrix $A$, the goal is to extract high-accuracy eigenvalues. The Rayleigh-Ritz (RR) method is the standard algorithm for the task, which has been shown to be optimal in several ways (when $A$ is symmetric, not necessarily positive semi-definite $A\succeq 0$). In this paper, we show that when $A\succeq 0$, alternative methods can outperform RR, including Nystr{\"o}m and one-sided projected SVD, while having the same computational complexity; that is, the main cost is in computing $AQ$, plus an $O(nk^2)$ term. In particular, we advocate the use of Nystr{\"o}m's method, quantitatively showing that the approximate leading eigenvalues have better accuracy than RR, and the improvement can be arbitrarily large. The significant accuracy improvement occurs for the first $i$ eigenvalues if $\lambda_i \gg \lambda_{k+1}$ and uniformly for all $k$ eigenvalues if $\lambda_k \gg \lambda_{k+1}$. This theoretical observation can be extended to the case where we extract $k$ leading eigenvalues from a larger-dimensional subspace. A similar improvement is numerically observed for the purpose of approximating the leading eigenvectors. In contrast, when the target eigenvalues are the trailing ones, the situation is reversed, and the Nystr{\"o}m method performs poorly; we suggest a remedy based on a shift for this situation.
Source:https://arxiv.org/abs/2605.05043PreviousExplicit Planar Finite Element Elasticity Complexes and $C^1$ Elements on Barycentric RefinementsNextA constrained Onsager variational framework for parametric approximations of Willmore and Helfrich flows
Related posts
Your Manager's Manager Has Booked a Skip Level Meeting With You
0dev.to

How to Make a Character Reference Sheet with AI (Prompts Included)
0dev.to Design
How Virtual Assistants Help Businesses Manage Their Work More Efficiently
0dev.to Productivity
DiffusionSSD: Achieving Extreme Visual Compression with Dual-stage Diffusion and Cross-level Near-Data Processing
0arXiv eess.IV
D2ToF: One-Step Diffusion for Depth Super-Resolution from Lightweight Single-Photon LiDAR Waveforms
0arXiv eess.IV
Few-Shot Open-Set Hyperspectral Pixel-Wise Classification with Spatial Aware Label Propagation
0arXiv eess.IV