0
$\begingroup$

I want to solve a least squares problem in the form of $\mathbf{A}\vec{x}=\vec{b}$, where $\mathbf{A}$ is a $m\times n$ matrix asociated to the transformation $T:\mathbb{R}^n \to \mathbb{R}^m$; and where $\vec{b} \notin C(\mathbf{A})$, menaing that there is no immediate solution for $\vec{x}$.

Even though $\mathbf{A}\vec{x}=\vec{b}$ has no solution, I know I can estimate the $\hat{\vec{x}}$ that would minimize the error, and that after some algebra (sorry, I have no reference at hand), it can be expressed as:

$$\mathbf{A}^{\intercal}\mathbf{A}\hat{\vec{x}} = \mathbf{A}^{\intercal}\mathbf{b}$$ My problem is that all text books I have come across stop here. THey state that the new formulation of the problem have a solution (that, I understand), but they say nothing about solving for $\hat{\vec{x}}$. Typically I would go about and solve like this:

$$\hat{\vec{x}} = (\mathbf{A}^{\intercal}\mathbf{A})^{-1}\mathbf{A}^{\intercal}\mathbf{b}$$

However, this requires that $\mathbf{A}^{\intercal}\mathbf{A}$ be invertible.

Question: is $\mathbf{A}^{\intercal}\mathbf{A}$ always invertible? If so, how can I prove it?


Edit: for the particular case I'm interested in, $\mathbf{A}$ has more rows than columns, as it comes from an over-determined system.

Edit 2: I have also checked the formulation of my problem. All columns are linearly independent, meaning that for my particular case, $\mathbf{A}$ has full rank.

$\endgroup$
  • $\begingroup$ It cannot be always invertible, one can see it considering, e.g., the zero matrix. But that is usually not the matrix in the problems. Nonetheless, it does not have to be invertible. If, however, $A$ has a full column rank, then the matrix $A^TA$ is regular and hence invertible. $\endgroup$ – michalOut Oct 31 '18 at 17:01
  • $\begingroup$ Also, are you interested in the topic from the actual computational point of view or just theoretically? The answers will be very different depending on this. $\endgroup$ – michalOut Oct 31 '18 at 17:04
  • $\begingroup$ Actually both: theory and implementation. For the later I know about the Chebyshev decomposition (although it still requires for the matrix to be invertible, right?). The thing is, I'm trying to solve and over-determined system for an engineering problem, yet seek a formal explanation of what I'm doing :) $\endgroup$ – andresgongora Oct 31 '18 at 17:10
  • 1
    $\begingroup$ The equation $A^\top Ax=A^\top b$ is known as the "normal equations". When A is fat, for example in your case, $A^\top A$ is not invertible and $A$ has a nontrivial nullspace. In this case, typically, people look for the simplest solution for $x$, for instance the sparest $x$. This leads to Basis Pursuit or LASSO problem. $\endgroup$ – abolfazl Oct 31 '18 at 19:31
  • 1
    $\begingroup$ Oh, OK. In that case, your problem is easier. If $A$ is full rank, i.e. its rank is equal to number of its columns (in other words, the columns are linearly independent), the solution $A^\top A$ is invertible. If $A$ is not full rank, the problem is ill-conditioned and the solution is not unique. In this case, you should again use regularization terms to specify what kind of solutions you are looking for. I think this link will be usefull: www2.aueb.gr/users/douros/docs_master/Least_Square_pr.pdf $\endgroup$ – abolfazl Nov 1 '18 at 21:14
5
$\begingroup$

