Covariance-residual technique for linear regression feature selection When doing forward feature selection for linear regression, there are two different ways one can select the next feature:


*

*Choose the feature which, when selected, will yield the greatest reduction in total squared error.

*Choose the feature whose covariance against the current residuals is furthest from 0.
The concept of forward feature selection is often introduced with 1, but 2 is usually preferred in practice for computational reasons.
Are these two equivalent? I'm looking for a proof or a counterexample.
In other words, is the following true?
$$|(X\beta - y)^Tu| > |(X\beta - y)^Tv| \Leftrightarrow ||X_u\beta_u - y|| < ||X_v\beta_v - y||$$
Here:


*

*$X$ is an $n \times k$ matrix representing the first $k$ features selected

*$y$ is an $n \times 1 $ target

*$\beta$ is the OLS solution to $y \approx X \beta$

*$u$ and $v$ are two $n\times 1$ candidate features

*$X_u$ and $X_v$ are the $n \times (k+1)$ matrices formed by concatenating $X$ with $u$ and $v$, respectively

*$\beta_u$ and $\beta_v$ are the OLS solutions to $y \approx X_u \beta_u$ and $y \approx X_v \beta_v$, respectively.

 A: These algorithms are equivalent, but only if the features are normalized to have unit variance and uncorrelated.


*

*If the feature is normalized, then highest covariance = hightest correlation = highest $R^2$ = lowest MSE in a univariate linear regression of the residuals on the feature.

*If the features are uncorrelated, then regressing $y$ on features $x_1, ...x_k$ and then regressing residuals on feature $x_{k+1}$ would produce the same coefficients as regressing $y$ on features $x_1, ...x_{k+1}$ at once. If coeffitients are the same, then predictions and MSEs are also the same. 


To produce a counterexample, you should violate my restrictions and, for example, make a good feature be correlated with the current prediction - then it will have high predictive power, but relatively low correlation with the current residuals. 
Here is a counterexample in Python, when the first method leads to selection of x1 and x2, but the second method leads to selection of x1 and x3. 
import numpy as np
from sklearn.linear_model import LinearRegression
from sklearn.metrics import mean_squared_error
np.random.seed(1)
n = 10000

# the true process generating Y
f1 = np.random.normal(size=n)
f2 = np.random.normal(size=n)
y = 0.8 * f1 + 0.2 * f2 + np.random.normal(size=n, scale=0.1)

# the observable features
x1 = f1
x2 = 0.6 * f1 + 0.4 * f2
x3 = f2 + np.random.normal(size=n, scale=1)
x = np.column_stack([x1, x2, x3])

# choosing the first feature - it will be the x1, as having the highest correlation with y
for feature in [x1, x2, x3]:
    print(np.corrcoef(y, feature)[0,1])
# 0.96, 0.93 and 0.17 respectively
resid =  y - LinearRegression().fit(x[:,[0]], y).predict(x[:,[0]])

# choose whether to add x2 or x3 next, based on MSE of the new model - x2 wins
for subset in [[0, 1], [0, 2]]:
    print(mean_squared_error(y, LinearRegression().fit(x[:,subset], y).predict(x[:,subset])))
# 0.0099 is R^2 for x2
# 0.0298 is R^2 for x3 - worse , because (x1, x3) gives a noiser representation of (f1, f2) than (x1, x2)
# thus, x2 would be chosen

# choose whether to add x2 or x3 next, based on correlatio with target
for feature in [x2, x3]:
    print(np.corrcoef(resid, feature)[0,1])
# 0.4940 is correlation for x2 - worse, because x2 is a noisier representation of f2 than x3 
# 0.6361 is correlation for x3 
# thus, x3 would be chosen

