4 ms·

Forgive me if you make this clear in the text (I may have missed it), but you have various pull quotes which say: "The new R2 sequence is the only 2-dimensional

Forgive me if you make this clear in the text (I may have missed it), but you have various pull quotes which say: "The new R2 sequence is the only 2-dimensional low discrepancy quasirandom sequence where..." Are you saying that it's the only known sequence? Or the only one possible? If the second, do you have formal proofs for those claims?

extremelearning 8y ago
I somewhat stumbled on this during my efforts to improve some machine learning architecture I was working on, so unfortunately no formal proofs as yet. This is one reason why I went down the route of technical blog post rather than more academic routes which would no doubt require more rigour and precise language. Although in many cases I have reason to strongly believe that it is not possible for other sequences to have similar properties, until such proofs are established, I agree that in a technical paper it would be prudent for me to preface most of the quotes with “only known...”
- jacobolus 8y ago
  One thing I wondered is if there’s a way to tweak this (e.g. by skipping values in one direction) to have better region filling (with respect to Euclidean distance) when the aspect ratio is not square. Try sliding the top slider at https://beta.observablehq.com/@jrus/plastic-sequence https://beta.observablehq.com/@jrus/plastic-sequence to see what I mean.
  - extremelearning 8y ago
    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.
    - DoctorOetker 8y ago
      While your R2 sequence is obviously better than the others for hyper uniform distribution on the sphere, I can't help but notice there are still spiral patterns. (are we looking at a pole of the coordinate transform btw?). Is this fundamentally the same or similar problem as the rectangular stretch mentioned here? But with a "jacobian" stretch as opposed to a linear stretch? Could you please read the short section https://en.wikipedia.org/wiki/Orthogonal_matrix#Randomization https://en.wikipedia.org/wiki/Orthogonal_matrix#Randomizatio... ? It is very short, first it defines what is meant with a random orthogonal matrix, then it describes the problem with an incorrect approach, ... and then it describes a recursive procedure to generate a random orthogonal matrix of dimension D using D * (D+1) / 2 uniformly distributed numbers: >Stewart (1980) replaced this with a more efficient idea that Diaconis & Shahshahani (1987) later generalized as the "subgroup algorithm" (in which form it works just as well for permutations and rotations). To generate an (n + 1) × (n + 1) orthogonal matrix, take an n × n one and a uniformly distributed unit vector of dimension n + 1. Construct a Householder reflection from the vector, then apply it to the smaller matrix (embedded in the larger size with a 1 at the bottom right corner). I predict this will give a better uniform distribution on that sphere, if you share your code for generation and visualization I might try myself :) Also, I applaud you for the extremely clear exposition of the problem, thought process and analogies presented. The one section I found harder to grasp was the one on dithering, as I don't fully understand the process from input picture to output pixel locations and intensities...
      - extremelearning 8y ago
        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-a-sphere/ http://extremelearning.com.au/evenly-distributing-points-on-... [2] http://www.math.vanderbilt.edu/saffeb/texts/262.pdf http://www.math.vanderbilt.edu/saffeb/texts/262.pdf

extremelearning 8y ago

I somewhat stumbled on this during my efforts to improve some machine learning architecture I was working on, so unfortunately no formal proofs as yet. This is one reason why I went down the route of technical blog post rather than more academic routes which would no doubt require more rigour and precise language. Although in many cases I have reason to strongly believe that it is not possible for other sequences to have similar properties, until such proofs are established, I agree that in a technical paper it would be prudent for me to preface most of the quotes with “only known...”

jacobolus 8y ago
One thing I wondered is if there’s a way to tweak this (e.g. by skipping values in one direction) to have better region filling (with respect to Euclidean distance) when the aspect ratio is not square. Try sliding the top slider at https://beta.observablehq.com/@jrus/plastic-sequence https://beta.observablehq.com/@jrus/plastic-sequence to see what I mean.
- extremelearning 8y ago
  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.
  - DoctorOetker 8y ago
    While your R2 sequence is obviously better than the others for hyper uniform distribution on the sphere, I can't help but notice there are still spiral patterns. (are we looking at a pole of the coordinate transform btw?). Is this fundamentally the same or similar problem as the rectangular stretch mentioned here? But with a "jacobian" stretch as opposed to a linear stretch? Could you please read the short section https://en.wikipedia.org/wiki/Orthogonal_matrix#Randomization https://en.wikipedia.org/wiki/Orthogonal_matrix#Randomizatio... ? It is very short, first it defines what is meant with a random orthogonal matrix, then it describes the problem with an incorrect approach, ... and then it describes a recursive procedure to generate a random orthogonal matrix of dimension D using D * (D+1) / 2 uniformly distributed numbers: >Stewart (1980) replaced this with a more efficient idea that Diaconis & Shahshahani (1987) later generalized as the "subgroup algorithm" (in which form it works just as well for permutations and rotations). To generate an (n + 1) × (n + 1) orthogonal matrix, take an n × n one and a uniformly distributed unit vector of dimension n + 1. Construct a Householder reflection from the vector, then apply it to the smaller matrix (embedded in the larger size with a 1 at the bottom right corner). I predict this will give a better uniform distribution on that sphere, if you share your code for generation and visualization I might try myself :) Also, I applaud you for the extremely clear exposition of the problem, thought process and analogies presented. The one section I found harder to grasp was the one on dithering, as I don't fully understand the process from input picture to output pixel locations and intensities...
    - extremelearning 8y ago
      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-a-sphere/ http://extremelearning.com.au/evenly-distributing-points-on-... [2] http://www.math.vanderbilt.edu/saffeb/texts/262.pdf http://www.math.vanderbilt.edu/saffeb/texts/262.pdf