Linear algebra algorithm

[Cogman]

Ok, first off, I have never taken linear algebra (still in college) so keep in mind that my only exposure the matrices has been from the lasts days in calc class where they basically say "Oh, and btw, this is a matrix!".

So here is the problem. I have a matrix of weighted points, we can call that M. and a function that given two point coordinates will give the weighted distance (it is a non-euclidean distance measurement). With this data, I need to be able to find a set of points such that for that set size, each point not contained in the set is at a minimum distance to its closest set point.

Right now, I'm just doing a Monte Carlo simulation where I just keep taking random points from the matrix, calculate their average distance, and repeat, saving off the best one. This works, but It would be nice to have an absolute answer (in a relatively short amount of time).

Brute force is out of the question. I could do up to 4 with a brute force approach, after that, with 5 it would take days. (I need to be able to do up to 20 points).

Now here is where the linear algebra comes in. I was told that this problem could be solved using a least squares approach (or a non-linear least squares) However, I am having a tough time actually understand least squares, and also seeing how it would give me the best answer in a relatively short amount of time (Hours of processing power is acceptable, days is not).

So any help would be much appreciated!

[tabstop]

Fortunately, least squares is more calculus and less linear algebra. The idea is you have a function to minimize, call it d(x). (It could be your distance, or some monotonic function of your distance -- when using Euclidean distance, it's almost always distance-squared to get rid of the square roots, hence the name.) Find d'(x), set it equal to 0 'cause that's where your minimum is, and there you go.

I don't know how your weights are involved, nor is it clear what you mean by "each point not contained in the set is at a minimum distance to its closest set point". Compared to what? (After all, if the point was in the set, the distance from that point to a set point would be 0, which is clearly smaller than whatever you're going to get from your distance function.)

[Cogman]

The weight for each point is just multiplied by the distance (the points represent a population). So, if a had a point (1, 2) and the closes point in the set to it was (2, 1). I would calculate the distance d(x) for it, and then mulitply d(x) * the weight at (1, 2). If the set falls on the point, then the distance is 0. So, if we had a point in the set for ever point on the matrix with a weight > 0, then the mean offset would be 0.

However, since that is not feasible for this problem, I need to minimize the mean offset as much as possible. So basically, I would be taking every point and calculate the d(x) to the nearest point in the set, multiply that by the weight on the point (not the point in the set), and add it to a total distance. Then I take that total distance and divide by the total population to get my mean offset. (I hope that made sense, I'm probably using incorrect terms )

I don't know if it is possible to just produce a function that determines what distance a given set of points will give, the problem is that I have a lot of points, and they weren't generated, it is real measured data. And there is a lot of it (the population is over 1500). (ok, I lie, it is possible, because I already have it but I'm not quite sure how to go about taking the derivative of a summation, or a matrix for that matter.)

Hopefully what I'm after is a little clearer (and thanks for the help!)

[m37h0d]

there's nothing special about a derivatives of summations or a matrices.

a summation is just a series of additions, and there are no special rules for derivatives of added terms, the derivative of the summation is the summation of the derivatives of the summed terms.

same deal with matrices, each element of the matrix is differentiated independently.