6
$\begingroup$

General setup: we have a finite-dimensional normed linear space $(V, \| \cdot \|)$, a subspace $U \subset V$, and a fixed vector $v_0 \in V$. We want to find the distance between $v_0$ and $U$. (No cheating: $\| \cdot \|$ is not induced by an inner product!) We don't care about finding the closest $u^* \in U$ to $v$; this would of course solve the problem, but let's assume it's computationally infeasible. All we care about is finding the number $d_0 = \min_{u \in U} \|u - v_0\|$ (or a reasonable substitute). It's entirely possible that finding $d_0$ is equivalent to finding $u^*$, and this would be an acceptable answer to my question, but maybe there's some clever way to find $d_0$ without $u^*$.

Examples:

  1. (This is really a non-example.) If $V = \mathbb R^n$ (or some other Hilbert space), then we may use orthogonal projections, and everything's bunnies and butterflies. Great.
  2. If $V = \mathbb F_2^n$ with the Hamming norm $\|v\| = \#\{i \in [n] : v_i = 1\}$, then $U$ is a binary linear code. Finding $u^*$ is the hard-decision decoding problem, which is in general NP-complete. (There may be some special cases of $U$ that make things easier, but we cannot assume we're in such a case.) Then, I suppose what we're after is some way of "fingerprinting" elements of $V$ to see if they're near $U$. Fingerprinting $v_0$ will lead to something like an answer.

2 is the case that I really have in mind, but I'd be happy to hear anything relevant: a particular $(V, \| \cdot \|)$ where this does work, for example, or a relaxation of some conditions (maybe $V$ is just a metric space and $U$ is just a subset) which admits an affirmative example.

$\endgroup$
  • 3
    $\begingroup$ If you consider norms that are not induced by an inner product, there is no unique point $u^*$ anyway. Think for example about $V=\mathbb R^2$ with the $\infty$-norm, $U$ the $x$-axis and $v_0=(0,1)$ for which all points $(t,0)$ with $t\in [-1.1]$ are closest. $\endgroup$ – Andreas Cap Apr 7 '16 at 10:02
  • $\begingroup$ I wonder if list decoding is relevant to your question. At least, it might be something of interest. en.wikipedia.org/wiki/List_decoding $\endgroup$ – Michael Apr 11 '16 at 20:09
  • $\begingroup$ If you could find the distance $d^*$ to the set $U$ in polynomial time, then you would at most need to try $\binom{n}{d^*}$ vectors in order to find the distance minimizing vector. Sadly this is still exponential complexity in $n$ in the worst case so it doesn't prove that your problem is NP-hard. Hmm... $\endgroup$ – Benjamin Lindqvist May 11 '16 at 21:50
  • $\begingroup$ Wait, actually it's not exponential in $n$. It's exponential in $d^*$. But that's $\Theta(n)$ in the general case so it still holds. $\endgroup$ – Benjamin Lindqvist May 11 '16 at 21:56

Your Answer

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

Browse other questions tagged or ask your own question.