Say I have a design matrix $X\in \mathbb{R}^{m\times n}$ with rows $x^{(i)} \in \mathbb{R}^{n}, i = 1,...,m$ and I also have a data vector $y \in \mathbb{R}^m$. I construct a "local" linear model for some $x \in \mathbb{R}^n$ as follows: First, define, $$ w_i = \exp \Big ( -\|x - x^{(i)}\|^2 \Big ) = \exp \Big (-\sum_{j=1}^n (x_j - x_j^{(i)})^2 \Big ) $$ for $i = 1,...,m$. Then, solve the following weighted least squares problem: $$ \beta^{(x)}:= \arg\min_{\beta} \sum_{i=1}^m w_i \Big ( \langle x^{(i)},\beta \rangle - y_i \Big )^2. $$ The jist of this whole procedure is to choose $\beta^{(x)}$ such that $\langle x, \beta^{(x)} \rangle$ is a prediction that relies mostly on the nearest neighbours of $x$. This is done by giving less weight to $x^{(i)}$ that are very different from $x$.

The real problem:

Now, let's say I believe my model is sparse. This means that only indices in some $\mathcal{S} \subset \{1,...,n\}$ have non-zero coefficients in $\beta^{(x)}$. Moreover, the set of indices can change for different local models, corresponding to different $x$'s, so we really have $$ \mathcal{S}^{(x)} := \{ j \in \{1,...,n\} | \beta^{(x)}_j \neq 0 \}. $$ This set is important, because we wouldn't want the weights $w_i$ to be affected by variables that are not a part of the model. We want to define "locality" as closeness only for the variables that are a part of the model (the variables in $\mathcal{S}^{(x)}$). Thus, we define $$ w^{(x)}_i := \exp \Big ( - \sum_{j \in \mathcal{S}^{(x)}} (x_j -x^{(i)}_j )^2\Big ) $$ and then solve a similar weighted least problem: $$ \beta^{(x)}:= \arg\min_{\beta} \sum_{i=1}^m w^{(x)}_i \Big ( \langle x^{(i)},\beta \rangle - y_i \Big )^2 \text{ subject to } \beta_j = 0, \forall j \not \in \mathcal{S}^{(x)}. $$ So, what we really want is to find $\mathcal{S}^{(x)}$ and $\beta^{(s)}$. We cannot just try to seek $\beta^{(x)}$ because different $\mathcal{S}^{(x)}$ give different least squares problems.

My thoughts:

First thing that comes to mind is some sort of LASSO, but I don't know how to make it work with the weights. Combinatorial search is also an option, albeit not a very tempting one. I believe this might have already been considered by others before me, so any reference would be appreciated.

  • $\begingroup$ I'm not surprised this question got no votes and no answers. But absolutely no views??? For a week??? What am I doing wrong? $\endgroup$
    – Yair Daon
    Commented Jun 28, 2017 at 0:21
  • $\begingroup$ @yairdaon first thing, you are talking to yourself. $\endgroup$
    – Yair Daon
    Commented Jun 29, 2017 at 6:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.