A generalization of the distance formula

Question

It is well-known that the distance of a point (3D vector) $q$ from the plane $n \cdot ( r - r_0 ) = 0$ is given by

$d=\dfrac{ | n \cdot (q - r_0) | }{ \sqrt{ n \cdot n } } $​

In this problem, I seek a generalization of the formula to $\mathbb{R}^n$, and to multiple hyperplanes.

So consider a point $q \in \mathbb{R}^n$, I want to find the point $x \in \mathbb{R}^n$ which satisfies $A x = b$, where $A$ is an $m \times n$ known matrix whose rows are the normals to $m$ hyperplanes, where $m \lt n $, and $b \in \mathbb{R}^{m} $ is a known vector of $ m $ constants. Hence, $x$ lies on the intersection of $m$ hyperplanes, each described by:

$$ A_i x = b_i \hspace{48pt} , i = 1, ..., m $$

where $A_i$ is the $i$-th row of matrix $A$ and $b_i$ is the $i$-th element of vector $b$.

The problem is to determine the minimum distance between such an $x$ and point $q$ which is given.

The distance is assumed to be the Euclidean distance, given by,

$ d(x, q) = \sqrt{ (x - q)^T (x - q) }$

Answer 1

I guess you want to minimize $d(x,q)$ for a given $q$ where $x$ is a solution to $Ax=b$? Let $x_0$ be a solution to $Ax=b$. Then we get: $$ x = x_0 + R$$ with $R$ in the kernel of $A$. Let’s assume that $x_0$ is orthogonal to the kernel (else we can repace $x_0$ by the projection onto the space created by the rows of $A$). Then $$ ||x-q||^2 = ||x_0+R - q ||^2 $$ If we set $q_p$ the projection of $q$ onto the rows of $A$ and $q_o=q-q_p$ so that $q_o$ is in the kernel of $A$ and $q_p$ is orthogonal to the kernel of $A$. Then we thus get $$ ||x-q||^2 = ||x_0-q_p||^2 + ||R-q_o||^2$$

This is of course minimal if and only if $R=q_0$. Then the minimal distance is $$ ||x_0-q_p|| $$

Now let’s assume that the rows $l_j$ in $A$ are all orthonormal (if they aren’t we can make them). Then $q_p$ is given by $\sum_j \langle q, l_j\rangle l_j$ and $x_0$ gets replaced by $\sum_j \langle x_0, l_j\rangle l_j$. This gives then the formula $$ \sum_j | \langle x_0-q,l_j\rangle|$$ for the minimum distance.

In your original problem $A=n^T$ and $b=nr_0$. Assume $$||n||=1$$ Then $q_p = \langle q, n\rangle n$. Also $r=r_0$ is a solution to $Ax=b$. Then $x_0=\langle r_0,n\rangle n$. So we get: The minimal distance is $$ || x_0-q_o || = || \langle r_0,n\rangle n - \langle q,n\rangle n || = | \langle r_0-q, n\rangle |$$ which is your initial formula.

Answer 2

The problem can be stated as follows:

$\text{Minimize } (x- q)^T (x - q) , \text{subject to } A x = b$

Direct application of the Lagrangian multipliers method yields the desired result.

Define $g(x) = (x - q)^T (x - q) + \lambda^T(A x - b)$ where $\lambda \in \mathbb{R}^m$ is the Lagrangian multipliers vector. Then, the gradient with respect to $x$ is

$\nabla_x {g} = 2 (x - q) + A^T \lambda = 0 \hspace{48pt} (1) $

and the gradient with respect to $\lambda$ is:

$ \nabla_\lambda {g} = A x - b = 0 \hspace{48pt} (2) $

From $(1)$, we obtain,

$x = q - \frac{1}{2} A^T \lambda \hspace{48pt} (3)$

Substituting this into $(2)$,

$ A(q − \frac{1}{2}A^T \lambda) −b = 0 \hspace{48pt} (4) $

Therefore,

$\lambda = −2 ({AA}^T)^{−1}(b − A q) \hspace{48pt} (5) $

Substituting this into $(3)$,

$x - q = A^T ({A A}^T)^{-1} (b - A q) \hspace{48pt} (6)$

so that,

$x = q + A^T ({A A}^T)^{-1} (b - A q) \hspace{48pt} (7)$

Finally, from $(6)$, the minimum distance is

$\begin{equation} \begin{split} d_{\text{min}} &= \sqrt{(x - p)^T (x - p)}\\ &= \sqrt{ (b - A q)^T ({A A}^T)^{-T} {A A}^T ({A A}^T)^{-1} (b - A q)} \\ &= \sqrt{ (b - A q )^T ({A A}^T)^{-1} (b - A q)} \hspace{48pt} (8) \end{split} \end{equation}$

It is easy to see that the distance formula in $3D$ with one plane is a special case of $(8)$.