Reducing the computational requirement of the orthogonal least squares algorithm

The orthogonal, least squares (OLS) algorithm is an efficient implementation of the forward regression procedure for subset model selection. The ability to find good subset parameters with only linear increase in computational complexity makes this method attractive for practical implementations. We examine the computation requirement of the OLS algorithm to reduce a model of K terms to a subset model of R terms when the number of training data available is N. We show that in the case where N≫K, we can reduce the computation requirement by introducing an unitary transformation on the problem