Closed form and gradient calculation for linear regression

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.
• 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.
– whuber
Jul 26, 2017 at 18:25
• 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)!
– user24544
Jul 26, 2017 at 19:31
• See stats.stackexchange.com/questions/60622 for more about matrix ranks.
– whuber
Jul 26, 2017 at 19:33
• 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."
– whuber
Jul 26, 2017 at 20:56
• 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$.
– whuber
Jul 26, 2017 at 21:02

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{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}$$

This can be rewritten in matrix notation as:

$$\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}$$

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.

• 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...?
– user24544
Jul 26, 2017 at 19:37
• @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. Jul 27, 2017 at 3:26
• 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
– user24544
Jul 27, 2017 at 8:50