# Rayleigh quotient over sparse vectors

Let $A$ be an $n\times n$ Hermitian positive definite matrix. The well-known Rayleigh quotient \begin{equation} R(A,z) := \frac{z^*Az}{z^*z},\ (z \neq 0) \in \mathbb{C}^n \end{equation} is bounded above and below by the maximum and minumum eigenvalues $\lambda_\mathrm{max}(A)$ and $\lambda_\mathrm{min}(A)$, respectively. Now, however, consider a restriction on $z$ such that they are at most $k$-sparse (in the same basis as $A$), $k<n$. For the purposes of notation, we denote this by the set \begin{equation} \mathcal{S} := \{z \in \mathbb{C}^n : \, 0 < |\mathrm{supp}(z)| \leq k\} \end{equation} In general these vectors will not be eigenvectors of $A$, and so in the interest of non-trivial results, we will explicitly impose that condition. Thus we should expect \begin{align} \max_{z\in\mathcal{S}} R(A,z) &< \lambda_\mathrm{max}(A),\\ \min_{z\in\mathcal{S}} R(A,z) &> \lambda_\mathrm{min}(A). \end{align}

My question is: are there any useful estimates (in the sense that they depend on the sparsity $k$) on the above expressions, assuming we know the spectrum of $A$?

I imagine that there must be a few published results out there about this problem, but I have only found works regarding sparse matrices, rather than vectors. (For what it's worth, I can show a simplistic upper bound, but am rather lost when it comes to the minimum.)

## 1 Answer

Diagonalizing and writing $A=\sum_i \lambda_i e_i e_i^T$ you have (supposing $z$ of norm 1): $$R(A,z)=\sum_i \lambda_i (e_i^T z)^2$$ so it depends on how well your sparse vector may be aligned with the smallest (or largest) eigenvector. I suppose that you intend to use it on a sparse matrix $A$ but as eigenvectors need not be (even close to) sparse I don't quite see a situation where the approach will be very useful (but just my opinion).