Given $A\in\mathbb{C}^{n\times n}$, what is $s_* = \arg\min \|A-sI\|$?

Here $\|A\|$ is the operator norm, $\|A\|=\rho(A^*A)^{1/2}$, and $I$ is the identity.

The corresponding problem for the Frobenius norm $\|A\|_F = \left(\sum A_{ij}^2\right)^{1/2}$ has a simple solution: reduce to the triangular case with a Schur factorization $A=QTQ^*$ (which does not alter $\|A\|_F=\|T\|_F$), then the problem becomes the one of minimizing $\sum_i |\lambda_i-s|^2$, with $\lambda_i=T_{ii}$ the eigenvalues of $A$, and then the solution is the arithmetic mean $s_{*,F}=\frac{1}{n}\sum \lambda_i$.

I do not see a simple solution for the case of the operator norm, though; I have tried applying the Schur factorization or the SVD, but the resulting problem is not immediate. Do you have any ideas? Or is this problem a known one?

  • 1
    $\begingroup$ in the case of A normal, I guess one gets s = the center of the minimum disk containing spec(A), right? $\endgroup$ – Pietro Majer Feb 21 '16 at 9:31
  • $\begingroup$ Conjugation by a unitary matrix doesn't affect the operator norm either, so you may assume $A$ is 70034-triangular. If $A$ is diagonal it's operator norm is the largest entry, so indeed in the normal case take $s$ to be the circumcentre of the spectrum. This may hold in general. $\endgroup$ – Lior Silberman Feb 21 '16 at 11:09
  • 1
    $\begingroup$ @PietroMajer Yes, if $A$ is normal then that is the solution (via a diagonalization argument). This also shows that in general the Frobenius-norm minimizer is different from the operator-norm minimizer: just take a $3\times 3$ diagonal matrix whose diagonal entries form a triangle with centroid different from its circumcenter. $\endgroup$ – Federico Poloni Feb 21 '16 at 11:48

Not a closed form answer, but this can be solved as a semidefinite program. In particular, we can rewrite the task as \begin{equation*} \min_{t\ge 0, s}\ t\quad \text{s.t.}\quad (A-sI)^*(A-sI) \preceq t^2I, \end{equation*} which results in the SDP \begin{equation*} \min_{s,t}\ t\quad \text{s.t.}\quad \begin{bmatrix} tI & A-sI\\ (A-sI)^* & tI\end{bmatrix} \succeq 0. \end{equation*}


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.