3
$\begingroup$

Given is a linear regression problem, where we have one training point, which is 1-dimensional: $x \in R_{>0}$ and the corresponding output, $y \in R$. We duplicate the feature, such that we have one training point with two (identical) features.

For this, we have to determine if we can apply the closed form solution $\beta = (X^TX)^-1*X^T*y$. Then we have to solve the linear regression problem by taking into account that $f(X) = ||y-X*\beta||^2$ is convex.

  • Application of the closed form solution: For this I want to determine if $X^TX$ has full rank. Given is $X = (1,x_{11},x_{12})$. Hence $X^T*X$ results in:

    \begin{bmatrix} 1 & x_{11} & x_{12} \\ x_{11} & x_{11}^2 & x_{11}x_{12} \\ x_{12} & x_{11}x_{12} & x_{12}^2 \end{bmatrix}

This matrix seems to have full rank (independent column vectors), so the closed form solution is applicable. Correct? Is there another way to determine the rank without explicitly calculating $X*X^T$?

  • For minimizing $f(\beta)$ I would derive $||y-X*\beta||^2$ and set it equal to zero.
$\endgroup$
  • 3
    $\begingroup$ Since the rank of $X$ is $1$, it's impossible for $X^\prime X$ to have a larger rank than that. Indeed, the rank of $X^\prime X$ is $1$, too, as you can confirm by observing that the second row is $x_{11}$ times the first row (after correcting the error in the $2,3$ entry) and the third row is $x_{12}$ times the first row. $\endgroup$ – whuber Jul 26 '17 at 18:25
  • $\begingroup$ Corrected, and see it now! So in general, rank(X'X) <= rank(X)? I did not know about that, also in the exercise we were asked to answer the question if the closed form can be used by determining the rank of (X'X)! $\endgroup$ – TestGuest Jul 26 '17 at 19:31
  • 1
    $\begingroup$ See stats.stackexchange.com/questions/60622 for more about matrix ranks. $\endgroup$ – whuber Jul 26 '17 at 19:33
  • 1
    $\begingroup$ It's problematic. First, your objective is a function of $\beta$, not $X$. Second, it's easy to minimize $f(\beta) = ||y - X\beta||^2$ directly. Note that this is not a "linear equation." $\endgroup$ – whuber Jul 26 '17 at 20:56
  • 1
    $\begingroup$ It wasn't evident you had approached it like that, for two reasons. (1) You wrote "$f(X)$" rather than $f(\beta)$ and (2) you did not correctly take the derivative with respect to $\beta$. The result will be a vector and it will involve $y$ as well as $X$ and $\beta$. $\endgroup$ – whuber Jul 26 '17 at 21:02
5
$\begingroup$

There are some incorrect statements in your question.

(Notation note: I'll use bold letters to denote vectors.)

Let $\mathbf{b}$ be a coefficient vector we're trying to estimate. The ordinary least squares problem is:

\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $\mathbf{b}$)} & \sum_{i=1}^n \epsilon_i^2 \\ \mbox{subject to} & y_i = \mathbf{x}_i \cdot \mathbf{b} + \epsilon_i \end{array} \end{equation}

This can be rewritten in matrix notation as:

\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $\mathbf{b}$)} & \left(\mathbf{y} - X \mathbf{b}\right)'\left(\mathbf{y} - X \mathbf{b}\right) \end{array} \end{equation}

This is an unconstrained, convex optimization problem, and gradient being equal to zero is a necessary and sufficient condition for an optimum. You can show the first order condition is:

$$(X'X) \mathbf{b} = X'\mathbf{y} $$

Any $\mathbf{b}$ that satisfies that equation will be an optimum. In the case where $X'X$ is full rank, $X'X$ can be inverted to obtain the unique solution:

$$ \mathbf{b} = (X'X)^{-1}X' \mathbf{y}$$

If $X'X$ is not full rank, then you cannot use that formula! In this case, there isn't a unique solution. Instead, there is a linear subspace of solutions that yield a sum of squares of zero.

Other notes:

  • $\operatorname{Rank}(X) = \operatorname{Rank}(X'X)$. See here.
  • The case where $X'X$ is rank deficient or close to rank deficient is known as multicollinearity.

How I interpret the first part of your question?

Given is a linear regression problem, where we have one training point, which is 1-dimensional: $x \in \mathbb{R} $ and the corresponding output, $ y \in \mathbb{R}$. We duplicate the feature, such that we have one training point with two (identical) features.

I interpret this as if you have one training observation $(y, x, x)$. It doesn't even say that an intercept is included, and for simplicity, I won't include one. The design matrix is: $$ X = \begin{bmatrix} x & x \end{bmatrix}$$

This is obviously rank 1. Hence $X'X$ is also rank one because $\operatorname{Rank}(X) = \operatorname{Rank}(X'X)$.

$$ X'X = \begin{bmatrix}x^2 & x^2 \\ x^2 & x^2 \end{bmatrix}$$ That matrix has one linearly independent row or column. The matrix is not invertible.

Any vector $\mathbf{b}$ which solves: $$ \begin{bmatrix} x^2 & x^2 \\ x^2 & x^2\end{bmatrix} \begin{bmatrix} b_1 \\ b_2 \end{bmatrix} = \begin{bmatrix} xy \\ xy \end{bmatrix} $$ will gives a solution. So as long as $b_1 + b_2 = \frac{y}{x}$, the sum of squared error will be zero.

$\endgroup$
  • $\begingroup$ Thank you. I corrected the mistake in the matrix above now. However, how exactly can I now proceed to find the solution(s), as I now see that the closed form to determine $\textbf{b}$ can not be used? The task is in particular as follows: "Solve the linear regression problem for the set of data described in the introduction. Note that the objective f(β) is convex, so that a point β is an optimum if and only if the gradient ∇f(β) is equal to zero. How many solutions do you get?" I understand that convexity means local extrama = global extrema, is my approach with derivation wrong then...? $\endgroup$ – TestGuest Jul 26 '17 at 19:37
  • 1
    $\begingroup$ @TestGuest It's not clear to me that you are carefully distinguishing what's a scalar, what's a vector, and how calculus rules work with matrices and vectors. This matrix cookbook is a useful resource and perhaps you could watch this Youtube video. $\endgroup$ – Matthew Gunn Jul 27 '17 at 3:26
  • $\begingroup$ Corrected the formalism, watched the video. Thank you! As I understand in my specific context, y is just a scalar. I have a follow-up question to the exact same setting where we add a regularizer - can I ask you for a feedback on that one as well? I am shortly going to post it $\endgroup$ – TestGuest Jul 27 '17 at 8:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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