# Efficient ways to partition rows of augmented design matrix $[X|y]$ into subsets with similar regression results?

Imagine I have $n$ observations on a regression model; are there any reasonably efficient methods for partitioning that into two (or more) roughly equally sized groups which almost reproduce the overall regression results? (parameter estimates and $s$ in particular, obviously not things like p-values)

One could of course randomly divide points among partitions and in a large sample that should be a pretty good start. One might then consider swapping pairs of points that would bring both "closer" in some sense, but naive approaches to identifying pairs that do so are not very efficient (there's $O(n^2)$ such pairs to consider, let alone working out the effect of swapping them, so anything based on this approach would need to be done in a fairly clever way).

I'm not especially tied to one particular measure of how close the estimates are -- even if one considers the coefficients alone, there's a number of ways to define a measure of closeness; if the variables are on similar scales one might use a sum of squared deviations or absolute deviations for example, or for dissimilar dimensions we might scale for the standard errors before summing squared deviations say; on the other hand some measure more like a kind of Mahalanobis' distance may make sense more generally. Once we bring $s$ in the exercise becomes more involved.

An algorithm that works well for a reasonable choice of "closeness" will probably be of some interest.

If it helps make the problem tractable, feel free to assume simple regression.

I'd be interested in suggestions for approaches, perhaps with some simple analysis, OR references to ways to tackle it (with a brief synopsis), or other useful pointers.

Here's an example of one partition that comes reasonably close on the coefficients (here closeness is a sum of squared deviations when standardized by the overall coefficient se's; I didn't worry about $s$ yet). The data set is the cars data in R (originally from Ezekiel, 1930 [1])

(y) dist:
2  10   4  22  16  10  18  26  34  17  28  14  20  24  28  26  34  34  46
26  36  60  80  20  26  54  32  40  32  40  50  42  56  76  84  36  46  68
32  48  52  56  64  66  54  70  92  93 120  85

(x) speed:
4  4  7  7  8  9 10 10 10 11 11 12 12 12 12 13 13 13 13 14 14 14 14 15 15 15 16 16 17 17
17 18 18 18 18 19 19 19 20 20 20 20 20 22 23 24 24 24 24 25


subsets (row numbers):

set1:
1  4  6  8 12 13 14 19 20 21 23 24 25 26 27 31 34 37 38 40 42 44 45 47 48
set2:
2  3  5  7  9 10 11 15 16 17 18 22 28 29 30 32 33 35 36 39 41 43 46 49 50


Both subsets have fits very close to the original fit:

(black line: full data, red: set1, blue: set2)

This pair of subsets was found by brute force (just randomly divide into two sets until the sum of squares of scaled deviations of coefficients was small for some arbitrary judgement of what "small" was).

I'm curious to identify substantially better approaches than that, and this hasn't yet added in getting $s$ close as well.

[1]: Ezekiel, M. (1930) Methods of Correlation Analysis. Wiley.