2
$\begingroup$

Let $A,B \in \mathbb{C}^{n \times m}$ be rank $r$ matrices and let

$$ A=U_A \Sigma_A V_A^* \quad \quad \quad B=U_B \Sigma_B V_B^* $$ be the singular value decompositions for $A$ and $B$, and diagonal entries of $\Sigma_A$ and $\Sigma_B$ are ordered from largest to smallest

I would like to show $$ \|A-B\| \geq \|\Sigma_A-\Sigma_B\| $$ where $\|\cdot \|$ is the Frobenius norm or the spectral norm. (I'd prefer to do it for both eventually.)

So far I have found that for the Frobenius norm the problem is closely related to the orthogonal Procrustes problem. Since the spectral and frobenius norm are invariant under left or right unitary multiplication we can assume $A=\Sigma_A$. If we further take $U_B=I$ or $V_B=I$ then the result flows from the linked wiki.

Using a similar approach to the wiki I have shown that for the Frobenius norm it is equivalent to show that $$ tr(U \Sigma_A V \Sigma_B) \leq tr(\Sigma_A \Sigma_B) $$ for any unitaries $U$ and $V$, where $tr$ is the trace.

I have had less success working with the spectral norm, but generated several million matrix pairs across chosen values of $n,m,r$ and did not find a counter example.

I did show the bound holds in the rank one case.

$\endgroup$
4
  • $\begingroup$ Presumably you're using the convention in SVD that the singular values are listed in decreasing order. Otherwise you could have $A=B$ but $\Sigma_A \ne \Sigma_B$. $\endgroup$ Commented Jan 24, 2019 at 15:46
  • $\begingroup$ Yes, singular values are ordered here. I'll edit for clarity $\endgroup$
    – Eric
    Commented Jan 24, 2019 at 15:51
  • $\begingroup$ @Eric: Were you able to solve this? I have also shown that $ \| A - B \|_F \geq \| \Sigma_A - \Sigma_B \|_F$, but stuck on the spectral norm. $\endgroup$
    – VHarisop
    Commented Feb 12, 2019 at 4:01
  • $\begingroup$ @VHarisop Unfortunately I have not managed to solve it for the spectral norm. The frob norm is good enough form my setting, so I not thinking about it much anymore, although I ideally think about it sometimes. I'll post here if I figure it out at some point. I'd certainly still be interested in seeing a solution if you think of one. $\endgroup$
    – Eric
    Commented Feb 13, 2019 at 9:24

1 Answer 1

1
+50
$\begingroup$

Let $\sigma_1(X)\geq\cdots\geq\sigma_n(X)$ denote the singular values of a $n\times n$ matrix $X$ in decreasing order.

For spectral norm $\|\cdot\|_2,$ we need to show a Lipschitz bound

$$|\sigma_i(A)-\sigma_i(B)|\leq \|A-B\|_2$$

for each $1\leq i\leq n.$

This is Golub-van Loan, Matrix Computations, Corollary 8.6.2. It is an easy consequence of the minmax characterization of singular values.

$\endgroup$

You must log in to answer this question.

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