I still haven’t quite figured out how to make D3’s implementation robust, though. Volodymyr Agafonkin’s robust-predicated would probably help…
https://github.com/mourner/robust-predicates
— one elegant trick I remember from there was that the value of a quadratic form with matrix A on vectors u and v (^T for transpose):
u^T A v
is interpreted as the dot product between the matrix A and the tensor product u v^T,
A • (u v^T)
— and dot product • on matrices is just from them being n×n vectors.
With that a lot of things are really nice now, e.g. interiors of ellipsoids correspond to intersections of halfspaces of matrices with the positive semidefinite cone. And halfspaces are simple to reason about and intersect!
This trick is also implicitly in the parent post, of course.
Well written piece, like that they walk through the problem formulation starting with the basics.
BTW is there a hackernews-type site or other aggregator that’s nothing but content like this? Maybe a subreddit? I’d love to read a few articles like this every day.
> So, our ellipse E is the set of all points y such that y = Ax where x is in the unit ball [and A is a transformation matrix].
So an ellipse is only something that exists following a transformation of a unit ball? So, these "unit balls" are the elemental atoms of this ellipsis physics? Technically speaking at least.
Every ellipse can be encoded by the matrix A (and the geometric concept is generalized to arbitrary dimensions).
Not sure I follow the physics analogy though. A unit ball is a specific case of an ellipse where A is the identity matrix. Perhaps the entries of A would be the atoms in this case as they uniquely shape it?
This is the premise behind some more recent self-supervised learning papers (see https://arxiv.org/abs/2303.03307). Turns out, it's a solid analog for classification tasks.
Nice short piece, reduces the geometric problem to a semidefinite program which can be solved by generic optimisation codes without drowning the reader in detail.
How useful is reducing to a semidefinite program in reality? A fair amount of stuff seems to conclude with "now that we've reduced to an SDP, it's all polytime from here baby, so we're done modulo boring implementation details that nobody cares about". But I've tried and failed to understand how meaningful that polytime is in a practical sense. Anybody know?
mbostock|2 years ago
https://observablehq.com/@d3/d3-packenclose
I still haven’t quite figured out how to make D3’s implementation robust, though. Volodymyr Agafonkin’s robust-predicated would probably help… https://github.com/mourner/robust-predicates
fiforpg|2 years ago
https://www.dmg.tuwien.ac.at/gruber/gruber_arbeiten/johnelli...
— one elegant trick I remember from there was that the value of a quadratic form with matrix A on vectors u and v (^T for transpose):
u^T A v
is interpreted as the dot product between the matrix A and the tensor product u v^T,
A • (u v^T)
— and dot product • on matrices is just from them being n×n vectors.
With that a lot of things are really nice now, e.g. interiors of ellipsoids correspond to intersections of halfspaces of matrices with the positive semidefinite cone. And halfspaces are simple to reason about and intersect!
This trick is also implicitly in the parent post, of course.
roger_|2 years ago
BTW is there a hackernews-type site or other aggregator that’s nothing but content like this? Maybe a subreddit? I’d love to read a few articles like this every day.
jakeogh|2 years ago
makerdiety|2 years ago
So an ellipse is only something that exists following a transformation of a unit ball? So, these "unit balls" are the elemental atoms of this ellipsis physics? Technically speaking at least.
dellamonica|2 years ago
Not sure I follow the physics analogy though. A unit ball is a specific case of an ellipse where A is the identity matrix. Perhaps the entries of A would be the atoms in this case as they uniquely shape it?
johnsutor|2 years ago
jjgreen|2 years ago
mycologos|2 years ago
a_gnostic|2 years ago