How to optimally trap points in high-dimensional spaces inside ellipsoids
1–10 of 18 posts
Re: How to optimally trap points in high-dimensional spaces inside ellipsoids
#2Nice short piece, reduces the geometric problem to a semidefinite program which can be solved by generic optimisation codes without drowning the reader in detail.
Re: How to optimally trap points in high-dimensional spaces inside ellipsoids
#3If you find this interesting, you might enjoy my write up of the Matoušek-Sharir-Welzl (MSW) algorithm used by D3’s circle-packing layout.
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
Re: How to optimally trap points in high-dimensional spaces inside ellipsoids
#4Nice 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?
Re: How to optimally trap points in high-dimensional spaces inside ellipsoids
#5Well 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.
Re: How to optimally trap points in high-dimensional spaces inside ellipsoids
#6There 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.
Re: How to optimally trap points in high-dimensional spaces inside ellipsoids
#7Sweet. Now to implement this into orbital planning for KSP…
Re: How to optimally trap points in high-dimensional spaces inside ellipsoids
#8Nice 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?
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.
Re: How to optimally trap points in high-dimensional spaces inside ellipsoids
#9Nice 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...
Re: How to optimally trap points in high-dimensional spaces inside ellipsoids
#10This 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.