Linear Regression - Data Subset with Lowest Mean-Squared Error? Short version: given a linear regression dataset and an integer $K$, what data subset of size $K$ results in linear parameters with the lowest mean squared error on the entire dataset?
Long version: Suppose I have a supervised dataset $D_n := \{x_n, y_n\}_{n=1}^N$ and I want to perform ordinary linear regression by minimizing
$$ L_{OLS, N}(w) = ||Y_N - X_N w||_2^2$$
where $Y_N$ is the matrix formed by stacking $y_n$ as row vectors and $X_N$ is the matrix formed by stacking $x_n$ as row vectors. I use the subscript $N$ to remind us that we used all the data to compute the parameter estimates.  Alternatively, I might want to perform ridge linear regression by minimizing
$$ L_{Ridge, N}(w) = ||Y_N - X_N w||_2^2 + c ||w||_2^2$$
We know that the parameters that minimize the above losses are given by
$$w_{OLS, N} = (X_N^T X_N)^{-1} X_N^T Y_N$$
$$w_{Ridge, N} = (X_N^T X_N + c I)^{-1} X_N^T Y_N$$
What I'm curious to know is: if we're  forced to choose a subset of only $K < N$ data $D_K := \{(x_k, y_k)\}_{k=1}^K \subset D_N$ and we fit parameters
$$w_{OLS, K} = (X_K^T X_K)^{-1} X_K^T Y_K$$
$$w_{Ridge, K} = (X_K^T X_K + c I)^{-1} X_K^T Y_K$$
what subset of $K$ data results in parameters $w_{OLS, K}$ and $w_{Ridge, K}$ such that $L_{OLS, N}(w)$ and $L_{Ridge, N}(w)$ (respectively) are minimized?

the squared error of the full data set are: $$SSE=\varepsilon'\varepsilon$$where $\varepsilon=Y-X\hat\beta_K$ and $\hat\beta_K=(X_K'X_K)^{-1}X'_KY_K$
You want to minimize SSE wrt a subset K. Unfortunately the only way to do it is through trying all combinations of K-subsets. It's $\frac{N!}{K!(N-K)!}$, which is a lot of work to say the least.
