How to optimally trap points in high-dimensional spaces inside ellipsoids(adrianriv.com)
adrianriv.com
How to optimally trap points in high-dimensional spaces inside ellipsoids
https://www.adrianriv.com/blog/2024/02/19/minimum_volume_ellipsoid/
17 comments
There is a very nice short proof of John's ellipsoid theorem by Gruber and Schuster:
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.
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.
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.
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.
not quite an aggregator, but you might like https://rjlipton.wpcomstaging.com/
> 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.
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?
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?
How about a software development analogy then?:
A unit ball along with the possibility of doing linear transformations on the unit ball are dependencies for constructing an ellipse.
:)
The physics metaphor is meant to communicate that you can have different materials (like aluminum or air), depending on the combinations or parameters used for a particular ellipsis case. And the physics or dynamics of ellipses would be the study of how the combinations on the dependencies (that is, the atomic elements) create different ellipsis shapes and properties.
A unit ball along with the possibility of doing linear transformations on the unit ball are dependencies for constructing an ellipse.
:)
The physics metaphor is meant to communicate that you can have different materials (like aluminum or air), depending on the combinations or parameters used for a particular ellipsis case. And the physics or dynamics of ellipses would be the study of how the combinations on the dependencies (that is, the atomic elements) create different ellipsis shapes and properties.
So I think the answer to your question is ‘yes*’. In the sense that the ellipse is a function of the unit ball && the matrix A. In this sense you could say that all ellipsoids are linearly-deformed spheres.
But more probably, you would consider the sphere part to be essentially your basis vectors and not terribly informative. All the information is in the matrix. The only important data is the extent along each axis, not the fact that if you set all extents to 1 it happens to be a unit sphere
But more probably, you would consider the sphere part to be essentially your basis vectors and not terribly informative. All the information is in the matrix. The only important data is the extent along each axis, not the fact that if you set all extents to 1 it happens to be a unit sphere
Then, could we say that the general or abstract form of the ellipse is a set of vectors? And with that set, there is an identity element, namely the unit ball. And that the identity is what produces the uninteresting basis vectors. Maybe what makes the vector space (that is, the set of vectors) interesting is equipped linear operators on all the vector space's elements?
Maybe this whole structure, a set equipped with some operations, has distinguishable features. Or maybe it can perform as underlying machinery for practical endeavors.
Maybe this whole structure, a set equipped with some operations, has distinguishable features. Or maybe it can perform as underlying machinery for practical endeavors.
Yes, or most abstractly, the mathematical definition would be the set of points satisfying a constraint - namely sum of distance to foci is constant.
https://en.wikipedia.org/wiki/Ellipse?useskin=vector#Definit...
Or for the n-dimensional generalization: https://en.wikipedia.org/wiki/N-ellipse?useskin=vector
So in that sense an ellipse is a function `ellipse(p_1, ..., p_n, d)`. But given the foci you can get the vectors and vice versa. So one representation isn't necessarily 'more fundamental' than another. They just have different (equivalent) perspectives that lend more easily/naturally to certain problem contexts.
(for example, the set of points definition is a lot less directly useful than the matrix A if you're trying to do linear algebra)
The unit ball isn't really an inherent "identity element" for ellipses. It's more of a special case where the foci are equally spaced (eccentricity is zero).
If you want to go that route, the eccentricity is a more fundamental descriptor of all conic sections, of which ellipses and circles are just two. In fact, all conic sections can be described as `conic_section(p_1, ..., p_n, eccentricity)`. So maybe you'd argue that's more "fundamental" because it's more general.
https://en.wikipedia.org/wiki/Eccentricity_(mathematics)?use...
https://en.wikipedia.org/wiki/Ellipse?useskin=vector#Definit...
Or for the n-dimensional generalization: https://en.wikipedia.org/wiki/N-ellipse?useskin=vector
So in that sense an ellipse is a function `ellipse(p_1, ..., p_n, d)`. But given the foci you can get the vectors and vice versa. So one representation isn't necessarily 'more fundamental' than another. They just have different (equivalent) perspectives that lend more easily/naturally to certain problem contexts.
(for example, the set of points definition is a lot less directly useful than the matrix A if you're trying to do linear algebra)
The unit ball isn't really an inherent "identity element" for ellipses. It's more of a special case where the foci are equally spaced (eccentricity is zero).
If you want to go that route, the eccentricity is a more fundamental descriptor of all conic sections, of which ellipses and circles are just two. In fact, all conic sections can be described as `conic_section(p_1, ..., p_n, eccentricity)`. So maybe you'd argue that's more "fundamental" because it's more general.
https://en.wikipedia.org/wiki/Eccentricity_(mathematics)?use...
The ellipse can be also encoded by just the lengths along each axis and then by a rotation in R^n (which is just a unitary matrix multiplication). So in essence, for the problem in the original post there are three pieces of information needed: a translation, a rotation, and the deformations of the unit ball along the axes.
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?
In practice, even storing the matrices that show up in the problem formulation can be prohibitive, let alone running a solver. Often you need to take advantage of sparsity in a nontrivial way (see e.g. COSMO [1]), or take advantage of cases where the solution can be approximated by a low rank matrix, and recently there has been a trend in using first-order methods like ADMM rather than full interior-point algorithms. The review article [2] from 2019 gives a feel for how much work has gone into making large-scale semidefinite programming possible, but has this sentence in their conclusion section:
"Semidefinite programming is still far from being a mature technology like linear or quadratic programming."
[1] https://link.springer.com/article/10.1007/s10957-021-01896-x [2] https://www.annualreviews.org/doi/pdf/10.1146/annurev-contro...
"Semidefinite programming is still far from being a mature technology like linear or quadratic programming."
[1] https://link.springer.com/article/10.1007/s10957-021-01896-x [2] https://www.annualreviews.org/doi/pdf/10.1146/annurev-contro...
From my understanding nowadays SDP solvers are becoming well developed, even the open source ones. Also, from my limited experience it is usually the case that the problem being cast into an SDP has no other good ways of solving it, so polytime is better than no solution / NP solutions.
Sweet. Now to implement this into orbital planning for KSP…
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