# Linear regression when you only know $X^t Y$, not $Y$ directly

Suppose $X\beta =Y$.

We don't know $Y$ exactly, only its correlation with each predictor, $X^\mathrm{t}Y$.

The ordinary least-squares (OLS) solution is $\beta=(X^\mathrm{t} X)^{-1} X^\mathrm{t}Y$ and there isn't a problem.

But suppose $X^\mathrm{t}X$ is near singular (multicollinearity), and you need to estimate the optimal ridge parameter. All the methods seems to need the exact values of $Y$.

Is there an alternative method when only $X^\mathrm{t}Y$ is known?

• interesting question. Perhaps some sort of EM algorithm would work... – probabilityislogic Jun 8 '12 at 8:14
• I don't understand, can't you use cross-validation for estimating the optimal ridge parameter? – Pardis Jun 8 '12 at 14:00
• @Pardis: No loss function is given in the question so we don't know what optimal means. Can you see the trouble we run into if the loss function is the MSE? – cardinal Jun 8 '12 at 14:08
• @JohnSmith: You are alluding to the point I was driving at. There is no indication of how to measure "optimality". What you are effectively doing is introducing a different metric (distance function) to measure "quality" of prediction or fit. We need more details from the OP in order to get very far, I suspect. – cardinal Jun 8 '12 at 18:50
• @Pardis: Finding the estimates is not the problem, as you note. :) However, if you decide to do crossvalidation, how are you going to estimate the out-of-sample MSE, i.e., on the left-out fold for each iteration? :) – cardinal Jun 8 '12 at 18:57

This is an interesting question. Surprisingly, it is possible to do something under certain assumptions, but there is a potential loss of information about the residual variance. It depends upon $X$ how much is lost.

Let's consider the following singular value decomposition $\newcommand{\t}{^\mathrm{t}}X = UDV\t$ of $X$ with $U$ an $n \times p$ matrix with orthonormal columns, $D$ a diagonal matrix with positive singular values $d_1 \geq d_2 \geq ... \geq d_p > 0$ in the diagonal and $V$ a $p \times p$ orthogonal matrix. Then the columns of $U$ form an orthonormal basis for the column space of $X$ and $$Z = U\t Y = D^{-1} V\t V D U\t Y = D^{-1} V\t X\t Y$$ is the vector of coefficients for the projection of $Y$ onto this column space when expanded in the $U$-column basis. From the formula we see that $Z$ is computable from knowledge of $X$ and $X\t Y$ only.

Since the ridge regression predictor for a given $\lambda$ can be computed as $$\hat{Y} = X(X\t X + \lambda I)^{-1} X\t Y = U D(D^2 + \lambda I)^{-1} D U\t Y = U D(D^2 + \lambda I)^{-1} D Z$$ we see that the coefficients for the ridge regression predictor in the $U$-column basis are $$\hat{Z} = D (D^2 + \lambda I)^{-1} D Z.$$ Now we make the distributional assumption that $Y$ has $n$-dimensional mean $\xi$ and covariance matrix $\sigma^2 I_n$. Then $Z$ has $p$-dimensional mean $U\t \xi$ and covariance matrix $\sigma^2 I_p$. If we imagine an independent $Y^{\text{New}}$ with the same distribution as $Y$ (everything conditionally on $X$ from hereon) the corresponding $Z^{\text{New}} = U\t Y^{\text{New}}$ has the same distribution as $Z$ and is independent and \begin{eqnarray*} E ||Y^{\text{New}} - \hat{Y}||^2 &= & E || Y^{\text{New}} - U Z^{\text{New}} + U Z^{\text{New}} - U \hat{Z} ||^2 \\ & = & E || Y^{\text{New}} - U Z^{\text{New}}||^2 + E||U Z^{\text{New}} - U \hat{Z} ||^2 \\ & = & \text{Err}_0 + E||Z^{\text{New}} - \hat{Z} ||^2. \end{eqnarray*} Here the third equality follows by orthogonality of $Y^{\text{New}} - U Z^{\text{New}}$ and $U Z^{\text{New}} - U \hat{Z}$ and the fourth by the fact that $U$ has orthonormal columns. The quantity $\text{Err}_0$ is an error that we cannot get any information about, but it does not depend upon $\lambda$ either. To minimize the prediction error on the left hand side we have to minimize the second term on the right hand side.

By a standard computation \begin{eqnarray*} E||Z^{\text{New}} - \hat{Z} ||^2 &= & E||Z - \hat{Z}||^2 + 2 \sum_{i=1}^p \text{cov}(Z_i, \hat{Z}_i) \\ & = & E||Z - \hat{Z}||^2 + 2 \sigma^2 \underbrace{\sum_{i=1}^p \frac{d_i^2}{d_i^2 + \lambda}}_{\text{df}(\lambda)}. \end{eqnarray*} Here $\text{df}(\lambda)$ is known as the effective degrees of freedom for ridge regression with parameter $\lambda$. An unbiased estimator of $E||Z - \hat{Z}||^2$ is $$\text{err}(\lambda) = ||Z - \hat{Z}||^2 = \sum_{i=1}^p \left(1 - \frac{d_i^2}{d_i^2 + \lambda}\right)^2 Z_i^2.$$

We combine this with the (unbiased) estimator $$\text{err}(\lambda) + 2 \sigma^2 \text{df}(\lambda)$$ of $E||Z^{\text{New}} - \hat{Z} ||^2$ given that we know $\sigma^2$, which we then need to minimize. Obviously, this can only be done if we know $\sigma^2$ or have a reasonable guess at or estimator of $\sigma^2$.

Estimating $\sigma^2$ can be more problematic. It is possible to show that $$E||Z - \hat{Z}||^2 = \sigma^2\left(p - \underbrace{\sum_{i=1}^p \frac{d_i^2}{d_i^2 + \lambda}\left(2 - \frac{d_i^2}{d_i^2 + \lambda}\right)}_{\text{d}(\lambda)}\right) + \text{bias}(\lambda)^2.$$ Thus if it is possible to choose $\lambda$ so small that the squared bias can be ignored we can try to estimate $\sigma^2$ as $$\hat{\sigma}^2 = \frac{1}{p-\text{d}(\lambda)} ||Z - \hat{Z}||^2.$$ If this will work depends a lot on $X$.

For some details see Section 3.4.1 and Chapter 7 in ESL or perhaps even better Chapter 2 in GAM.

Define $β$ as in the question and $β(λ,K)=[(X^TX)_{KK}+λI]^{−1}(X^TY)_K$ for various parameters $\lambda$ and sets $K$ of sample labels. Then $e(λ,K):=\|Xβ(λ,K)-Y\|^2-\|Xβ-Y\|^2$ is computable since the unknown $\|Y\|^2$ drops out when expanding both norms.

This leads to the following algorithm:

• Compute the $e(λ,K)$ for some choices of the training set $K$.
• Plot the results as a function of $\lambda$.
• Accept a value of $\lambda$ where the plot is flattest.
• Use $β^*=[X^TX+λI]^{−1}X^TY$ as the final estimate.
• I'm guessing "where the plot is flattest" will be at $\lambda$ very small, like roughly 0 :) – jbowman Jun 10 '12 at 17:07
• @jbowman: This will happen only if the problem is well-conditioned and needs no regularization, then $\lambda=0$ is indeed adequate. In the ill-conditioned case, the prediction of the items outside $K$ will be poor because of overfitting, and $e(\lambda,K)$ will therefore be large. – Arnold Neumaier Jun 11 '12 at 8:41
• @ArnoldNeumaier: $(X^TY)_K$ isn't computable. We only know the correlation with each predictor. $(X^TY)$ is in the "predictor domain", not in the "Y domain" (If N is the sample size and p the number of predictors, we only have p values, one for each predictor). – Jag Jun 11 '12 at 9:25
• @Jag: Then there is not enough information for selecting $\lambda$. But $X^TY$ must have been collected somehow. If during its collection you partition the sample into $k$ batches and assemble the $X^TY$ separately for each batch then one can reserve one batch each for cross validation. – Arnold Neumaier Jun 11 '12 at 11:19
• @ArnoldNeumaier: $X^TY$ are externally given, don't collected. – Jag Jun 11 '12 at 12:32