extremelearning

Thanks! To be honest, I hadn't previously made it prominent as I thought RSS had basically died several years ago. However, based on the multiple comments in this parent thread, evidently RSS is still alive and well. So I'll definitely update my blog now to make it more visible!

I am a statistician / data scientist who blogs about nifty sampling methods, which are frequently used in rendering computer graphics such as: ray-tracing (via Quasi-Monte Carlo methods), object placement, dithering, etc...

http://www.extremelearning.com.au

All these methods try to find the most efficient sampling techniques that minimize various undesirable effects such as aliasing.

Techniques and topics include: blue noise distributions; low discrepancy quasirandom sequences; orthogonal grid-based sampling; and even-sampling on the surface of n-spheres.

My most favourite articles (two of which have previously been featured on HN) include:

* "The unreasonable effectiveness of quasirandom sequences" http://extremelearning.com.au/unreasonable-effectiveness-of-...

* "A new method to construct isotropic blue noise with uniform projections" http://extremelearning.com.au/isotropic-blue-noise-point-set...

* "Evenly distributing points on a sphere" http://extremelearning.com.au/evenly-distributing-points-on-...

I hope that someone finds some of these useful and interesting. ;)

i suspect a caching issue. I cleared my wordpress cache, so hopefully it will appear correct to others soon. ;)

Yes.

Consider π. For any S>0, you can construct an infinite number of rational approximations that have a score of less than S.

But for any quadratic irrational (surd), as the depth of the corresponding continued fraction increases, the score will converge (in an alternating manner) to a critical score, S.

This means that for any score S < S, there is only a finite set of rational approximations that have a score of less than S.

For example, in figure 3, for S=0.4 < 1/√5 ≃ 0.447, there is only one fraction that gives a score of less than S=0.4.

Hope that helps!

Good question, but I don't know and haven't really done anything substantially related that might even give us a hint.

Hopefully someone else chime in on this thread. ;)

I pondered this issue for what seemed like an inordinate amount of time namely: on how to describe this subtle but key difference.

Unfortunately, I couldn't find a nice way, so i glossed over this point, which you correctly say makes many expressions and theorems cleaner and more elegant.

Furthermore, this difference helps explains why q^2 is a natural choice, which some other readers on this thread have enquired about.

@svat's comment and link may also be helpful in this regard.

Thanks. No, you aren't crazy, but maybe my typos made you crazy! ;)

I have now fixed a couple of typos in the grammar and continued fractions expressions for that section.

Generally my answer is that this is for the same reason that fitting lines of best fit to data is nearly always done via a least-squares fitting.

Squaring has a few major benefits.

The first is that is never negative.

Therefore, one might ask why don't we just take absolute value (1-norm)? It turns out that the absolute function makes many calculus expressions very messy. Thus, ironically, when analysing these concepts theoreticlly/algebraically it is usually easier to square the errors (use the 2-norm), rather than the 1-norm.

The x^2 function is a very elegant function that smoothly curves. The |x| function has a pointy corner at x=0, which causes many analytical headaches.

(Although, I must admit that in recent years with large-scale computing, errors based on the absolute value are making a notable comeback, especially in machine learning!)

Secondly, history seems to have shown that squaring is frequently the simplest transformation that leads to non-trivial results. Thus, the principle of Occam's razor, would suggest that 2 is a very good place to begin and end.

Finally, if we consider higher powers, it makes sense to ensure our errors are not negative, so that generally rules out cubes. Finding square roots, and roots of quadratic equations is relatively simple, but finding roots of degree 4 polynomials is very tough, and finding roots of higher even degree polynomials is usually intractable.

Hope that helps!

The distance from Angkor Wat to Giza is: 4754 miles. And the distance from Gize to Nazca is: 4754 x φ miles.

By adding these, you get that the distance from Angkor Wat to Nazca is 4754 (1+φ) miles.

But φ is defined such that 1+φ = φ², [Verify for yourself that 1.61803398875² = 2.61803398875]

So thus, the distance from Ankor Wat to Nazca can also be described as 4754 φ² miles.

Absolutely! Everybody loves the numberphile videos. They frequently distil deep maths topics into very intuitive and visual explanations. ;)

What I find fascinating is that there seem to be so many valid ways to generalize the Golden Ratio.

As you say, the "metallic means" [1] are quite well-known, and relate to the recurrence relation via: T(n) = m *T(n-1)+ T(n-2), for some constant integer m. For example, m=1 is the golden ratio, m=2 is the silver ratio,...

But one of my other posts [2], generalizes the Golden ratio via the "Harmonious Numbers", as defined by the lagged recurrence, T(n+m) = T(n)+T(n-1), for some constant m. In this case, m=1 relates to the Golden Ratio, and m=2 relates to the Plastic Number [3].

