3 updated exactly a year old answer!

Update. One more point worth mentioning here is that for positive definite $A$ and $B$, the following inequality can be shown:

\begin{equation*} \sigma_j(A-B) \le \sigma_j(A \oplus B),\qquad j=1,2,\ldots,n, \end{equation*} where $A\oplus B$ denotes the direct sum of $A$ and $B$.

The choice $\epsilon' = \sigma_1(A)+\sigma_1(B)$ works, and in general cannot be improved upon: simply take $B=-A$.

By restricting to special classes of matrices, you can probably obtain more interesting upper-bounds.

## Some details.

A standard result is: $\sigma_1(X+Y) \le \sigma_1(X)+\sigma_1(Y)$, which implies that $\sigma_1(A-B) \le \sigma_1(A) + \sigma_1(B)$. This inequality suggests the bound on $\epsilon'$ mentioned above.

A lower-bound on $\sigma_1(C) =: \|A-B\|$ is more exciting. For example, the following inequality (see Problem III.6.13, of Matrix Analysis by R. Bhatia) can be shown:

$$(*)\qquad\max_j |\sigma_j(A)-\sigma_j(B)| \le \|A-B\|.$$

Update. One more point worth mentioning here is that for positive definite $A$ and $B$, the following inequality can be shown:

\begin{equation*} \sigma_j(A-B) \le \sigma_j(A \oplus B),\qquad j=1,2,\ldots,n, \end{equation*} where $A\oplus B$ denotes the direct sum of $A$ and $B$.

The choice $\epsilon' = \sigma_1(A)+\sigma_1(B)$ works, and in general cannot be improved upon: simply take $B=-A$.

By restricting to special classes of matrices, you can probably obtain more interesting upper-bounds.

Some details.

A standard result is: $\sigma_1(X+Y) \le \sigma_1(X)+\sigma_1(Y)$, which implies that $\sigma_1(A-B) \le \sigma_1(A) + \sigma_1(B)$. This inequality suggests the bound on $\epsilon'$ mentioned above.

A lower-bound on $\sigma_1(C) =: \|A-B\|$ is more exciting. For example, the following inequality (see Problem III.6.13, of Matrix Analysis by R. Bhatia) can be shown:

$$(*)\qquad\max_j |\sigma_j(A)-\sigma_j(B)| \le \|A-B\|.$$

1

The choice $\epsilon' = \sigma_1(A)+\sigma_1(B)$ works, and in general cannot be improved upon: simply take $B=-A$.

By restricting to special classes of matrices, you can probably obtain more interesting upper-bounds.

Some details.

A standard result is: $\sigma_1(X+Y) \le \sigma_1(X)+\sigma_1(Y)$, which implies that $\sigma_1(A-B) \le \sigma_1(A) + \sigma_1(B)$. This inequality suggests the bound on $\epsilon'$ mentioned above.

A lower-bound on $\sigma_1(C) =: \|A-B\|$ is more exciting. For example, the following inequality (see Problem III.6.13, of Matrix Analysis by R. Bhatia) can be shown:

$$(*)\qquad\max_j |\sigma_j(A)-\sigma_j(B)| \le \|A-B\|.$$