0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.