# Choosing set of best estimators for linear least squares

I have a measured experimental dataset which is well approximated by the sum of several basis functions in linear combinations. Linear least squares of course gives me the optimal weight for each basis function. These basis functions are all unrelated and may or may not be correlated (or even repeated). That still doesn't cause any problem when fitting.. least squares is well defined and I always get optimal weights.

My question is about choosing the best subset of these basis functions to represent my data. If I'm allowed to use say only up to 7 of the 20 basis functions I have, how should I pick the 7? I realize I can just use the covariance matrix and cut out rows and columns to solve the fit for any set of 7 I like, but is there an optimal strategy for choosing the best 7 to fit my data? Enumerating all sets of 7 would be expensive (20 choose 7 = 77520) and what happens if I have 100 or 1000 input base functions?

My first thought is to find the one basis function (out of 20) that best approximates the data, and greedily "accept" that one. I then look at the remaining 19 contributors, and take the one that best helps. Repeat 7 times. This seems like a reasonable strategy, but I don't know if it finds the best set of choices, or even if it's efficient.

I haven't found discussion of choosing subsets in such a fit in my linear algebra or multivariate statistics texts, nor Google. This must be a common question, I can think of many examples where you'd use it. (Pick the best 3 weather stations to query to mix to find your local conditions. Or have a table you want to interpolate with several built in functions, and you want to pick at most 5 of them to keep evaluation speed fast. Or have multiple different sources of stock recommendations, and you only have the budget to query a limited set of them...)

Thanks!

-
There is such a thing as stepwise least squares, where you can monitor the coefficient of determination (as well as a bunch of other parameters whose names I'm forgetting) as you keep adding/removing basis functions. –  Ｊ. Ｍ. Aug 4 '11 at 6:07
You might want to look at this for instance... –  Ｊ. Ｍ. Aug 4 '11 at 7:02
You mention that your basis functions may even be repeated, but that this poses no problem for you since least-squares is well defined even in this case. Is that actually true? Are you also doing an $\ell_1$ or $\ell_2$ penalization on the weights? –  Gus Aug 7 '11 at 5:56

These basis functions are all unrelated and may or may not be correlated (or even repeated). That still doesn't cause any problem when fitting.. least squares is well defined and I always get optimal weights.

The optimal least-squares approximation of the target is uniquely defined, but if you have repeated or redundant functions in the basis, the coefficients of the model will not be uniquely defined. This is called "multicollinearity" in the statistics literature.

Parsimonious selection of submodels, even for linear least squares, is an NP-complete problem.

-