Add a multiple of $I$ to a matrix to minimize its operator norm

Question

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?

Answer 1

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*}