4
$\begingroup$

$\newcommand{\opnorm}[1]{\left\| #1 \right\|_{\mathrm{op}}} \newcommand{\norm}[1]{\left\| #1 \right\|}$ Suppose we have $X = x_1 x_2^\top \in \mathbb{R}^{n \times d}$ a rank-1 matrix which is non-symmetric in general. I want to either prove that $\| X\|_F = \opnorm{X}$ or give an upper bound $\norm{X}_F \leq c \opnorm{X}$, where ideally $c$ does not depend on the dimensions of $X$. My attempt:

$$ \opnorm{X} = \sup_{\norm{v} = 1} \norm{Xv}_2 = \sqrt{\sup_{\norm{v} = 1} \norm{Xv}_2^2} = \sqrt{\sup_{\norm{v} = 1} v^\top X^\top X v} = \sqrt{\lambda_{\max}(X^\top X)} $$

For the Frobenius norm, use $X$'s singular value decomposition to write $X = USV^\top$, and obtain

$$ \norm{X}_F = \sqrt{\mathrm{tr}(X^\top X)} = \sqrt{\mathrm{tr}(V S U^\top U S V^\top)} = \sqrt{\mathrm{tr}( S^2)} = \sqrt{\sum_{i=1}^{\mathrm{rank}(X)} \sigma_i^2} = \sqrt{\sigma_1^2} $$

However, we know that the singular values of $A$ are the square roots of the eigenvalues of $X^\top X$, therefore $\sigma_1^2 = \lambda_{\max}(X^\top X)$. Hence $\norm{X}_F = \opnorm{X}$.

Is the above proof correct?

$\endgroup$
0

1 Answer 1

8
$\begingroup$

Your proof is correct, but it can be conceptually simplified as follows. Note that both the operator norm and Frobenius norm are unitarily invariant. Therefore, by singular value decomposition, we may assume without loss of generality that $X$ is a singular value matrix whose $(1,1)$-th entry is $\sigma_1$ and all other entries are zero. Now it is blatantly obvious that the two norms are both equal to $\sigma_1$.

Alternatively, we can prove the equality without using singular values: \begin{align} \|X\|_{\operatorname{op}} &=\max_{\|v\|=1}\|X^\top v\| =\max_{\|v\|=1}\|x_1x_2^\top v\| =\max_{\|v\|=1}\|x_1\||x_2^\top v| =\|x_1\|\|x_2\|,\\ \|X\|_F &=\sqrt{\operatorname{tr}\left(XX^\top\right)} =\sqrt{\operatorname{tr}\left(x_1x_2^\top x_2x_1^\top\right)} =\sqrt{(x_1^\top x_1)(x_2^\top x_2)} =\|x_1\|\|x_2\|. \end{align}

$\endgroup$
1
  • $\begingroup$ Nice! This is indeed much simpler. $\endgroup$
    – VHarisop
    Apr 21, 2018 at 23:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .