13
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ interesting question. Perhaps some sort of EM algorithm would work... $\endgroup$ – probabilityislogic Jun 8 '12 at 8:14
  • $\begingroup$ I don't understand, can't you use cross-validation for estimating the optimal ridge parameter? $\endgroup$ – Pardis Jun 8 '12 at 14:00
  • $\begingroup$ @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? $\endgroup$ – cardinal Jun 8 '12 at 14:08
  • 1
    $\begingroup$ @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. $\endgroup$ – cardinal Jun 8 '12 at 18:50
  • 1
    $\begingroup$ @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? :) $\endgroup$ – cardinal Jun 8 '12 at 18:57
8
$\begingroup$

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.

Improve this answer
$\endgroup$
-1
$\begingroup$

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.
Improve this answer
$\endgroup$
  • 1
    $\begingroup$ I'm guessing "where the plot is flattest" will be at $\lambda$ very small, like roughly 0 :) $\endgroup$ – jbowman Jun 10 '12 at 17:07
  • $\begingroup$ @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. $\endgroup$ – Arnold Neumaier Jun 11 '12 at 8:41
  • 3
    $\begingroup$ @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). $\endgroup$ – Jag Jun 11 '12 at 9:25
  • $\begingroup$ @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. $\endgroup$ – Arnold Neumaier Jun 11 '12 at 11:19
  • $\begingroup$ @ArnoldNeumaier: $X^TY$ are externally given, don't collected. $\endgroup$ – Jag Jun 11 '12 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.