Skip to content
Preprint

Solving a sequence of eigenvalue problems using snapshot and row subsampling

Oct 2026 · 0 citations · 74 references
Mathematics Computer Science

Abstract

A sequence of eigenvalue problems requires solving $A_i\vec{x}_i= \lambda_i\vec{x}_i$ where $i \in \{1, \dots, N\}$, $N \gg 1$ and (usually) $\lambda_i$ is the largest or smallest eigenvalue of $A_i$. Often, the matrices $A_i$ come from a discretization of a smooth map depending on a parameter $p \rightarrow A(p)$, that is $A_i = A(p_i)$, so the matrices $A_i$ change gradually along the sequence. Under this latter assumption, we introduce an efficient algorithm for solving sequences of eigenvalue problems. Our algorithm combines the ideas of reduced order model and row subsampling, as done in [E. Jones and Y. Nakatsukasa, arXiv, 2025] for linear systems. In addition, in our approach, the same set of rows is guaranteed to work well independently of the value of the parameter $p$ or the matrix $A(p)$ as long as the snapshot matrix is unchanged and given that the row subset was chosen well at the beginning. Furthermore, we implement an update strategy of the snapshot matrix. Along these results, we present theoretical analysis of the snapshot matrix for eigenvalue problems, showing an exponential decay of the singular values, and we give bounds on the error on eigenvectors for unseen value of the parameter. This analysis generalizes that in [M. Guido, D. Kressner, and P. Ricci, J. Sci. Comput., 2024] and shows that, regardless of the distribution of the snapshot points, the convergence is always (asymptotically) exponential in the number of snapshot points if the function $A(p)$ admits an analytical extension. We further generalize our algorithm for computing largest or smallest singular values and relative singular vectors and to generalized eigenvalue problems. We conclude with numerical results showing the efficiency of our approach.

View source

Similar papers

Sep 2026

Eigenvalue and Eigenvector Approximation for Random Matrices Using Low-Degree Polynomials

We initiate the study of approximating the top eigenvalue and eigenvector of a random symmetric matrix $ A \in \mathbb{R}^{n\times n} $ using $ q(A)b $ where $q$ is a degree-$d$ polynomial and $b$ is a standard Gaussian vector independent of $A$. For spiked GOE $ Y = \lambda vv^\top + X $, we identify $ d_\star = \frac...

Yi-Han Zhang · 0 citations
Preprint Nov 2026

A Fast and Accurate Algorithm for the $p \to q$ Norm of Sparse Non-Negative Matrices

We present an algorithm that computes the $p \to q$ norm of a non-negative matrix with $s$ nonzero entries to accuracy $\varepsilon$ in time $\widetilde{O}(s^{3/2} \log (1/\varepsilon))$, for any $p \ge q \ge 1$. The fastest algorithm previously designed for this problem has running time $\widetilde{O}(s / \varepsilon)...

M. Pirazzini, D. Spielman · 0 citations
Preprint Sep 2026

Exponent Profiles of Oscillatory Matrices under Matrix and Inverse Sparsity

We classify the simultaneous half-bandwidths $p,q$ of a symmetric oscillatory matrix $A$ and its inverse. At order $n\ge2$, the possible pairs are $(1,n-1)$, $(n-1,1)$, and all pairs with $2\le p,q\le n-1$. Let $e_k(A)$ be the least positive integer $m$ for which all minors of order $k$ of $A^m$ are positive, and let $...

Wei Xie · 0 citations
Preprint Oct 2026

Limiting ESD for a weighted sample covariance matrix

We study the empirical spectral distribution (ESD) of the random matrix $M_N=\frac1N\sum_{i=1}^N f(|\pi Y_i|^2)\,Y_iY_i^\top$, where $\pi$ is a rank $k$ orthogonal projector on $\R^p$, $Y_1,\dots,Y_N$ are i.i.d. standard Gaussian vectors, and $k\to \infty$, $p/N\to \gamma$. We here assume that $f(x)=g(x/k)$ for some fu...

S. Péché · 0 citations
Preprint Nov 2026

Local contraction of stochastic affine recursions of $\mathbb{R}^d$

We consider affine stochastic recursions $X^x_{n+1}=A_{n+1}X^x_n+B_{n+1}$ in $\mathbb{R}^d$, where $(B_n,A_n)$ are i.i.d. in $\operatorname{Aff}(\mathbb{R}^d)$ with strongly irreducible and proximal linear part. In the critical regime where the top Lyapunov exponent vanishes, we show that the recursion is locally contr...

Richard Aoun, Sara Brofferio, M. Peigné · 0 citations
Preprint Sep 2026

Tight bounds for positive discrepancy via eigenvalues

Given an $n\times n$ symmetric matrix $M$ with largest eigenvalue $\lambda_1\geq 0$, it is easy to show that the solution of the optimisation problem $\max_{v\in [-1,1]^n}v^TMv$ is at most $\lambda_1 n$. We prove the following converse: if every $n'\times n'$ principal submatrix of $M$ has maximal eigenvalue at least $...

Oliver Janzer, István Tomon, Fredy Yip · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.