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.