5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – artificial_moonlet Jul 25 '18 at 10:16
  • 1
    $\begingroup$ Thanks for the comment. Isn't your inequality clear from $D$ being the identity matrix or am I missing something? $\endgroup$ – Sebastian Schlecht Jul 25 '18 at 11:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Suvrit Jul 30 '18 at 1:08
4
+50
$\begingroup$

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\} $$


Previous answer

Unfortunately behind a paywall, but following my own comment about chasing literature on matrix balancing, I found the following old paper that solves your problem (EDIT: As noted by Sebastian, this paper actually only provides a solution for a restricted case), not only for the operator norm, but for a variety of other norms.

T. Ström. Minimization of norms and logarithmic norms by diagonal similarities. Computing, March 1972, Volume 10, Issue 1–2, pp 1–7.

$\endgroup$
  • $\begingroup$ Thank you very much for this very helpful lead. Btw, I'm only concerned with the operator norm. The recommended paper solves the problem almost. It is unfortunately restricted to companion matrices for the operator norm (Theorem 2). I will keep digging... $\endgroup$ – Sebastian Schlecht Jul 30 '18 at 10:20
  • $\begingroup$ The LMI book noted above solves it numerically as a generalized eigenvalue problem, while interestingly Ström's paper, as you noted, solves it for companion matrices (in some sense, in fact "analytically"). $\endgroup$ – Suvrit Jul 30 '18 at 13:56
  • $\begingroup$ The formulation as a GEVP in the referred book looks perfect. I need some more time to understand how to numerically solve this GEVP. $\endgroup$ – Sebastian Schlecht Jul 30 '18 at 14:22
  • $\begingroup$ Have a look at the LMI toolbox (in Matlab, or possibly even separately). I think it comes equipped with some kind of interior point methods for solving this GEVP. $\endgroup$ – Suvrit Jul 30 '18 at 18:36
  • 1
    $\begingroup$ @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). $\endgroup$ – Mark L. Stone Jul 30 '18 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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