Content deleted Content added
m Open access bot: url-access updated in citation with #oabot. |
|||
Line 20:
The CUR matrix approximation is not unique and there are multiple algorithms for computing one. One is ALGORITHMCUR.<ref name=mahoney />
The "Linear Time CUR" algorithm <ref>{{Cite journal |last1=Drineas |first1=Petros |last2=Kannan |first2=Ravi |last3=Mahoney |first3=Michael W. |date=2006-01-01 |title=Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication |url=https://epubs.siam.org/doi/abs/10.1137/S0097539704442684 |journal=SIAM Journal on Computing |volume=36 |issue=1 |pages=132–157 |doi=10.1137/S0097539704442684 |issn=0097-5397|url-access=subscription }}</ref> simply picks ''J'' by sampling columns randomly (with replacement) with probability proportional to the squared column norms, <math>\|L_{:,j}\|_2^2</math>; and similarly sampling ''I'' proportional to the squared row norms, <math>\|L_{i}\|_2^2</math>.
The authors show that
taking <math>|J| \approx k /\varepsilon^4</math> and <math>|I| \approx k / \varepsilon^2</math> where <math>0 \le \varepsilon</math>, the algorithm achieves Frobenius error bound <math>\|A - CUR\|_F \le \|A - A_k\|_F + \varepsilon \|A\|_F</math>, where <math>A_k</math> is the optimal rank ''k'' approximation.
| |||