The Deceptively Asymmetric Unit Sphere(tangramvision.com)
tangramvision.com
The Deceptively Asymmetric Unit Sphere
https://www.tangramvision.com/blog/the-deceptively-asymmetric-unit-sphere
31 comments
Something that may be of interest to CS people and reveals the complexity of the unit sphere is the following problem:
Find an efficient (class of) algorithm(s) to select a large number N of uniformly distributed points on S^2, where "uniformly distributed" is given in a more flexible sense than the usual one. For instance, you may want to minimize the Weyl discrepancy between average and integral, or you may want to focus more on minimizing the number of ε-clusters of distances.
One of the most elegant approaches to this problem is the classic work of Lubotzky, Phillips and Sarnak: Hecke Operators and Distributing Points on the Sphere I and II. They translate the problem to one of generating good sequences of elements of SO(3), which they attack with a combination of harmonic analysis on the semisimple groups, homogeneous dynamics and number theory with Hecke operators as their central tool.
Find an efficient (class of) algorithm(s) to select a large number N of uniformly distributed points on S^2, where "uniformly distributed" is given in a more flexible sense than the usual one. For instance, you may want to minimize the Weyl discrepancy between average and integral, or you may want to focus more on minimizing the number of ε-clusters of distances.
One of the most elegant approaches to this problem is the classic work of Lubotzky, Phillips and Sarnak: Hecke Operators and Distributing Points on the Sphere I and II. They translate the problem to one of generating good sequences of elements of SO(3), which they attack with a combination of harmonic analysis on the semisimple groups, homogeneous dynamics and number theory with Hecke operators as their central tool.
Were does the notation T^2 for oriented real projective space come from? That's just bad, because it is not a torus but a sphere, and the two are topologically very different!
If you click through the first link there’s an explanation:
“In precise mathematical terms, this set of rays is called the oriented real projective plane and is commonly denoted by T^2. If you’ve seen this terminology before, you’ll notice that this is a torus. This is because in real-projective geometry, we also add the points and lines “at infinity”.”
“In precise mathematical terms, this set of rays is called the oriented real projective plane and is commonly denoted by T^2. If you’ve seen this terminology before, you’ll notice that this is a torus. This is because in real-projective geometry, we also add the points and lines “at infinity”.”
It's incorrect, though.
The oriented real projective plane is a sphere, not a torus.
The projective points at infinity (one point for every 1-D angle (R mod 2pi)) form the equator of the sphere.
The T in T² is for "two-sided" , not Torus.
The torus explanation that Tangram gives doesn't make sense. In a pinhole projection, the horizontal and vertical infinites do not "wrap around" to meet. There is no meaningful "horizontal" and "vertical", the system is rotationally symmetric, which forms a hemisphere of curve it to make it compact. (Half sphere because you can only see one half of the space outside a pinhole camera)
https://en.m.wikipedia.org/wiki/Oriented_projective_geometry
The oriented real projective plane is a sphere, not a torus.
The projective points at infinity (one point for every 1-D angle (R mod 2pi)) form the equator of the sphere.
The T in T² is for "two-sided" , not Torus.
The torus explanation that Tangram gives doesn't make sense. In a pinhole projection, the horizontal and vertical infinites do not "wrap around" to meet. There is no meaningful "horizontal" and "vertical", the system is rotationally symmetric, which forms a hemisphere of curve it to make it compact. (Half sphere because you can only see one half of the space outside a pinhole camera)
https://en.m.wikipedia.org/wiki/Oriented_projective_geometry
You're right. I've messed up. The notation here is a bit misleading and I didn't dig as deep here as I should have. I'll fix the website soon.
Thanks for sharing such an insightful article of complex material. Some follow-up showing how this helps optimization (gradient descent, Newton solvers?) would be great.
>> For convenience of notation, we’ll drop the explicit parametrization of the curves and denote this vector shift as [...]
FYI for clarity I wish the explicit parametrization was kept, even though it is more verbose.
>> For convenience of notation, we’ll drop the explicit parametrization of the curves and denote this vector shift as [...]
FYI for clarity I wish the explicit parametrization was kept, even though it is more verbose.
Indeed, I should have been a more critical reader!
Great example of a corporate blog! My immediate reaction is I want to work in this team.
Another awesome mathematics article that loses me about 10-15% of the way in do to my own technical limitations. Any tips from HN on how to improve my ability to get thru, say, 45-50% of these types of articles?? Generally speaking, not specific to the math in OP article
spend 1-2 years learning consistently _any_ undergrad math. id recommend focusing on “mastering” multivariable calculus, dependencies included. but keep taking peaks of higher level stuff or just articles as these. doing this is important as the math can be contextualised in many ways and being exposed to those ways helps you internalise intuitions
To be clear I am not being sarcastic in saying this but the only method I’ve found to work with any consistency is: Try, try again.
I find this is what works for me. I seem to be quite a nonlinear learner. I struggle with the methodical x leads to y leads to z approach.
I tend to try and take on the whole thing and not really understand it then repeat the process (often from different sources) after a while I just seem to understand more and more
I tend to try and take on the whole thing and not really understand it then repeat the process (often from different sources) after a while I just seem to understand more and more
[deleted]
Author of this post. I have an undergraduate in Applied Mathematics and my training in the "definition -> proposition -> proof" style of mathematics probably comes through in the article more than I wanted it to.
That being said, I began studying Differential Geometry and Lie Groups as part of my graduate degree in Electrical Engineering. Engineers think about problems very differently than mathematicians and I've benefited a lot from taking a more geometric-based and visual approach to learning in the years following my undergraduate.
So, my prescription would be to play around with math ideas when you see them. Create a script to draw what you are trying to visualize. This was my first time using the `manim` library and I gained a deeper appreciation and intuition for the ideas presented in the article even though I've studied them dozens of times!
Overall, learning math is a slow and deliberate exercise. Don't get down on yourself if you don't understand something at first glance. Feel free to pause, verify an idea (either visually or with a formal proof) and then continue on a more firm base of understanding.
That being said, I began studying Differential Geometry and Lie Groups as part of my graduate degree in Electrical Engineering. Engineers think about problems very differently than mathematicians and I've benefited a lot from taking a more geometric-based and visual approach to learning in the years following my undergraduate.
So, my prescription would be to play around with math ideas when you see them. Create a script to draw what you are trying to visualize. This was my first time using the `manim` library and I gained a deeper appreciation and intuition for the ideas presented in the article even though I've studied them dozens of times!
Overall, learning math is a slow and deliberate exercise. Don't get down on yourself if you don't understand something at first glance. Feel free to pause, verify an idea (either visually or with a formal proof) and then continue on a more firm base of understanding.
I think where you might lose some of the uninitiated in this post is in introducing the term "operator" without definition or illustration
It's been way too many years since uni for me to do any rigorous math, so what tends to help me is to try and get an approximate intuition instead. As a specific example, this article talks a lot about manifolds. Since I didn't study math in English, I don't know what that is, so I go and look it up. A simplified, but intuitive model [0] might be:
> A manifold is a space that is locally Euclidean, but globally might be complicated, e.g. a torus or sphere, or etc.
Okay, so that's reasonably simple. As an intuition, if we imagine a 2D character living on the surface of the sphere, if they walk forward, from their perspective they just move forward in 2D, but from our outside perspective, they're moving in 3D on the curved surface of a sphere.
Once I have this, I try and read until I get lost again. I don't try to rigorously solve or follow through with each equation, but to rather approximately understand what the idea is.
[0] https://math.stackexchange.com/q/1211762/128941
> A manifold is a space that is locally Euclidean, but globally might be complicated, e.g. a torus or sphere, or etc.
Okay, so that's reasonably simple. As an intuition, if we imagine a 2D character living on the surface of the sphere, if they walk forward, from their perspective they just move forward in 2D, but from our outside perspective, they're moving in 3D on the curved surface of a sphere.
Once I have this, I try and read until I get lost again. I don't try to rigorously solve or follow through with each equation, but to rather approximately understand what the idea is.
[0] https://math.stackexchange.com/q/1211762/128941
You just don't know enough about the foundations the article is building off of to follow it. What I do in such a case, is forget about the article at hand, and make a list of things that I don't understand and then try and learn about them all individually. It's okay to just bounce off of a technical article and use it as motivation to learn more about the subject from other sources.
For example in this article, I got completely stuck on how the Exp and Log functions he's talking about relate to the usual definitions of those functions, so now I'm going down that rabbit hole.
For example in this article, I got completely stuck on how the Exp and Log functions he's talking about relate to the usual definitions of those functions, so now I'm going down that rabbit hole.
What is it you’re trying to get out of reading these types of articles? In my experience, it’s hard to really retain info unless I’m actively working on a related problem, so reading something like this out of the blue is mostly just entertainment (and a way to check existing knowledge).
Learning maths is all about having the proper prerequisites (and time and effort...). The concepts all build on simpler ones in a hierarchy leading down to our basic ideas of numbers and space, so if you're missing any of those simpler ones you simply won't be able to understand anything more advanced or exotic except in a very fragmentary or superficial way.
For differential geometry the prerequisites are linear algebra and multi-variable calculus, and the prerequisite for multi-variable calculus is single variable calculus, and the prerequisites for each of those is basic algebra, trigonometry, and elementary geometry.
You don't need to know everything about each of these to get things at the next level, but a thorough grounding in the basics is essential in my experience. There's a reason every STEM field begins with calculus and linear algebra - they're used everywhere in anything at a higher level. Once you get through those you will find things open up for you.
I don't know your level so it's difficult to make any concrete recommendations, but in general I find Lang's books to be clear and efficient sources. His Short Calculus covers all the basics of single variable calculus in less than 200 pages, instead of ~500 pages like many intro to calc books. Similarly his Calculus of Several Variables is ~300 pages instead of 500-700. Alternatively a mathematical methods for physicists book like the one by Riley, Hobson, and Bence might suit you. It's huge (~1300 pages), but you can pick out the chapters you want to learn from and it builds up from the basics to some quite sophisticated mathematics and has references if you want more depth on some topic, and great problems.
I find I don't really learn anything from watching videos. They can be complementary, but most of the learning with maths comes from doing problems after reading through an introduction to the concepts
For differential geometry the prerequisites are linear algebra and multi-variable calculus, and the prerequisite for multi-variable calculus is single variable calculus, and the prerequisites for each of those is basic algebra, trigonometry, and elementary geometry.
You don't need to know everything about each of these to get things at the next level, but a thorough grounding in the basics is essential in my experience. There's a reason every STEM field begins with calculus and linear algebra - they're used everywhere in anything at a higher level. Once you get through those you will find things open up for you.
I don't know your level so it's difficult to make any concrete recommendations, but in general I find Lang's books to be clear and efficient sources. His Short Calculus covers all the basics of single variable calculus in less than 200 pages, instead of ~500 pages like many intro to calc books. Similarly his Calculus of Several Variables is ~300 pages instead of 500-700. Alternatively a mathematical methods for physicists book like the one by Riley, Hobson, and Bence might suit you. It's huge (~1300 pages), but you can pick out the chapters you want to learn from and it builds up from the basics to some quite sophisticated mathematics and has references if you want more depth on some topic, and great problems.
I find I don't really learn anything from watching videos. They can be complementary, but most of the learning with maths comes from doing problems after reading through an introduction to the concepts
Study more math? It’s hard and takes a long time; there isn’t really a royal road.
Never underestimate the power of das blinkenlights to entertain lazy dumb people.
Very nice "visual" introduction a topic that's usually treated very abstractly in math textbooks! If you'd like more of such a visual perspective on differential geometry, I recommend Tristan Needham's book [1].
[1]: https://press.princeton.edu/books/paperback/9780691203706/vi...
[1]: https://press.princeton.edu/books/paperback/9780691203706/vi...
Can this playlist based on the book be a good substitute for the book?
https://www.youtube.com/watch?v=mKtctCyd0rs&list=PLWEiAJhCw-...
https://www.youtube.com/watch?v=mKtctCyd0rs&list=PLWEiAJhCw-...
Depends on how much of the work you do yourself.
Math is like skiing or playing the guitar, you don't get better by watching others do it.
Personally I find videos useful to augment books, but rarely a substitute for them. But I am bad about pausing, ruminating and practicing, you may be more successful than I.
But practice is required IMHO.
Math is like skiing or playing the guitar, you don't get better by watching others do it.
Personally I find videos useful to augment books, but rarely a substitute for them. But I am bad about pausing, ruminating and practicing, you may be more successful than I.
But practice is required IMHO.
Well... there are some things one can get better at by watching — chess, for example. However, of course, you're right: in mathematics (and probably chess?) 90% of the learning has to be done yourself.
Ooh thanks, looks really nice!
No mention of quaternions and SLERP?
Hey, I'm the author of this post.
Quaternions and SLERP are absolutely a fundamental part of 3D vision (and game development too). However, I wanted to focus this post mainly on the question "why is optimizing on the unit sphere difficult?" As the post stands, it's already quite verbose.
Maybe I'll find some time to do a deep dive on common Lie Groups used in computer vision e.g. SO(3), SE(3) and Sim(3) and also the common representations used for those groups.
Quaternions and SLERP are absolutely a fundamental part of 3D vision (and game development too). However, I wanted to focus this post mainly on the question "why is optimizing on the unit sphere difficult?" As the post stands, it's already quite verbose.
Maybe I'll find some time to do a deep dive on common Lie Groups used in computer vision e.g. SO(3), SE(3) and Sim(3) and also the common representations used for those groups.
> Maybe I'll find some time to do a deep dive on common Lie Groups used in computer vision e.g. SO(3), SE(3) and Sim(3) and also the common representations used for those groups.
+1
Also, great article!
+1
Also, great article!
I'd love such an article.
I wish someone had told me about these computer vision applications of Lie groups when I was writing my dissertation on Lie groups, but better late than never!
I wish someone had told me about these computer vision applications of Lie groups when I was writing my dissertation on Lie groups, but better late than never!
[0]: https://en.wikipedia.org/wiki/Hairy_ball_theorem