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$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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, 2020 at 19:21
  • $\begingroup$ Assuming that the matrix you have is full-rank and skinny, then yes. $\endgroup$
    – user303375
    Dec 15, 2020 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, 2020 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, 2020 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, 2020 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.