5
$\begingroup$

Let $A \in \mathbb{R}^m$ be some set with the property that it is easy (polynomial-time computation) to generate random elements $r \in A$. Is it then also easy to compute

$$ P_A(x) := \arg \min_{y\in A} \;\|y-x\| ,$$

that is, the set of elements in $A$ nearest $x$?

You may assume $A$ is locally affine, and whatever definition of random is most convenient. If that's still too vague, here are two examples where $A$ is discrete.

Suppose $A \subset \mathbb{R}^{n\times n}$ is the set of all $n!$ permutation matrices. It's clearly easy to generate random $n\times n$ permutation matrices. Moreover, the projection to a permutation matrix nearest a given $x\in\mathbb{R}^{n\times n}$ can be computed in time $n^3$ with the Hungarian algorithm.

Instead, let $A\subset\mathbb{R}^{n\times n\times n}$ be the set of tensors with $n^2$ 1s (rest 0) such that there's a single 1 in each row, column, and whatever you call the third index. This is the set of Latin squares and it's not easy to generate random elements (and computing projections is harder still).

Edit:

Iosif came up with a good counterexample: Given an arbitrary lattice basis, it's easy to generate lattice elements, while it is known to be hard to find nearest lattice points.

This suggests the following qualification on the set $A$: It should be possible to specify $A$ with a fixed amount of data, so the only parameter on which the complexity of the computation can depend is the dimension of the space.

For example, if $A=D_n$, the checkerboard lattice in $n$ dimensions, computing the nearest element is easy. Other examples with the fixed-data property are low rank matrices, sparse vectors, orthogonal matrices, and the probability simplex. For all of these it's easy to generate random elements, and finding nearest elements is also easy.

When the amount of data in the specification of $A$ is fixed, the set $A$ will have a lot of symmetry. Symmetry might therefore be another way to make the conjecture work. In fact, that would allow the $A$ comprising all permutations of a list of $n$ arbitrary real numbers. This $A$ has a lot of symmetry, despite an amount of data that grows with $n$, and projecting to it is easy.

