1
$\begingroup$

$\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})$.

$\endgroup$
8
  • $\begingroup$ Your formulation of the problem and notations are so horrible that nobody will understand what you are asking. $\endgroup$ – Hans Apr 16 '18 at 1:03
  • $\begingroup$ @Hans I edited the question. Does it makes sense now ? $\endgroup$ – Shew Apr 16 '18 at 6:32
  • $\begingroup$ No. $f(X)$ does not make sense, because $UV′$ is but one of infinitely many decompositions of X, so your definition of $f(X)$ is not a function of $X$. You'd better not write it this way. I have answered your question below. $\endgroup$ – Hans Apr 17 '18 at 1:27
  • $\begingroup$ @Hans Does the notation make sense now ?. $\endgroup$ – Shew Apr 17 '18 at 6:14
  • $\begingroup$ Now it does, but only in the question formulation proper. Do you now know why your linked question is put on hold? Your current description is still erroneous. e.g. $f(\mathbf{X}) = \langle\sigma, \mathbf{P_i}\rangle \langle\sigma,\mathbf{Q_j}\rangle$ does not make sense. How can it depend on $(i, j)$? Your thoughts appear chaotic and your presentation drives people mad. :-D May I ask whether you have had any formal training in mathematics? $\endgroup$ – Hans Apr 17 '18 at 7:20
2
$\begingroup$

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}

$\endgroup$
0

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.