search

vbartle / VMLS-Companions

These are companion notebooks written in Julia and Python for: "Introduction to Applied Linear Algebra" by Boyd and Vandenberghe.
306 stars 129 forks source link

Chebyshev bound function #3

Open zhouyiqi91 opened 3 years ago

zhouyiqi91 commented 3 years ago

According to VMLS: cheb_bound = lambda x,a: npl.norm(x)**2//a**2

But in python companions，the denominator is not squared: cheb_bound = lambda x,a: npl.norm(x)**2//a

Is this a mistake?

vbartle commented 3 years ago

Hi! Can you share where you see //a**2 in VMLS? I agree that in the book on 47 and 48, the authors describe squaring the whole RHS. I believe it was written as you describe in the notebooks though, because in the Julia companion, found here, on 24 and 25, the authors describe floor(...//a) as an improvement in notation.

If this number is, say, 12.15, we can conclude that no more than 12 entries have absolute value at least a, since the number of entries is an integer. So the Chebyshev bound can be improved to be floor(‖x‖2/a), where floor(u) is the integer part of a positive number.

Curious what you think. And please let me know if you find anything else that might be incorrect!

adricortes commented 2 years ago

I came here to report the same. The mistake is still there in the VMLS Python Ch. 03 Norm.ipynb, in the cell where you have

cheb_bound = lambda x,a: npl.norm(x)**2//a

Thxs.