Suppose $X$ is a $m \times n$ real matrix, which has only $k$ number of nonzero elements ($k \ll mn$). Given a vector $y$, the sparsity of $X$ allows $X y$ to be computed in $O(k)$ time which is independent of $m$ or $n$.

Question: how much computation is needed to find an $\epsilon$ accurate estimate of the largest singular value of $X$ (not all singular values)? Since most algorithms rely only on matrix-vector multiplication, it is reasonable to conjecture that the computational cost should also be independent of $m$ or $n$. However, I can't find any established rate of convergence that only depends on $k$ and $\frac{1}{\epsilon}$.

Does anybody have any idea? Any similar result on eigenvalue decomposition for real symmetric matrix can also be helpful.

Thanks in advance.


Have a look at the references cited in my older answer here, for the results of the kind you are looking for (complexity in there though is shown with a worst case O($\log n$) dependence on the dimension, but perhaps the analysis can be adapted to remove that dependence in your case)

| cite | improve this answer | |
  • $\begingroup$ I think the complexity will turn out to be something like $O(k\log n \cdot 1/\epsilon)$ but haven't checked yet. $\endgroup$ – Suvrit Nov 1 '13 at 21:00

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.