Inequality between matrix-vector products

Question

$A$ is a full row-rank $m\times n$ matrix with $n > m$. Can I say the following holds for a vector $x\in\mathbb{R}^n$? $$ \|(AA^\top)^{-1}Ax\| \leq \|A^\top (AA^\top)^{-1} A x\| $$ If not, under which conditions could this hold?

Answer 1

Recall that $\operatorname{Im}(A^\top)=\ker(A)^{\perp}$. Hence $\operatorname{Im}(A^\top)\oplus \ker(A)= \mathbb{R}^n$.

So every $x\in\mathbb{R}^n$ can be written as $x=A^\top y+z$, where $z\in\ker(A)$ and $y\in\mathbb{R}^m$.

Now $\|(AA^\top)^{-1}Ax\|=\|(AA^\top)^{-1}A(A^ty+z)\|=\|y\|$

Next $\|A^\top (AA^\top)^{-1} A x\|=\|A^\top (AA^\top)^{-1} A(A^\top y+z)\|=\|A^\top y\|$.

Therefore, your question reduces to the following one:

Does $\|y\|\leq \|A^\top y\|$ hold for every $y\in\mathbb{R}^m$?

This is true if and only if the $m$ singular values of $A^\top$ are greater or equal to 1.