2
$\begingroup$

I'm reading [1] where some columns and rows of a matrix $A$ are selected by their leverage scores aiming to have CUR decomposition of $A$. In the paper $c$ is a value determining how many indices we will select which is found as follows:

$$c = O(k \log k / \epsilon^2)$$

where $k$ stands for the number of right singular vectors selected and $\epsilon$ is an error value.

What I don't understand is that how can we assign a variable according to some big-O order of a value in the implementation of the algorithm. I can multiply $k \log k / \epsilon^2$ by any constant and it will behave asymptotically the same. But the results would be different in practice. More specifically, let me try to implement to see how it behaves, would I do something like

k = ...; eps = ...; c = round(k * log(k) / eps^2); 

or should I do

scale = ...; # some constant like 2 c = round(scale * k * log(k) / eps^2); 

How can I decide on the scale. What actually does this big-O order values for error bounds mean? Where should I look? Any recommendations are appreciated.

Mahoney, M. W., & Drineas, P. (2009). CUR matrix decompositions for improved data analysis. Proc. of the National Acad. of Sciences, 106(3), 697-702. doi:10.1073/pnas.0803205106

  • 1
    As you said: the algorithm should behave the same with any constant, but in practice the specific value of the constant will matter. You should try evaluating *imperically* the performance of the algorithm for different values of the constant, and reach a conclusion on optimal values (that is, values that make the implementation either faster, or more numerically stable).2011-12-31
  • 0
    I think I will go for this.2012-01-02

1 Answers 1