I'm perusing this paper. In page 8, I came across this:
My question is about equation 45. Also in this question I don't care about neither $u$ nor $M$, I mentioned them just to give some context.
In short my problem is:
Let $y \in \mathbb{R}^n$, $x \in \mathbb{R}^m$, $A \in \mathbb{R}^{n \times m}$.
$\|.\|$ is the euclidean vector norm, $\|.\|_{op}$ is a matrix norm defined as: $$\|A\|_{op} = \max_x \frac{\|Ax\|}{\|x\|}$$
So I have: $|y^TAx| \leq \|y\|\space\|A\|_{op}\|x\|$. As long as I have an inequality with the absolute value of something, it is the same as $y^TAx \leq \|y\|\space\|A\|_{op}\|x\|$
Now I will multiply both sides by 2 and multiply the left side by: $$\frac{\sqrt{\tau}}{\sqrt{\tau}}\frac{(\tau\sigma \|A^TA\|_{op})^{\frac{1}{4}}}{(\tau\sigma \|A^TA\|_{op})^{\frac{1}{4}}}$$
Then I get: $$2y^TAx \leq\ 2 \frac{\|A\|_{op} \|y\| \sqrt{\tau}} {(\tau\sigma \|A^TA\|_{op})^{\frac{1}{4}}} \frac{(\tau\sigma \|A^TA\|_{op})^{\frac{1}{4}} \|x\| } {\sqrt{\tau}}$$
using $a^2+b^2 \geq 2ab$: $$2y^TAx \leq\ \frac{\|A\|^2_{op} \tau} {(\tau\sigma \|A^TA\|_{op})^{\frac{1}{2}}} \|y\|^2 + \frac{(\tau\sigma \|A^TA\|_{op})^{\frac{1}{2}} } {\tau} \|x\|^2 $$
In equation 45, the term $\|A\|^2_{op}$ doesn't appeard, it is replaced by $\|A^TA\|_{op}$. I know that $\|A\|^2_{op} \geq \|A^TA\|_{op}$, so I don't know why the authors make this replacement. In the paper, they say that $A$ is any matrix with no special properties.
The next line comes from doing: $$(\tau\sigma \|A^TA\|_{op})^{\frac{1}{2}}z = \frac{\|A^TA\|_{op} \tau} {(\tau\sigma \|A^TA\|_{op})^{\frac{1}{2}}}$$ $$\tau\sigma \|A^TA\|_{op} z = \|A^TA\|_{op} \tau$$ $$z = \frac{1}{\sigma}$$
Why do authors replace $\|A\|_{op}^2$ with $\|A^TA\|_{op}$ in equation 45? With this replacement the inequalities don't necessarily hold. Is there a property I am missing?
I'll use $\langle x,y\rangle$ to denote the usual inner product $y^*x$.
It is always true that $$\|A\|^2_{op}=\|A^*A\|_{op},$$ where $A^*$ denotes the adjoint (the conjugate transpose, so just the transpose if $A$ is real). This is very easy to prove. The reverse inequality from the one you mention is the easy one: \begin{align} \|A\|^2&=\max\{ \|Ax\|^2:\ \|x\|=1\}=\max\{\langle Ax,Ax\rangle:\ \|x\|=1\}\\ &=\max\{\langle A^*Ax,x\rangle:\ \|x\|=1\}\\ &\leq \|A^*A\|, \end{align} where the inequality is simply Cauchy-Schwarz and definition of the operator norm. Now, from the above inequality, you have $$ \|A\|^2\leq\|A^*A\|\leq\|A^*\|\,\|A\|. $$ So, for nonzero $A$ (the zero case is trivial) you have $\|A\|\leq\|A^*\|$. Apply the above to $A^*$, to get $\|A^*\|\leq\|A^{**}\|=\|A\|$, so $\|A^*\|=\|A\|$. If you now go back to the inequalities we had, $$ \|A\|^2\leq\|A^*A\|\leq\|A^*\|\,\|A\|=\|A\|^2. $$ So $\|A\|^2=\|A^*A\|$.