# Lower bound for distance between matrices from singular values

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.

• 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$. Commented Jan 24, 2019 at 15:46
• Yes, singular values are ordered here. I'll edit for clarity
– Eric
Commented Jan 24, 2019 at 15:51
• @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. Commented Feb 12, 2019 at 4:01
• @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.
– Eric
Commented Feb 13, 2019 at 9:24

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.$$