Show that $\mathbf{X}_{tr} \leq \sqrt{nm} f(\mathbf{X})$

Question

$\mathbf{X}$ is a $n\times m$ matrix and $$ f(\mathbf{X}) = \min\limits_{X = UV} \max_i \mathbf{\|U_i\|} \max_j \mathbf{\|V_j\|} \;\; \text{(max over the rows) and } \|\| \text{is the $l_2$ norm} $$

If $\mathbf{P\Sigma Q'}$ is the SVD of $\mathbf{X}$, then we can consider $\mathbf{U} = \mathbf{P\Sigma^{1/2}}$ and $\mathbf{V} = \mathbf{Q\Sigma^{1/2}})$.

How can I show that $\mathbf{X}_{tr} \leq \sqrt{nm} f(\mathbf{X})$ where $\mathbf{X}_{tr}$ is the trace norm of $\mathbf{X}$ (sum of singular values)

What I did so far,

Trace norm can be written in matrix form as $\mathbf{X}_{tr} = \mathbf{Tr}(\Sigma\mathbf{C}), \mathbf{C} \text{ is the } m \times n \text{ matrix of ones}$, and using Cauchy-Schwarz inequality,

$ \mathbf{Tr^2(\Sigma C}) \leq \mathbf{Tr(\Sigma'\Sigma)}\mathbf{Tr(C'C)} = nm\mathbf{Tr(\Sigma'\Sigma)}$

Now, I am stuck at the point $\mathbf{Tr(\Sigma'\Sigma)}$, which is the sum of the eigenvalues of $\mathbf{X'X}$. How can I show that $\mathbf{Tr(\Sigma'\Sigma)} \leq f(\mathbf{X})$.

Answer 1

Applying the Cauchy-Schwartz inequality, we have for any real matrices $C$ and $D$ \begin{align} \text{tr}(CD)&=\sum_{ij}C_{ij}D_{ji} \\ &\le\Big(\sum_{ij}C_{ij}^2\Big)^\frac12\Big(\sum_{ij}D_{ij}^2\Big)^\frac12 \\ &=\big(\text{tr}(C^TC)\big)^\frac12\big(\text{tr}(D^TD)\big)^\frac12=\|C\|\|D\|. \end{align}

Now perform the singular value decomposition of $UV^T=ASB^T$ where $S$ is the diagonal matrix of the singular values of $UV^T$ and $A$ and $B$ are the associated orthogonal matrices. Apply the above proposition, we have \begin{align} \|UV^T\|_\text{tr} &= \text{tr}(S) = \text{tr}(A^TUV^TB) \\ &\le \|A^TU\|\|V^TB\|=\|U\|\|V\| \\ &\le \sqrt{n\,\max_i(U_iU_i^T)}\sqrt{m\,\max_j(V_jV_j^T)}=\sqrt{nm}\max_i\|U_i\|\max_j\|V_j\|. \end{align}