# Numerical minimization spectral norm under diagonal similarity

This question is a follow up.

Let $A$ be a real square matrix of size $n \times n$. How to determine the minimum spectral norm under diagonal similarity, i.e.,

$$s(A) = \inf_{D} \lVert D^{-1} A D\rVert_2,$$ where $D$ is a non-singular, diagonal real matrix. As it is unlikely to find an analytical upper bound, I would like to ask how $s(A)$ could be determined numericallly.

• I believe the following holds $$||D^{-1} A D ||_2 \leq ||D^{-1}||_2 ||A||_2 ||D||_2 = ||A||_2 \kappa(D),$$ where $\kappa(D) = \frac{\sigma_{\max}(D)}{\sigma_{\min}(D)}$, also known as the condition number of $D$. The smallest condition number is 1, therefore, $$s(A) \leq ||A||_2.$$ I realize this doesn't exactly answer your question, but it does give a bound. – artificial_moonlet Jul 25 '18 at 10:16
• Thanks for the comment. Isn't your inequality clear from $D$ being the identity matrix or am I missing something? – Sebastian Schlecht Jul 25 '18 at 11:46
• In case you are interested in the Frobenius norm version of this, have a look at radio.feld.cvut.cz/matlab/toolbox/robust/osborne.html -- the Frobenius norm version of this problem is the same as the $\ell_2$-norm matrix balancing, which ends up being a convex optimization problem. More generally, if you look into the matrix balancing literature you'll likely find a solution to your question. – Suvrit Jul 30 '18 at 1:08

Here is a better, more direct solution.

This problem can be cast as a Generalized Eigenvalue Problem as is shown by Boyd, El Ghaoui, Feron, and Balakrishnan on page 39 (§3.3) of Linear Matrix Inequalities in System and Control Theory:

$$s(A) = \inf \left\{\gamma \mid A^*PA < \gamma^2 P \textrm{ for diagonal } P > 0 \right\}$$

• @Sebastian Schlecht This is not convex, but is a quasi-convex Bilinear Matrix Inequality (due to product of $\gamma^2$ with $P$), hence can be solved by bisection (employing LMI solver for bisection sub-problems) - see, for example, yalmip.github.io/example/decayrate. However, Nesterov and Nemirovski's Projective Method, used by LMI toolbox's gevp, may be better (faster). – Mark L. Stone Jul 30 '18 at 21:17