2
$\begingroup$

Given $M$ points in $\mathbb{R}^{N}$ (where $M$ is larger than $N$), I was wondering if there is an algorithm to find a $N-1$-dimensional hyperplane which goes through the origin and also intersects as many points as possible.

Specifically, does there exist an algorithm which runs faster than $O(M^{N})$ time? This is achieved by looking at all subspaces defined by each subset of $N-1$ points.

Furthermore, if there is no faster exact algorithm, I was wondering if there are any constant factor approximations which run faster than $O(M^{N})$. It would be greatly appreciated if someone can point me to the correct papers or references for these.

Improve this question
$\endgroup$
  • $\begingroup$ It looks like you've accidentally created two accounts/usernames. I suggest you register one of them and then merge your two accounts. $\endgroup$ – D.W.♦ Jul 6 '16 at 1:13
  • $\begingroup$ There may be approaches for creating axis-aligned hyperplanes, which may be useful for discrete data. For that you could walk through all points and create frequency tables for all coordinates. This may allow creating hyperplanes in something like $O(M*N)$. $\endgroup$ – TilmannZ Jul 6 '16 at 14:56
  • $\begingroup$ For approximation, one could use a cluster detection algorithm (elki.dbs.ifi.lmu.de/wiki/Algorithms). Then you could order the clusters by size and put your plane through the (N-1) largest clusters. Then do some micro-shifting to hit at as many points as possible from these clusters. Also: in practice you may have to think about your epsilon for numeric precision, because for most plane orientations, it will be next to impossible to have more than N-1 point on that plane with perfect numeric precision. $\endgroup$ – TilmannZ Jul 6 '16 at 15:16
  • $\begingroup$ And it may be worth considering the "curse of dimensionality". For large N, what is the lieklihood of points being on the same plane? For example, nearest-neighbour search becomes somewhat pointless for large N because the distances from a point to its closest and its furthest neighbor converge (at least for purely random data). For example for N=2000 and M=100,000 (distributed evenly in a cube [0.0,1.0]) the difference in distance between closest and farthest point is about 10%. $\endgroup$ – TilmannZ Jul 6 '16 at 15:29
2
$\begingroup$

I suspect your problem might be hard, for the following reason: The corresponding problem when working over a finite field is NP-hard.

Your problem is equivalent to the following:

Inputs: a $M \times N$ matrix $A$, with real-valued entries
Goal: Find $x \in \mathbb{R}^N$ that maximizes the number of 0 entries in $Ax$

The corresponding problem for a finite field (e.g., working with integers modulo a prime $p$, rather than real numbers) is known as the minimum-weight codeword problem for linear codes, and it is known to be NP-hard. See, e.g., https://cs.stackexchange.com/a/59922/755, Solving/Optimizing a linear system in a finite field (Z/2Z), https://cstheory.stackexchange.com/q/27460/5038, https://cstheory.stackexchange.com/q/21678/5038. It's always possible that the problem is dramatically easier for real numbers than over a finite field, but that seems like it might be a lot to hope for.

Anyway, I don't know if there are algorithms with running time better than $O(M^N)$, but I suspect it's hard (not likely to have a polynomial-time solution).

See also https://cstheory.stackexchange.com/q/3719/5038 for a related but different problem.

Improve this answer
$\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.