And then finally, this post explores generalizing it via a completely different perspective, that of "Lagrange Numbers".

It seems that we need to 'think outside the box' a litte when generalizing the Golden ratio, as there is not single obvious way to generalise continued fractions.

[1] https://en.wikipedia.org/wiki/Metallic_mean

[2] http://extremelearning.com.au/unreasonable-effectiveness-of-...

[3] https://en.wikipedia.org/wiki/Plastic_number

LOL! You're totally right. It should be 85/10 and 425/50. Now fixed.

Author here. Happy to try to answer any questions any one might have on this post or topic. )

Although using a low discrepancy sequence (eg Halton, Sobol, R2) might be a good starting point, these sequences are designed to maximize the distance between points assuming that the left-and-right edges wrap, as well as the top-and-bottom. As it seems that the OP does not require this condition, I wold presume you get better solutions which involve lots of going to and from the far-left to the far-right, etc..

(Ordered dither matrices might offer another good starting point.)

1. Stretching I think you and Jacob are on to something when we realise that the R_2 sequence (and presumably R_D) loses some of its properties when it is naively stretched. I think if we solve this problem then we can make some real progress in the sphere problem.

2. Regarding rotations. Yes, I agree. When i wrote 'rotations' i meant it very generally. Any direct transformations from one point on the sphere to another without requiring intermediate mappings such as on a Torus.

3. 6-tuples. This is a really interesting idea, and sorry I missed it the first time. I will definitely explore this idea more.

Sobol's sequence is really quite amazing. However, there are three reasons why it doesn't get as much attention as it probably deserves.

First is that the maths is far more complex than that of other sequences. Here is a the easiest description I have seen so far [1].

Secondly this complexity as well as the non-trivial requirement to carefully select the basis parameters means that the computing side is very very complex. To get an indication of its complexity, the code for Sobol generation in Mathematica and WolframAlpha is not done by Wolfram itself but rather "comes courtesy of the Intel MKL libraries,... Specifics of the implementation, such as choice of initial values, are not documented. Evaluation of this implementation in terms of discrepancy, projections, and performance in application remains for future work." [also 1]

Thirdly, as defined by d* discrepancy, ( which is by far the most common formal method of quatifying discrepancy) the Sobol sequence does not have an asymptotic discrepancy as low as many of other sequences.

Despite this last point, it has been found that in practice Sobol generally yields as good or better performance when used for numerical integrations.

I personally have a suspicion that this is because of the special property, called "Property A" [2] that all Sobol point sequences possess. However, I will let people much smarter than me comment on whether this belief is justified or not...

In one of my other posts [3], Sobol sequences outperform all of the other low discrepancy sequence (including my new R2 sequence) hands down.

Finally, please note that for brevity and clarity, my blog only shows one example for most topics. I will leave it to other authors, or future posts to more rigourously show how consistent the comparisons are....

[1] http://www.mathematica-journal.com/2011/12/a-toolbox-for-qua... [2] http://www.andreasaltelli.eu/file/repository/HD_SobolGenerat... [3] http://extremelearning.com.au/how-to-generate-a-sequence-of-...

That's great. I'm glad you got it working. ;)

Yes. I think that using the dither matrix based on the R_2 sequence should be competitive with any of the the dither masks mentioned on that link.

Thus in situations like video, and/or ray tracing where computing speed is of the essence, maybe a better mask such as the R2 dither mask would offer an improvement on existing methods.

However, in terms of end-quality I am not aware of any dither masks that are anywhere near as good as the state-of-the-art error diffusion algorithms. Thus, for a small number of images such as our favourite animated gifs, I would still be recommending an error-diffusion method. :)

Thank you for your kind words! Regarding the mapping of R_2 to the surface of the sphere, I totally agree that although it is better than other options, it is far from optimal. Also, yes, these visualizations are looking from the North pole downwards as I thought this viewpoint highlighted the differnces and discrepancies the best. It was this clearly suboptimal mapping that spurred me to write a prior blog post on improved ways to place N points on a sphere [1].

I think that much of the problem is not with the particular unit square point distribution but rather with the fact that we are using a mapping (lambert) that has a singularity at each pole.

For constant/given n, there is an excellent reference by Saff on mapping points to a sphere. However, if n is not known (ie you need an open sequence of points) I am not aware of any method that is better than simply/naively mapping a low discrepancy sequence from the unit square to S2.

I think that the most ideal situation will work directly on the surface of the sphere and consist of rotations from one point on the surface to the other. Thus, although this is not my area of expertise I wouldn't be surprised if methods such as what you cite may assist someone in finding a better spherical distribution.

