Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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). – user2468 Dec 31 '11 at 0:34
I think I will go for this. – petrichor Jan 2 '12 at 11:29

The authors are apparently only interested in asymptotically bounding the value c. In algorithm theory (I assume this is computational linear algebra), the growth rate tends to matter more than absolute values, even if the differences you discuss may seem large. Here is the wiki entry on it

which also gives a precise definition. A good source is the standard text book in algorithms\

The notation goes back to Knuth, if you'd like the source, in his famous

Knuth usually discusses his concepts in great detail as well.

share|cite|improve this answer
Actually, I know Big-O notation and asymptotic analysis well. But this is a different case. In algorithm analysis, we compute the complexity given the array has size N. For example we may have 2 additions in a loop, then the result will be 2 times the loop count. It is OK. Coefficient 2 is not leading here and we are not setting something to the complexity here. But in the question, I need to set some variable which is computed in Big-O notation. This is confusing part. – petrichor Jan 2 '12 at 11:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.