Name
Abstract | ||
|---|---|---|
We propose a method for rank $k$ approximation to a given input matrix $X mathbb{R}^{d times n}$ which runs in time [ tilde{O} left(d ~cdot~ minleft{n + tilde{sr}(X) ,G^{-2}_{k,p+1} , n^{3/4}, tilde{sr}(X)^{1/4} ,G^{-1/2}_{k,p+1} right} ~cdot~ text{poly}(p)right) ~, ] where $pu003ek$, $tilde{sr}(X)$ is related to stable rank of $X$, and $G_{k,p+1} = frac{sigma_k-sigma_p}{sigma_k}$ is the multiplicative gap between the $k$-th and the $(p+1)$-th singular values of $X$. In particular, this yields a linear time algorithm if the gap is at least $1/sqrt{n}$ and $k,p,tilde{sr}(X)$ are constants. |
Year | Venue | Field |
|---|---|---|
2016 | arXiv: Information Theory | Discrete mathematics,Combinatorics,Singular value,Multiplicative function,Matrix (mathematics),Low-rank approximation,Sigma,Mathematics |
DocType | Volume | Citations |
Journal | abs/1607.02925 | 0 |
PageRank | References | Authors |
0.34 | 13 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alon Gonen | 1 | 104 | 9.76 |
| Shai Shalev-Shwartz | 2 | 3681 | 276.32 |