# What properties does a set of data has to have in order to apply matrix multiplication method to find the optimal regression line using least square?

In the problem of linear regression, we are given $$n$$ observations $$\{ (x_1, y_1),\dots,(x_n, y_n)\}$$, where each input $$x_i$$ is a $$d$$-dimensional vector. Our goal is to estimate a linear predictor $$f(.)$$ which predicts $$y$$ given $$x$$ according to the formula $$$$f(x) = x^\top\boldsymbol{\theta},$$$$ Let $${\bf y} = [y_1, y_2 \dots y_n]^\top$$ be the $$n \times 1$$ vector of outputs and $${\bf X} = [x_1, x_2, \dots x_n]^\top$$ be the $$n \times d$$ matrix of inputs. One possible way to estimate the parameter $$\boldsymbol{\theta}$$ is through minimization of the sum of squares. This is the least squares estimator: $$$$argmin_{\boldsymbol{\theta}} \ \lVert {\bf y} - {\bf X}\boldsymbol{\theta} \rVert_2^2. \label{eq:LS_q3}$$$$

So the optimal value of $$\theta$$ for this cost function is $$\theta=(X^TX)^{-1}X^Ty$$. SO we need the matrix $$X^TX$$ to be invertible. What does this mean in terms of the data itself?

My thought was it has to do with covariance matrix somehow, but I'm not exactly sure.

• We don't need $X^\prime X$ to be invertible to find this minimum: one always exists. Invertibility of $X^\prime X$ is related to the covariance matrix only when a nonzero constant vector is contained in the span of the columns of $X.$
– whuber
Oct 15, 2019 at 13:45
• I know we could use gradient decent to find the minimum, but suppose we were to compute the minimum using the above matrix multiplication method, what assumption we have to have on the data? Oct 15, 2019 at 13:52
• Nothing at all, provided you either (a) solve the Normal equations $X^\prime X\theta=X^\prime y$ directly or (b) use generalized inverses to obtain a solution.
– whuber
Oct 15, 2019 at 13:56
• Ok cool, I’ll let my prof know... but suppose I just want find inverse of $X^TX$, what assumption do we have to have on the data? We need $X^TX$ to have no zero determinant. This is true if and only if X has no zero determinant. So The columns or the rows of X have to be linearly independent right? But in terms of properties of date what does this mean? Oct 15, 2019 at 14:07
• I don't understand what you mean by "properties of date." If you mean data, it's unclear what one might add to your (correct) characterizations of $X.$
– whuber
Oct 15, 2019 at 14:15

First, it is not quite true that you need $$X^TX$$ to be invertible in order to get the OLS estimate. It is possible to use a generalized inverse $$(X^TX)^-$$ and write $$\hat\beta = (X^TX)^-X^Ty$$.
If, however, you want to use the usual inverse and require $$X^TX$$ to be invertible, then this is a matter of the linear algebra. Consider some properties of invertible matrices. One such property is that the matrix has full rank. In order $$X^TX$$ to have full rank, $$X$$ itself must have full rank. This means that the columns of $$X$$ are linearly independent: that is, no linear combination of columns of $$X$$ can give another column of $$X$$, unless that linear combination has all weights as zero (the "trivial solution"). Note that this is stronger than just saying that no column of $$X$$ is a scalar multiple of another. If two columns of $$X$$ add up to a third column of $$X$$, for instance, then $$X$$ lacks full rank.
This is synonymous with saying that your data (including the intercept column of all $$1$$s, if you include it) cannot exhibit perfect multicollinearity if $$X^TX$$ is to be invertible.