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.



Dimension independent computational complexity of singular value decomposition
Have a look at the references cited in my [older answer here](https://mathoverflow.net/a/75382/8430), 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)


