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.

Improve this question
$\endgroup$
3
  • $\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, 2018 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$
    – Jiro
    Jul 25, 2018 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, 2018 at 1:08

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\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$
    – Jiro
    Jul 30, 2018 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, 2018 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$
    – Jiro
    Jul 30, 2018 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, 2018 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, 2018 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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