# Find distance to a set (subspace) without computing closest point

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.

• 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. – Andreas Cap Apr 7 '16 at 10:02
• I wonder if list decoding is relevant to your question. At least, it might be something of interest. en.wikipedia.org/wiki/List_decoding – Michael Apr 11 '16 at 20:09
• 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... – Benjamin Lindqvist May 11 '16 at 21:50
• 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. – Benjamin Lindqvist May 11 '16 at 21:56