0
$\begingroup$

Say I have three matrices $\mathbf{W} \in \mathbb{R}^{p \times m}$ and $\mathbf{A}, \mathbf{B} \in \mathbb{R}^{m \times n}$ with $\operatorname{rank}(\mathbf{A}) \leq r$ and $\mathbf{B}$ is unconstrained on rank. I also assume that all of them are bounded in Frobenius norm by some number say $\Vert\mathbf{W}\Vert_F, \Vert\mathbf{A}\Vert_F, \Vert\mathbf{B}\Vert_F \leq \kappa$

I am trying to show that $ \sup \Vert\mathbf{WA} \Vert_F \leq \sup \Vert\mathbf{WB}\Vert_F$ (sup is over the three matrices)

My idea is blend SVD decomposition and the fact that the Frobenius norm of a matrix is the squared singular values and hence LHS would be cropped as only $r$ singular values would contribute to the sum. But I can't make it formal. Do you have any hints on how to proceed?

——— Edit post @whuber comment!

OK. This was question was actually not posed correctly at all sorry. What I am looking is not really to simply show that $ \sup \Vert\mathbf{WA} \Vert_F \leq \sup \Vert\mathbf{WB}\Vert_F$ but rather to find the separating factor based on the ranked (A) vs. full ranked (B) constraint. So basically looking a result like;

$$ \sup \Vert\mathbf{WA} \Vert_F \leq \textrm{some function of} (r, \kappa) \\ \sup \Vert\mathbf{WB} \Vert_F \leq \textrm{some function of} (m, \kappa) $$

Happy to get any pointers! Thanks again :)

$\endgroup$
3
  • 3
    $\begingroup$ I must be misreading this, so could you clarify something? It appears we could restate your problem as follows. Let $X=\mathbb R^{p\times m}$ and $Y=\mathbb R^{n\times m},$ limited to matrices of Frobenius norm $\kappa$ or less. Let $f:Y\to\mathbb R$ be given by $$f(A)=\sup\{||WA||_F\mid W\in X\}.$$ You seem to be asking whether the supremum of $f$ where $A$ ranges over the subset of $Y$ of matrices of rank $r$ or less cannot exceed the supremum of $f$ where $A$ ranges over $Y.$ That's trivially true, so where is my interpretation incorrect? $\endgroup$
    – whuber
    Commented Apr 18 at 21:56
  • $\begingroup$ @whuber Hi! Thanks for your answer, I clarified my question in main text. $\endgroup$
    – Dime
    Commented Apr 19 at 22:24
  • $\begingroup$ I think there will be no separating factor, as the singular values of $WB$ can be arbitrarily small; for example, if $\text{rank}(A) = r-1$ and all the nonzero singular values of $WA$ equal the largest $r-1$ singular values of $WB$, we can make $||WB||_F$ arbitrarily close to $||WA||_F$ by having the smallest singular value of $WB$ approach zero... so the sups would appear to me to be the same. $\endgroup$
    – jbowman
    Commented Apr 19 at 22:34

1 Answer 1

3
$\begingroup$

Consider the case where $p=n$ so $WA$ and $WB$ are square. Let $WB$ equal the identity matrix, and $WA$ equal the identity matrix with the $[n,n]^{th}$ entry equal to zero. The Frobenius norm of $WB$ is obviously equal to $\sqrt{n}$, and that of $WA$ to $\sqrt{n-1}$.

Now, let the $[n,n]^{th}$ entry of $WB$, label it $\sigma^2_n$, $\to 0$. Clearly $\Vert WB\Vert _F = \sqrt{n-1+\sigma^2_n} \to \sqrt{n-1}$.

We can easily extend this to the case of $r < n-1$ and nonsquare matrices; the key is the singular values, not the shape. Thus, for every $WA$, there is a $WB$ with Frobenius norm arbitrarily close to that of $WA$.

This indicates that, as long as we know nothing but the rank of the two matrices $WA$ and $WB$, we cannot show that the separating factor is greater than zero.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.