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.
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...
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)...
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 $...
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...
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
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.