[HN Gopher] How to optimally trap points in high-dimensional spa...
___________________________________________________________________
How to optimally trap points in high-dimensional spaces inside
ellipsoids
Author : tartakovsky
Score : 74 points
Date : 2024-02-22 11:55 UTC (11 hours ago)
(HTM) web link (www.adrianriv.com)
(TXT) w3m dump (www.adrianriv.com)
| jjgreen wrote:
| 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.
| mycologos wrote:
| 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?
| nihzm wrote:
| 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.
| cevi wrote:
| 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...
| mbostock wrote:
| If you find this interesting, you might enjoy my write up of the
| Matousek-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
| roger_ wrote:
| 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.
| fiforpg wrote:
| 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 nxn
| 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.
| a_gnostic wrote:
| Sweet. Now to implement this into orbital planning for KSP...
| johnsutor wrote:
| 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.
___________________________________________________________________
(page generated 2024-02-22 23:01 UTC)