Under which condition if $||UV||_{F}$ is small then we can deduce that $||U||_{F}||V||_{F}$ is also small?

Question

Suppose that $U$ is a $m\times r$ matrix and $V$ is a $n\times r$ matrix, then the following inequality relationship holds: \begin{equation} ||UV^{T}||_{F} \leq ||U||_{F} ||V||_{F}, \end{equation} where $||\cdot||_{F}$ means the Frobenius norm. Since $||U||_{F} ||V||_{F}$ is the upper bound of $||UV^{T}||$, if we enforce the value of $||U||_{F} ||V||_{F}$ is small, then we can achieve the goal of making the value of $||UV^{T}||$ small. However, I'm curious, if we let $||UV^{T}||$ is small, then what additional condition will allow us to deduce that $||U||_{F} ||V||_{F}$ is also small?

Also, since I haven't taken the matrix analysis course in systematics, I want to know under what condition do the inequality take equal signs? I don't find the answer on the description of Wikipedia for matrix norm?

Answer 1

$$\newcommand{\norm}[1]{\left\lVert #1 \right\rVert} \newcommand{\col}{\operatorname{col}}$$

This is a partial answer: Let $\{u_1,\dots,u_m\}$ and $\{v_1,\dots v_n\}$ be the columns of $U$ and $V$ respectively. Then

$$A=\lVert UV^T\rVert_{F}^2=\sum_{i=1}^m\sum_{j=1}^n \left(u_i,v_j\right)^2\tag {1}$$ where $(\cdot,\cdot)$ is the euclidena inner product. On the other hand $$B=\lVert U \rVert ^2_F \lVert V \rVert ^2_F = \left(\sum_{i=1}^m \Vert u_i\Vert^2\right)\left(\sum_{i=1}^m \Vert v_i\Vert^2\right)\tag{2}$$

Now, let us go back to $(1)$ and use the formula in proof 1:

$$A=\sum_{i=1}^m\sum_{j=1}^n\norm{u_i}^2\norm{v_j}^2 -\norm{v_j}^2\norm{u_i -P_{v_j} u_i}^2,$$ where $P_b a= \frac{(a,b)}{\norm{b}^2} b$ is the projection of a vector $a$ onto a vector $b$. Therefore, $$A=B-\underbrace{\sum_{i=1}^m\sum_{j=1}^n\norm{v_j}^2\norm{u_i -P_{v_j} u_i}^2}_C=B-C,$$ which shows that $A\le B$ (we already know that). If $\boxed{C\le \kappa B}$ for some $\kappa\in (0,1)$ then, we'd have $A\ge (1-\kappa)B$.

Answer 2

Thanks for the help of @Tulip. So let me summarize, what @Tulip tries to say is that when $||UV^{T}||_{F}$ is equal to $||U||_{F} ||V||_{F}$, then by making $||UV^{T}||_{F}$ small, we can infer that $||U||_{F} ||V||_{F}$ is also small. This problem can be summarized as discussing what is the equal condition of $||UV^{T}||_{F} \leq ||U||_{F} ||V||_{F}$. Note that \begin{equation} \begin{aligned} ||UV^{T}||_{F}^{2} &= \sum_{i=1}^{m}\sum_{j=1}^{n}|\sum_{k=1}^{r}u_{ik}v_{kj}|^2 \\& \leq \sum_{i=1}^{m}\sum_{j=1}^{n}\left(\sum_{k=1}^{r}|u_{ik}|^2 \sum_{k=1}^{r}|v_{kj}|^2\right) \\& = \left(\sum_{i=1}^{m}\sum_{k=1}^{r}|u_{ik}|^2\right)\left(\sum_{j=1}^{n} \sum_{k=1}^{r}|v_{kj}|^2\right) \\& = ||U||_{F}^2 ||V||_{F}^2, \end{aligned} \end{equation} where the first inequality is following by Cauchy-Schwarz inequality. If we denote $\mathbf{u}_i$ is the $i$-th row of matrix $U$ and $\mathbf{v}_j$ is the $j$-th row of matrix $V$, then when Cauchy-Schwarz becomes equal which means that $\mathbf{u}_i$ and $\mathbf{v}_j$, $\forall j \in [1, n]$ are linear dependent, we can conclude that $||UV^{T}||_{F} \leq ||U||_{F} ||V||_{F}$.

Remark: Although this is a method that allows me to deduce that $||U||_{F} ||V||_{F}$ is also small if I know $||UV^{T}||_{F}$ is small, I think this condition is too pathological, since it seems to require that every row in the matrix $U$ and the matrix $V$ are linearly dependent.