3
$\begingroup$

In the matrix form of least squares , the inverse of ( X transpose X ) we are calculating . So, what if that matrix does not posses inverse properties. I mean what if it is not invertible ? Sorry if the question is dumb .

$\endgroup$
5
  • 1
    $\begingroup$ Can you give an example? $\endgroup$ – 5xum May 13 '15 at 11:52
  • $\begingroup$ @5xum - Example. Man I am not so high into Linear algebra. But , what i am wondering like , what if there a matrix X for which calculating inverse (X transpose X) is impossible. Simply , what if X is not invertible ? That means, we cannot apply Least square matrix form equation to solve it. right ? $\endgroup$ – Sarath R Nair May 13 '15 at 12:08
  • $\begingroup$ If $X^TX$ is not invertible, the least squares solution is not unique; there is an infinite number of solutions minimizing the (Euclidean) norm of the residual. Anyway, among them, there is always a unique solution having the minimal norm, which is provided by the Moore-Penrose pseudoinverse. $\endgroup$ – Algebraic Pavel May 13 '15 at 12:16
  • $\begingroup$ @AlgebraicPavel - Exactly. This was I looking for. So, the positive definite property will also come into consideration here right ? $\endgroup$ – Sarath R Nair May 13 '15 at 12:24
  • $\begingroup$ I'm not really sure what you mean. $\endgroup$ – Algebraic Pavel May 13 '15 at 12:41
0
$\begingroup$

Start with the linear system $$ \mathbf{A}x = b $$ with $$ \mathbf{A} \in \mathbb{C}^{m\times n}_{\rho}, \quad x \in \mathbb{C}^{n}, \quad b \in \mathbb{C}^{m}. $$ If the data vector $b$ is in the image of $\mathbf{A}$, then there is a solution vector $x$ such that $$ \mathbf{A}x - b = 0. $$ If the data vector $b$ has a nullspace component, we can not get an exact answer, and instead ask for the best answer.

Choosing the $2-$norm, the least squares minimizers are defined as $$ x_{LS} = \left\{ x\in\mathbb{C}^{n} \colon \lVert \mathbf{A} x_{LS} - b \rVert_{2}^{2} \text{ is minimized} \right\}. $$ Every matrix has a singular value decomposition $$ \mathbf{A} = \mathbf{U}\, \Sigma\, \mathbf{V}^{*} $$ which allows us to express the Moore-Penrose pseudoinverse $$ \mathbf{A}^{\dagger} = \mathbf{V}\, \Sigma^{\dagger}\, \mathbf{U}^{*} $$ which can be used to pose the general solution to the least squares problem: $$ x_{LS} = \mathbf{A}^{\dagger} b + \left( \mathbf{I}_{n} - \mathbf{A}^{\dagger}\mathbf{A} \right) y, \quad y\in\mathbb{C}^{n} $$ The geometry of the solution is discussed in Is the unique least norm solution to Ax=b the orthogonal projection of b onto R(A)?

More on the SVD here: How does the SVD solve the least squares problem?

When the classic inverse exists, it is the pseudoinverse. In this case, there are no nullspace components and $\Sigma=\mathbf{S}$ and we can see that $$ \begin{align} % \mathbf{A}\mathbf{A}^{-1} &= \mathbf{A}\mathbf{A}^{\dagger} = \left( \mathbf{V}\, \mathbf{S}\, \mathbf{U}^{*}\right) \left( \mathbf{U}\, \mathbf{S}^{-1}\, \mathbf{V}^{*}\right) = \mathbf{I} \\ % \mathbf{A}^{-1}\mathbf{A} &= \mathbf{A}^{\dagger}\mathbf{A} = \left( \mathbf{U}\, \mathbf{S}^{-1}\, \mathbf{V}^{*}\right) \left( \mathbf{V}\, \mathbf{S}\, \mathbf{U}^{*}\right) = \mathbf{I} % \end{align} $$

The normal equations solution is discussed here: Difference between orthogonal projection and least squares solution

Additional discussion here: Least squares and pseudo-inverse

$\endgroup$

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.