1
$\begingroup$

In Andrew Ng's Machine Learning course lecture 4.6 on "Normal Equation", he says that in order to minimize $J(\theta) = \frac{1}{2m}\sum\limits_{i=1}^{m}({h_{\theta}}(x^{(i)}) - y^{(i)})^2$, where $h_{\theta}(x) = \theta_{0} + \theta_{1}x_1 + \theta_{2}x_2 + ... + \theta_{n}x_n$ and solve for $\theta$, one should take the design matrix $X$ and compute the following expression:

$\theta = (X^{T}X)^{-1}X^{T}y$ ,

where the design matrix is the matrix of all feature vectors $[1, x^{(i)}_{1}, x^{(i)}_{2}, ..., x^{(i)}_{m}]$ as rows. He shows the Octave (Matlab) code for computing it, as pinv(x'*x)*x'*y.

However, long time ago, when I used Numpy to solve the same problem, I just used np.linalg.pinv(x) @ y. It is even stated in Numpy's pinv docs that pinv solves the least squares problem for $Ax=b$, such that $\overline{x} = A^{+}b$.

So why should I compute $\theta = (X^{T}X)^{-1}X^{T}y$ when I can just compute $\theta = X^{-1}y$ ? Is there any difference?


EDIT:

Actually, it is easy to see that $\theta = (X^{T}X)^{-1}X^{T}y$ is right, because by definition,

$(X^{T}X)^{-1}(X^{T}X) = I$,

but thanks to the associative property of matrix multiplication, we can write the same equation as

$((X^{T}X)^{-1})X^{T})X = I$,

such that we get that by multiplying $X$ from the left by $(X^{T}X)^{-1})X^{T}$, we get $I$, meaning that it is its left-inverse matrix. The left-inverse is the matrix that is used for solving the least-squares problem, as multiplying both sides by it from the left turns $X\theta=y$ into $I\theta=(X^TX)^{-1}X^Ty$, meaning that the coefficients are $\theta = (X^TX)^{-1}X^Ty$.

Similarly, the following equation is true by definition,

$(XX^{T})(XX^{T})^{-1} = I$,

which again, thanks to the associative property of matrix multiplication, can be written as

$X(X^{T}(XX^{T})^{-1}) = I$,

So we get that $(X^{T}(XX^{T})^{-1})$ is the right-inverse of $X$.

$\endgroup$
2
$\begingroup$

$X^{-1}$ only makes sense for square matrices. For least-squares problems, we often have a strictly-skinny, full-rank matrix $X$. When $X$ is square and full rank, then you can use $\theta = X^{-1}y$, as $(X^TX)^{-1}X^T = X^{-1}$. But when $X$ is strictly-skinny and full-rank, only the pseudoinverse $(X^TX)^{-1}X^T$ exists, which leads to the formula given in the link.

$\endgroup$
5
  • $\begingroup$ I have used Numpy's pinv on non-squared matrices. Does it mean that on such matrices, numpy automatically uses the longer formula? $\endgroup$ – SomethingSomething Dec 15 '20 at 19:21
  • $\begingroup$ Assuming that the matrix you have is full-rank and skinny, then yes. $\endgroup$ – user303375 Dec 15 '20 at 19:22
  • $\begingroup$ What's the meaning of "skinny"? And what if it isn't full rank? Suppose that I have 100 samples and 10 features, so my matrix's dimension is 100x10 $\endgroup$ – SomethingSomething Dec 15 '20 at 19:25
  • 1
    $\begingroup$ If you have an $n \times m$ matrix $X$, then it is skinny when $n \geq m$ and strictly-skinny when $n > m$. So in your example, yes, the matrix is skinny. If $X$ is not full rank, then you would need to use the SVD of $X$ to compute the pseudoinverse. In a design matrix, you likely will not have a case when $X$ is not full rank, unless you have features that are linear combinations of each other. $\endgroup$ – user303375 Dec 15 '20 at 19:32
  • 1
    $\begingroup$ To give an example, say you are predicting housing prices and you have features $x_1$ and $x_2$, where $x_1$ is the number of rooms you have in the home, and $x_2$ is the number of rooms you have in the home times 4. The design matrix that you construct from your observations will certainly not be full rank, as the second row will always be 4 times the first. $\endgroup$ – user303375 Dec 15 '20 at 19:36

Your Answer

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

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