Improve this question
$\endgroup$
12
  • 4
    $\begingroup$ In general, MathOverflow discourages "moving target" questions where you edit the question in response to an answer. If you have a different follow-up question, you should ask it as a separate question (and accept Iosif's answer if it resolves your original question). $\endgroup$ Commented Feb 26 at 13:26
  • $\begingroup$ I find the question to be a strange mix of complexity considerations, such as polynomial time, with a computable analysis context, because the setting $\mathbb{R}^m$ setting suggests that one would be talking about computable real numbers, that is, computable convergent sequences of approximations. What does it it mean exactly for the OP to speak of generating a real number in polynomial time? $\endgroup$ Commented Feb 26 at 15:44
  • $\begingroup$ Another confusion I have is the observation that for any set $A$ for which we are able computably to generate elements $r\in A$, then this will also be true for any superset $A^+\supseteq A$, which will definitely change the projection function, since some reals will now be closer to elements of $A^+$ that are not in $A$. And those new points could be noncomputable reals, hence definitely not computable. So doesn't this simply answer the question negatively? $\endgroup$ Commented Feb 26 at 15:47
  • 1
    $\begingroup$ @JoelDavidHamkins For you second point of confusion: I think that the OP does not ask for mere generation of elements $r\in A$, but for generation of a random sample (and I think that this means a uniform random sample in some sense). And of course, being able to sample uniformly at random from some set $A$ does not imply that you can sample uniformly at random from every superset $A'$. $\endgroup$ Commented Feb 27 at 13:07
  • 1
    $\begingroup$ The comments all make valid points, and I apologize again for my imperfectly crafted question. Still, the math community should acknowledge that users with different backgrounds come with different defaults. Pure math, with its precise language, is the gold standard when it comes to avoiding ambiguity. But it is not perfect, and I can dig up an article where Bill Thurston makes that point. My background is physics, and I will work hard to shift my defaults in the future. At the same time, math professionals might make an effort to read between the lines, as particular cases may warrant. $\endgroup$ Commented Feb 27 at 13:53

2 Answers 2

Reset to default
11
$\begingroup$

$\newcommand\R{\Bbb R}$Suppose that P $\ne$ NP. Then the answer is no (which should be expected, as the two problems, of generating elements and of finding a minimizer, seem hardly related). Moreover, for any real $c>1$ and each natural $k$ there is a subset $B$ of $\R^k$ whose elements can be generated in polynomial time, whereas the problem of determining $$m_x(B):=\min_{y\in B}\|y-x\|$$ within the factor $c$ is NP-hard and hence cannot be solved in polynomial time.

Indeed, let $$B:=\{Mx\colon x\in GF(2)^k\},$$ where $M\in GF(2)^{k\times k}$. Then clearly a random element of $B$ (whose distribution is, say, the pushforward by the action of the matrix $M$ of the uniform distribution on $GF(2)^k$) can be generated in polynomial time.

On the other hand, here the problem of determining $m_x(B)$ is the Nearest-Codeword Problem, which is NP-hard (even of determining $m_x(B)$ up to any given real factor $c>1$), according to Theorem 2. $\quad\Box$

(In this case, all the $\ell^p$-norms are equivalent to one another, in the sense that $\|y-x\|_p^p=\|y-x\|_1$ for all real $p>0$ and all $x,y$ in $GF(2)^k$.)

Improve this answer
$\endgroup$
3
$\begingroup$

Being able to compute $\operatorname{argmin}_{y \in A} |x - y|$ at all is a rather strong and peculiar demand. Already in one dimension, let $A_\varepsilon$ be of the form $[-2,-1-\varepsilon] \cup [1-\varepsilon,2]$ (or its interior, if you prefer to work with open sets). Having a minimizer for $\min_{y \in A_\varepsilon} |y|$ entails knowing a true case amongst $\varepsilon \leq 0$ and $\varepsilon \geq 0$.

I would expect that every sensible notion of ``being able to sample from $A_\varepsilon$'' will depend computably on $\varepsilon \in \mathbb{R}$. This shows that we can easily have the abilty to sample, but finding projection points wouldn't even be computable.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I probably don't understand what you mean by "computable" here. In my understanding of the OP, in your example we can easily do rejection sampling for $A_\varepsilon$ (sample uniformly from $[-2,2]$ and reject if in $]-1-\varepsilon,1-\varepsilon[$). If we can do this we can also project onto $A_\varepsilon$ easily, by just checking which of the four endpoints of the set is the closest. $\endgroup$ Commented Feb 27 at 13:13
  • $\begingroup$ @Dirk There is no algorithm that takes a real $\varepsilon$ and outputs a true case amongst $\varepsilon \leq 0$ and $\varepsilon \geq 0$, and that means we cannot tell which endpoint is the closest. $\endgroup$ Commented Feb 27 at 15:17
  • $\begingroup$ So that's probably using this formal definition of computable which (I guess) is not meant by the OP. I think that in the OP, it is really just asked if this can be done in floating points in reasonable cases. Another thing: What do you mean by "sample from"? I think that one is after "sampling uniformly at random". If I understand your argument correctly, the rejection sampling that I described is also impossible, right? $\endgroup$ Commented Feb 27 at 19:04
  • $\begingroup$ @Dirk No, the rejection sampling works because the probability of our sample points being on the boundary is 0, so it doesn't matter that we can't decide whether to keep or reject there doesnt matter. $\endgroup$ Commented Feb 27 at 19:30
  • $\begingroup$ Ah, I see, thanks! (In the sense of the question, the numbers $1-\varepsilon$ and $-1-\varepsilon$ are available on the computer and well different from $1$ and $-1$ respectively, I guess…) $\endgroup$ Commented Feb 27 at 19:35

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.