2
$\begingroup$

Background: Let $X \in \mathbb{R}^{N\times K}$ and $y \in \mathbb{R}^{N\times 1}$ be data for a regression problem. The aim is to find $\beta \in \mathbb{R}^{K\times 1}$ such that $X\beta \approx y$ in some suitable sense. The ordinary least squares (OLS) solution $\beta_{OLS}$ minimizes $||y - X\beta||_2$ and is given by the solution to the normal equation $$(X^TX)\beta = X^Ty.$$ The complete subset regression (CSR) is computed in the following way: for a fixed $k\in \{1,\ldots,K\}$, find all the subsets of $\{1,\ldots,K\}$ with $k$ elements (there are $n = K!/(k!(K-k)!)$ such subsets). For each subset, run the OLS regression using only the corresponding columns in $X$, yielding $\beta_i$ for the $i$th subset (consider each $\beta_i$ as a point in $\mathbb{R}^{K\times 1}$, with zeros for each element outside the subset). Finally, take the average over all the calculated regression coefficients: $$ \beta_{CSR} = \frac{1}{n}\sum_{i = 1}^{n}\beta_i. $$ Simply performing all these subset regressions can clearly be impractical, if $K$ is large and $k$ is not close to 1 (or $K$), which leads to the

Question: Can $\beta_{CSR} = \frac{1}{n}\sum_{i}\beta_i$ be computed efficiently?

Some calculations: Let $S_i \in \mathbb{R}^{K\times K}$ be a diagonal matrix with $1$s on the diagonal elements corresponding to the $i$th subset, and $0$s otherwise. The normal equation for the $i$th subset regression is then $$ S_i(X^TX)S_i\beta_i = S_iX^Ty.\\ $$ Summing over $i$, we get \begin{eqnarray} \sum_{i = 1}^nS_i(X^TX)S_i\beta_i &=& \sum_{i}S_iX^Ty\\ &=& \left(\sum_{i}S_i\right)X^Ty\\ &=& c X^Ty \end{eqnarray} where the constant $c$ is the number of times each element is included in a subset. Could the left hand side perhaps be written as $M \left(\sum_{i}\beta_i\right)$, for some cleverly constructed matrix $M$?

A simple case that is not so interesting (described on page 4 in the reference below) is when $X^TX$ is a diagonal matrix --- then the left hand side is simply $X^TX \left(\sum_{i}\beta_i\right)$, since $X^TX$ and $S_i$ commutes, and $S_i\beta_i = \beta_i$, so $\beta_{CSR}$ is simply a constant times $\beta_{OLS}$.

Reference: Elliott, Gargano, and Timmermann (2012), "Complete Subset Regressions", see http://rady.ucsd.edu/docs/faculty/timmerman/subset-regression-April-25-2012.pdf.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ You will probably get other comments suggesting, Cross Validated or stats.exchange etc. as the proper place to ask- and it is. I personally have never heard of such a thing, nor is it clear to me why that would be preferable to some 'regularization regression". I would definitely look at "The Elements of Statistical Learning" by Hastie et al. They certainly discuss similar issues. $\endgroup$
    – meh
    Commented Oct 17, 2014 at 23:28
  • 1
    $\begingroup$ @aginensky, CSR is one type of regularized regression, but the question has nothing to do with whether it is preferable to other methods. My question is a pure linear algebra question: can the average of the solutions to a large number of linear equation systems (with lots of structure) be computed efficiently? The kind of answer I was hoping for would probably involve some sort of clever matrix identity. Perhaps the "Background" section was not helpful, I will consider editing the question to not mention the application at all, and phrase it as a completely abstract linear algebra question. $\endgroup$
    – svangen
    Commented Oct 18, 2014 at 20:56
  • $\begingroup$ In many of these issues, "preferable = quicker". If time wasn't an issue, one would simply compute CSR and find what worked best (after checking for overfitting etc, etc). $\endgroup$
    – meh
    Commented Oct 19, 2014 at 1:13

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .