2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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)

Improve this answer
$\endgroup$
1
  • $\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
    Commented Nov 1, 2013 at 21:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .