From: Dave Rusin <rusin@math.niu.edu>
Subject: Re:  Distance between point and subroom
Date: Thu, 6 Jan 2000 14:52:40 -0600 (CST)
To: Klaus.vonSengbusch@post.rwth-aachen.de
Summary: Minimal distance from point to subspace

>subroom (I hope this is the correct word in english)
subspace ('Raum'='space')

This is actually very easy. Treat the rows of  A  as vectors in  R^100.
Replace with linear combinations as necessary to assume that the rows
form an orthonormal set. Complete to get a basis for  R^100. In this
basis we may write  p = Sum( p_i v_i )  where the  p_i  are numbers and
the  v_i  are the orthonormal basis vectors. Likewise the vector you
seek is  x = Sum( x_i v_i ) for some unknown numbers  x_i. Now, the
point of all this basis change is just that the subspace  A x = y  is
just the set of vectors with  x_1 = y_1,  x_2 = y_2,  and the other
coordinates   x_i  arbitrary. That is, in this coordinate system, the
subspace is "flat". Clearly the closest point on such a subspace  to the
point  p  is the point directly "beneath"  p, that is, it's the point
with (x_1 = y_1,  x_2 = y_2,  and)  x_i = p_i  for all the other  i.

Fortunately you can compute this point without needing to carry out
any of these calculations. We go "down" from  p  to the subspace by
subtracting  (p1-y1)v1+(p2-y2)v2, which is the only vector in the span
of the rows of  A  for which the difference from  p  lies in the subspace.
That is, we only need those two coefficients  w1=p1-y1  and  w2=p2-y2,
which are characterized by the matrix equation  A (p - A' w) = y, i.e.
you need only solve the  2x2 matrix equation  (A A') w = (A p - y);
the point you seek is then  p - A' w. The square of the distance from  p  
to this point is just  (A' w )' (A' w ) = w' (A A') w = w' (A p - y ).

This works with any number of equations in any number of unknowns. You
may have seen such a formula for finding the point on a line (in the plane)
closest to a given point  p: if the line is  ax+by+c=0  then the point we seek
is  (p1, p2) - ( (a p1 + b p2 + c)/(a^2+b^2) )*(a, b).

This is not an appropriate post for sci.math.research, though.
dave (moderator)

[boilerplate deleted --djr]

Your post:

Hi,

I'm am looking for an algorithm to calculate the smallest distance between a
point p and a subroom (I hope this is the correct word in english) described
by Ax=y.
A: Matrix with 100 columns and 2 rows
x:  unknown vector with 100 elements
y:  known vector with 2 elements
p:  known vector with 100 elements

Any help would be greatly appreciated.

Klaus