2
$\begingroup$

I have a large set $\mathbf{V}$ of vectors in $\mathbb{R}^d\setminus\{\mathbf{0}\}$ and need to find a vector $\mathbf{u}$ that maximizes $\sum_{\mathbf{v}\in\mathbf{V}}\mathbf{1}_{\mathbf{u}\cdot\mathbf{v}>0}$, which is to say the count of vectors in $\mathbf{V}$ that have a positive dot product with $\mathbf{u}$. Alternatively, one could also phrase this problem as finding a maximum subset of the half-spaces defined by the elements of $\mathbf{V}$ such that the intersection of those half-spaces is nonempty. I am wondering if an efficient algorithm for this problem is known.

Just to rule out an obvious idea, normalizing the vectors in $\mathbf{V}$ and taking their average does not solve the problem. In particular, even in two dimensions a normalized set like $\mathbf{V}=\left\{\left(1, 0\vphantom{\frac{0}{0}}\right)\!, \left(-\frac{5}{13}, \frac{12}{13}\right)\!, \left(-\frac{5}{13}, -\frac{12}{13}\right)\right\}$ would have average $\left(\frac{1}{13},0\right)$, which only has a positive dot product with $\left(1, 0\vphantom{\frac{0}{0}}\right)$, whereas an alternative like $\left(-1, 0\vphantom{\frac{0}{0}}\right)$ has a positive dot product with both $\left(-\frac{5}{13}, \frac{12}{13}\right)$ and $\left(-\frac{5}{13}, -\frac{12}{13}\right)$.

A correct but slow algorithm would be to consider all size-$(d-1)$ subsets of $\mathbf{V}$, use each subset to construct a candidate vector orthogonal to everything in the subset, and then keep whichever of these candidates maximizes the count. But the run time of that design has $d$ in an exponent, so it scales poorly. Is there something better?

Context that I don't think affects the answer, but I will include anyway in case I am wrong, and it is relevant:

  • In this particular case, I actually have $\mathbf{V}\in\mathbb{Z}^d\setminus\{\mathbf{0}\}$, so the components are in fact integers.
  • For the particular application, I would be very surprised if the answer $\mathbf{u}$ did not have all positive components, though I still expect vectors in $\mathbf{V}$ to have components with mixed signs.
  • I also suspect that the subspace of solutions will be connected, and it would be nice to compute a $\mathbf{u}$ that is in the middle of this space so that its quality isn't super sensitive to issues with precision, rounding, etc. later on.
Improve this question
$\endgroup$
3
  • $\begingroup$ If you are happy with approximations, this might be useful: arxiv.org/abs/2106.13851 $\endgroup$
    – Tassle
    Commented Dec 10, 2023 at 12:55
  • $\begingroup$ @Tassle Could you turn that into an answer? Their algorithm considers half-spaces with boundaries away from the origin, which is different than my question, but as I look more closely, I think it could still be adapted to that restriction. So I will probably take this route if no efficient exact solution turns up. $\endgroup$
    – multiplywithadot
    Commented Dec 11, 2023 at 2:51
  • $\begingroup$ I suspect your problem is NP-hard, as it is basically finding a one-class SVM with 0-1 loss, and it is apparently known that optimizing for a (two-class) SVM with 0-1 loss is NP-hard (though I don't know the proof off-hand). $\endgroup$
    – D.W. ♦
    Commented Dec 11, 2023 at 18:12

1 Answer 1

Reset to default
1
$\begingroup$

If I understand your question correctly, you are describing a problem that is almost identical to the optimization problem in Support Vector Machines. The only difference is that in your case the separating plane is not offset from the origin, i.e. $b=0$. If a $u$ exists that makes all dot products positive, you could solve the following convex optimization problem:

$$ \begin{matrix} \mathcal{minimize}_u && 0 \\ \mathcal{subject} \; to && V^Tu \ge 1 \end{matrix} $$

If violations are possible, you could introduce a slack/error vector $e$ solve the following problem:

$$ \begin{matrix} \mathcal{minimize}_{u,e} && \max_i{e_i} \\ \mathcal{subject} \; to && V^Tu \ge 1-e \\&& e \ge 0 \end{matrix} $$

Which, again, is a convex optimization problem. There many open-source convex solvers available, like CVXOPT and CVXPY for Python.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Great connection! I think it's very close, but not quite correct, I think. It looks to me like the question is related but different from the standard SVM problem. The problem as stated in the question is effectively asks us to minimize the 0-1 loss, whereas your optimization formulation minimizes the hinge loss. Consequently solving the optimization problem in this answer doesn't (necessarily) yield the optimal solution to the problem in the question. $\endgroup$
    – D.W. ♦
    Commented Dec 11, 2023 at 0:44
  • 1
    $\begingroup$ To elaborate on @D.W.'s comment above, unfortunately, the vector minimizing $e$ might be arbitrarily bad. For instance, when one vector in $\mathbf{V}$ is $(1,0,\ldots,0)$, and the other vectors are all $(-\epsilon,\ldots)$ in some symmetric arrangement, the formulation in this answer has its optimum at $(1,0,\ldots,0)$, which gives $e=\epsilon$, but its count of positive dot products would only be $1$ instead of the true optimum, $\left\lvert V\right\rvert-1$. And the likelihood of such problems appearing grows with increasing $d$. Still, I appreciate the thought—it was a good idea. $\endgroup$
    – multiplywithadot
    Commented Dec 11, 2023 at 2:47
  • $\begingroup$ I am out of my depth here, but I believe it does minimize the 0-1 loss. It's hidden in the boundary constraints (BC). Note that the BC are $\ge 1$ not $\ge 0$. In the counterexample given, $(V^Tu)_2$ would be $-\epsilon$ which would be much less than $1 - e_2 \approx 1$. That would be a massive boundary violation. See this post. P.S.: The formulation of my convex optimization problem might be off. $\endgroup$
    – DirkT
    Commented Dec 11, 2023 at 6:16
  • 1
    $\begingroup$ Can you edit your answer to add a proof of correctness for the second optimization formulation, i.e., explain why it finds the optimal solution to the original problem? I don't understand the explanation in your comment. To me it looks wrong. The optimal solution to the original problem might have $v^T u$ be extremely negative for some $v$, in which case you have to take some $e_i$ be extremely large; but there might be another solution that is worse by the original problem's metric, but has a smaller value for all $e_i$'s. $\endgroup$
    – D.W. ♦
    Commented Dec 11, 2023 at 18:09
  • $\begingroup$ But we minimize $\max_i{e_i}$ so large $e_i$ will be rejected. And the beauty of convex optimization is that we can reliably find the global minimum (in fact, there are no local minima). I will try to put together a proof, but as I said: I am out of my depth. It will take me a little time to brush up my SVM and convex optimization knowledge. $\endgroup$
    – DirkT
    Commented Dec 11, 2023 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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