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$ – user24544 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
4
$\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$ – user24544 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$ – user24544 Jul 27 '17 at 8:50

Your Answer

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