2
$\begingroup$

Let $S$ be a $k$-simplex in $\mathbb{R}^k$. I'd like to find a hyperplane $P$ that passes through the origin such that projections of vertices of $S$ onto $P$ are as close as possible to the origin (in minimax sense). The distances are measured in $\ell_2$-norm.

I could only get trivial results for $k=2$, but even for $k=3$ I couldn't find a way to find a solution.

Any hint on whether there is a polynomial-time algorithm that can solve this would be appreciated. If you know papers that are relevant I'd be thankful if you let me know.

$\endgroup$
  • 1
    $\begingroup$ In other words, you are looking for Orthogonal Distance Minimax (or Chebyshev) Line Fitting, where the line is also forced to go through the origin. While a natural problem, it's likely to be hard. I'm pretty sure that Cross Validated has a higher concentration of experts in the area than Mathematics. $\endgroup$ – 40 votes Jul 21 '13 at 20:38
  • 1
    $\begingroup$ Two more things: (a) the minimum is not unique in general, for example the regular triangle centered at the origin has three minimal projections; (b) if you replace smallest containing cylinder with smallest containing cone, the problem becomes easier, and is solved here. $\endgroup$ – 40 votes Jul 21 '13 at 21:27
  • $\begingroup$ @40votes Thanks for you comments. I'll post it on Cross Validated as well. Regarding multiple solutions, you are right though it is not surprising since the problem can be cast as a non-convex optimization. $\endgroup$ – S.B. Jul 22 '13 at 14:29
  • $\begingroup$ @40votes The cone constrained form is also interesting, but I'm not sure if I can reduce my original problem to this form. $\endgroup$ – S.B. Jul 22 '13 at 14:30
  • $\begingroup$ Link to CV version. $\endgroup$ – 40 votes Jul 22 '13 at 20:23
2
$\begingroup$

In other words, you want to find a vector $x$ on the unit sphere such that $\max a_j(1-\langle x,x_j\rangle^2)$ is as small as possible where $a_j$ are given positive numbers and $x_j$ are given unit vectors. Let's just ask if it is possible to find a vector giving the value $m$ or less. Then the problem reduces to the simultaneous solvability of $|\langle x,x_j\rangle|>b_j$, i.e., to checking that the intersection of the slabs $|\langle x,x_j\rangle|\le b_j$ is contained in the sphere. As far as I know, it is fairly hopeless because, by a linear change of variable, you can restate it as the question about the maximum of a positive definite quadratic form on the cube $[-1,1]^k$. It is known (see this, for instance) that the maximization over $[0,1]^k$ is NP-hard and, frankly speaking, I do not see much difference. So, it looks like you should be looking for a good heuristic method with some reasonable running time, not for a full solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.