Skip to main content
3 of 3
Minor improvements

Let function $f : \mathbb R^{m \times n} \to \mathbb R_0^+$ be defined as follows

$$f (\mathrm X) := \| \,\mathrm X \mathrm A^\top \|_\text{F}^2 + \| \,\mathrm X^\top \mathrm A \,\|_\text{F}^2 + \left( \langle \mathrm A, \mathrm X \rangle \right)^2$$

where $\mathrm A \in \mathbb R^{m \times n}$ is given. Note that

$$\| \,\mathrm X \mathrm A^\top \|_\text{F}^2 = \| \,\mathrm A \mathrm X^\top \|_\text{F}^2 \geq \lambda_n ( \mathrm A^\top \mathrm A ) \, \| \mathrm X \|_\text{F}^2$$

$$\| \mathrm X^\top \mathrm A \|_\text{F}^2 = \| \mathrm A^\top \mathrm X \|_\text{F}^2 \geq \lambda_m ( \,\mathrm A \mathrm A^\top ) \, \| \mathrm X \|_\text{F}^2$$

and that $\left( \langle \mathrm A, \mathrm X \rangle \right)^2 \geq 0$. Hence,

$$f (\mathrm X) \geq \left( \lambda_n ( \mathrm A^\top \mathrm A ) + \lambda_m ( \,\mathrm A \mathrm A^\top ) \right) \| \mathrm X \|_\text{F}^2$$

Suppose that $\rm A$ is tall (i.e., $m > n$) and has full column rank (i.e., $\mbox{rank} (\mathrm A) = n$). In this case,

$$\lambda_n ( \mathrm A^\top \mathrm A ) = \sigma_n^2 (\mathrm A) = \left( \frac{\| \mathrm A \|_2}{\kappa (\mathrm A)} \right)^2$$

where $\kappa (\mathrm A)$ is the (finite) condition number of $\rm A$, and $\lambda_m ( \,\mathrm A \mathrm A^\top ) = 0$. Thus,

$$f (\mathrm X) \geq \left( \frac{1}{\kappa (\mathrm A)} \right)^2 \| \mathrm A \|_2^2 \, \| \mathrm X \|_\text{F}^2$$

Since

$$\| \mathrm A \|_\text{F} \leq \sqrt{\mbox{rank} (\mathrm A)} \, \| \mathrm A \|_2 = \sqrt{n} \, \| \mathrm A \|_2$$

we obtain

$$f (\mathrm X) \geq \underbrace{\frac 1n \left( \frac{1}{\kappa (\mathrm A)} \right)^2}_{=: c (\mathrm A)} \| \mathrm A \|_\text{F}^2 \, \| \mathrm X \|_\text{F}^2$$

where $c$ is a function of matrix $\rm A$.