Given a matrix $A$ with distinct eigenvalues, can I find a sparsest eigenvector of it in polynomial time?

It is tempting to say that one can simply compute the eigenvectors and pick the sparsest among them. However, I believe methods for computing eigenvectors do so with additive error. Indeed, since the eigenvectors may have irrational entries, computing them exactly is hopeless. And knowing the eigenvector with any fixed additive error may not give a definitive answer about whether a particular entry is zero or not.

Of course, this gives rise to the question of what, exactly, I mean by finding a sparsest eigenvector. I'm fairly flexible here - but for the sake of definiteness, let us say that if $v$ is some sparsest eigenvector, then I am happy with an $\epsilon$ additive approximation $v^{\epsilon}$ to $v$ which has the further property that if $v_i=0$ then $v_i^{\epsilon}=0$.


Your Answer

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

Browse other questions tagged or ask your own question.