# Dimension independent computational complexity of singular value decomposition

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.

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)

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