And finally regarding the section on dithering. Thanks for the feedback. I will add some more background explanations to ensure that it is clearer for those who do not directly work in the graphics rendering space.

[1] http://extremelearning.com.au/evenly-distributing-points-on-... [2] http://www.math.vanderbilt.edu/saffeb/texts/262.pdf

That's strange. To double-check that i typed it into my blog correctly, I copy-and-pasted the code from the post into my python IDE and it compiles and runs properly in my environment. For what it is worth, I am using Python 2.7 on a 64-bit windows machine. Maybe someone else reading has some ideas?

You should notice that after my example code, I have included two other people's code demos so that you can see the same algorithm from a different perspective. Maybe these will help you understand what's required.

In summary, for 2 dimensions, x and y coordinates of the n-th term (n = 1,2,3,....) are defined as:

  g = 1.32471795724474602596090885447809 
  a1 = 1.0/g
  a2 = 1.0/(g*g)
  x[n] = (0.5+a1*n) %1
  y[n] = (0.5+a2*n) %1

where %1 is the mod 1 operator and takes the fractional part of the argument. Hope that helps.

I have now inserted some sound demonstrations into my blog post! You can now listen to what 1-dimensional (mon) and 2-dimensional (stereo) quasirandom sound might be like.

I will leave it to you to decide which ones you prefer, and maybe even think why some of the quasirandom sequences are more pleasant than others.

For those who have already visited the site, you may need to clear your browser cache to see/hear this update.

Unfortunately, I haven’t found a nice solution to this problem yet. For those requiring quasirandom Monte Carlo integration over a say a 2x1 rectangular grid there is always the option of scaling the unit square points by 2 and then rejecting half of the points. Not super elegant and not very efficient in high dimensions, but at least it is unbiased and maintains the low discrepancy characteristics.

Thanks for this advice. I am new to blogging and certainly new to HN front page etiquette. I think my excitement got the better of me! I have now taken it off.

Only blue noise... I have absolutely no idea what it would sound like. So that means I’ll definitely try it later tonight and update the blog post. Tx

Thanks for the kind words and promotion! ;) These findings were a combination of a lot of literature searching, perseverance, decades of mathematical intuition and computer modelling of various hypotheses. I had a problem to solve so I was determined to find a solution. And then combine this with my obsession with simplicity, it meant I didn’t just want to tweak a million parameters to get a result.

For a known fixed value of n, you can get amazing convergence rates. For example, the basic midpoint rule gives O(1/n^2) and Simpson's rule gives O(1/n^4).

Despite this, there are two major use cases for quasirandom sequences: The first is when n is not known upfront and so you can't create a lattice; and the second is in higher dimensions. The reason for this latter situation is because the number of points required to make a lattice in D dimensions scales exponentially in D, whereas the convergence rates for random or quasirandom sampling are (amazingly!) independent on the dimension.

I think that you would really like Owen's paper on this topic. It is very comprehensive and yet extremely readable [1]

1[ ]http://statweb.stanford.edu/~owen/mc/Ch-quadrature.pdf

Yes, using an open (infinite) one dimensional low-discrepancy sequence in conjunction with a space-filling curve such as the Hilbert-curve has been explored. For example by Owen [1]

Niederreiter himself has a beautiful paper that includes a section on weighted low discrepancy sequence [2] where he also cites several references within it that might be of interest to you.

[1] http://statweb.stanford.edu/~owen/reports/extgrid.pdf [2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.614...

My intent when I wrote that phrase was two-fold. Firstly to emphasise the large body of work that was done by Weyl, Kronecker, Hurwitz et al relating to the equidistribtuion theorem, badly approximately numbers and diophantine approximation. Armed with this knowledge it is easily proved that the recurrrence relation using the golden ratio mod 1 is optimal using almost any measure.

Although some other readers on HN may be able to see a connection between one dimensional quasirandom sequences and quadratic residue, unfortunately I can’t immediately see an explicit one. Sorry!

My second intent was to contrast this with how little is provably known for higher dimensions. To my knowledge, thanks to the phenomenal work by Halton, Sobol, Niederreiter et al, we know that many of the contemporary sequences are optimal in the limiting Big O sense, but there are no proofs even for d=2 for optimality for any of the sequences for general finite values of n.

Thanks tlb. You're totally right. I wrote the example code to match the notation used in the post which is a reflection of my maths background. I suspect that from a programming perspective using the recurrence relation:

z[i+1] = (z[i] + alpha) %1

is better practice in terms of both speed and accuracy. I have updated my post to make this clearer. Thanks.