$\mathbf{A}^{\intercal}\mathbf{A}$ is certainly not always invertible. In fact, it will have the same rank as $\mathbf{A}$. Thus if $\mathbf{A}$ has more columns than rows, then $\mathbf{A}^{\intercal}\mathbf{A}$ will never be invertible. However, when doing least squares in practice, $\mathbf{A}$ will have many more rows than columns, so $\mathbf{A}^{\intercal}\mathbf{A}$ will have full rank and thus be invertible in nearly all cases.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Oh wow, that's exactly the sort of explanation I'm looking for. As for your consideration $\mathbf{A}$ does indeed have more columns than rows (it's an overdetermined system). Could you please elaborate a bit on your answer? $\endgroup$ – andresgongora Oct 31 '18 at 17:11
  • $\begingroup$ Sorry about the above comment, I just realized I had mixed up rows and columns (I can't edit it). My matrix $\mathbf{A}$ has more rows than columns, as it comes from an overdetermined system. $\endgroup$ – andresgongora Nov 1 '18 at 19:41
  • $\begingroup$ @andresgongora In that case, you would typically be safe, though it is possible one would occasionally need the pseudo-inverse as discussed in Ryan Howe's answer. $\endgroup$ – Christian Sykes Nov 1 '18 at 19:48
  • $\begingroup$ My question then is, when is it not invertible? Is there any mathematical test/proof for this situations? $\endgroup$ – andresgongora Nov 1 '18 at 20:17
  • $\begingroup$ @andresgongora When the rank of $A$ is less then the number of columns. This is often called rank-deficient. $\endgroup$ – Christian Sykes Nov 1 '18 at 20:32
1
$\begingroup$

However, this requires that $A^{T}A$ be invertible.

No, it doesn't. In practice, it is basically never invertible.

$$ \hat{x} = (A^{T}A)^{-1}A^{T}b \tag{1} $$

can be given by the pseudo-inverse. You can write matrix with the SVD

$$ A = U \Sigma V^{T} \tag{2}$$

where $U \in \mathbb{R}^{m \times m}$ $V \in \mathbb{R}^{n \times n}$ are orthogonal matrices and $\Sigma$ is the matrix of singular values $\Sigma \in \mathbb{R}^{m \times n}$ $$ \Sigma = \textrm{diag}(\sigma_{1}, \cdots, \sigma_{r}, 0, \cdots, 0) \tag{3} $$

the pseudo inverse is given by an $ n \times m $ matrix $$ A^{\dagger} = V \Sigma^{\dagger} U^{T} \tag{4}$$

where $\Sigma^{\dagger}$ is

$$ \Sigma^{\dagger} =\textrm{diag}(\frac{1}{\sigma_{1}}, \cdots, \frac{1}{\sigma_{r}}, 0, \cdots, 0) \tag{5} $$

$$ x^{\dagger} = A^{\dagger}b = V \Sigma^{\dagger}U^{T} b \tag{6} $$

then we get

$$ \| Ax -b \| = \| U\Sigma V^{T}x - b \| = \| \Sigma V^{T}x - U^{T}b \| \tag{7}$$

if we let $ y = V^{T}x $ then we have $ \| x\| = \| y\| $ since $ U$ is an isometry we get $\| Ax-b\|$ is minimized iff $\| \Sigma y - U^{T} b \| $ is minimized. Then we show the least squares solution is. $$ y^{\dagger} = \Sigma^{\dagger}U^{T}b \tag{8}$$

since $ y = V^{T}x$ with $\|x\|$ = $\|y\|$ we get

$$ x^{\dagger} = V \Sigma^{\dagger} U^{T} b = A^{\dagger}b \tag{9} $$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

By taking into account all the provided answers and (very useful) comments, I was able to refine my online search and stumbled upon this video by Khanacademy. With it, I was able to further progress until I was able to write down a proof that I myself was able to understand. Although I'm not sure if its OK to answer my own question, I wanted to post it nonetheless to (i) peer-review it and (ii) leave it here for the community.


Postulate

For any matrix $\mathbf{A}$ of size $m\times n$, the matrix multiplication of its transpose times itself, $\mathbf{A}^{\intercal}\mathbf{A}$, is invertible if $m\geq n$ and $\mathbf{A}$ has full rank. That is, if all $n$ columns in $\mathbf{A}$ are linearly independent.

Proof

Assuming that $\mathbf{A}_{m\times n}$ has full rank (i.e. all its columns are L.I.), we know that its nullspace will only contain the zero vector $\mathbf{0}_n$. $$ Rank(\mathbf{A})=n ~~\Leftrightarrow~~ N(\mathbf{A})=\{\mathbf{0}_n\} ~~\Leftrightarrow~~ \mathbf{A}\mathbf{x} = \mathbf{0}_m \text{ only for } \mathbf{x} = \mathbf{0}_n $$

Conversely, $\mathbf{A}^{\intercal}\mathbf{A}$ will also be full rank, as it will have dimensions $n \times n$ and the same rank as $\mathbf{A}$. In particular, it will have the same rank as $\mathbf{A}$ , because the matrix multiplicaiton $\mathbf{A}^{\intercal}\mathbf{A}$ will lead to a linear combination of either the rows of $\mathbf{A}$ or the columns of $\mathbf{A}^{\intercal}$ (which is equivalent), and because the column rank is equal to the row rank, meaning that the number of L.I. rows (or columns) in $\mathbf{A}^{\intercal}\mathbf{A}$ will be the same as in $\mathbf{A}$. Thus: $$ rank(\mathbf{A}^{\intercal}\mathbf{A}) = rank(\mathbf{A})=n $$

This can be further proven by takin into acount the following:

  • $\mathbf{v}^{\intercal}\mathbf{0}=0$, for any vector $\mathbf{v}$.

  • $\mathbf{u}^{\intercal} \mathbf{v}=\mathbf{u}\cdot\mathbf{b} $, for any two vectors because of the equivalence between dot product and matrix multiplication.

  • The matrix sizes are: $\mathbf{A}^{\intercal}_{n\times m} \mathbf{A}_{m\times n} \mathbf{v}_{n\times 1} = \mathbf{0}_{n\times 1}$.

$$\begin{aligned}\mathbf{A}^{\intercal}\mathbf{A}\mathbf{v} &= \mathbf{0} \\\mathbf{v}^{\intercal}\mathbf{A}^{\intercal}\mathbf{A}\mathbf{v} &= \mathbf{v}^{\intercal}\mathbf{0} = 0\\(\mathbf{A}\mathbf{v})^{\intercal}\mathbf{A}\mathbf{v} &= 0, \text{ where } \mathbf{A}\mathbf{v} \text{ is a vector wit size } n\times 1 \\(\mathbf{A}\mathbf{v})^{\intercal} \cdot (\mathbf{A}\mathbf{v}) &= 0\\\mid\mid \mathbf{A}\mathbf{v} \mid\mid^2 &= 0 \\& \Rightarrow \mathbf{A}\mathbf{v} = \mathbf{0} \\& \Rightarrow \text{if } \mathbf{v} \in N(\mathbf{A}^{\intercal}\mathbf{A}) \Rightarrow \mathbf{v} \in N(\mathbf{A}) \Rightarrow \mathbf{v} = \mathbf{0}, \text{because } N(\mathbf{A})=\mathbf{0} \\ & \Rightarrow N(\mathbf{A}^{\intercal}\mathbf{A}) = \{ \mathbf{0}\}\end{aligned}$$

Finally, we can conclude that $\mathbf{A}^{\intercal}\mathbf{A}$ is a square matrix with linearly independent columns, a sufficient condition to be invertible.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I did my best to come up with a rigorous proof. However, I'm no mathematician, so please let me know if there are any mistakes. Also, I'm not sure the material conditionals (if $\Rightarrow$) and actualy biconditionals (iff $\Leftrightarrow$). $\endgroup$ – andresgongora Nov 2 '18 at 13:38
  • $\begingroup$ Sorry, my last comment is a bit fuzzy. I meant that I'm not sure whether all the "ifs" in my own answer are actually "iffs". For example, A is invertible if it has full rank, vs A is invertible if and only if it has full rank. $\endgroup$ – andresgongora Nov 2 '18 at 13:50
  • $\begingroup$ You need to add is that $n\geq m$. Also, the statement about matrix multiplication leads to a linear combination of columns is not true for non-square matrices. The transpose has the reverse dimensions of the original. $\endgroup$ – Christian Sykes Nov 3 '18 at 12:52
  • $\begingroup$ The first boxed proof is mostly correct however. The second one is superfluous and a bit circular since you already used the equivalence of invertibility and trivial nullspaces in the second proof. It's a basic result in linear algebra and is in any textbook; no need to prove it, except to yourself. $\endgroup$ – Christian Sykes Nov 3 '18 at 13:05
  • $\begingroup$ Since you seem to be concerned with writing correct proofs, it's better, stylistically speaking, to take out all those implication arrows and use words. The chain of implications in the second to last line is somewhat nonsense because of the use of symbols instead of just saying something like "Therefore, $v\in N(A)$. Hence, $v = 0$ since $A$ is invertible." etc. $\endgroup$ – Christian Sykes Nov 3 '18 at 13:19

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.