# Max-norm projection of a Hermitian matrix onto the set of positive semidefinite matrices

For a given Hermitian matrix $$A$$ (i.e. complex matrix with $$A_{ij}^{\ast}=A_{ji}$$) find its max-norm projection onto the set of complex positive semi-definite matrices:

$$\Pi(A)=\mathrm{argmin}_{M\succeq0}\|A-M\|_{\infty}.$$

Here $$\|A\|_{\infty}=\mathrm{max}_{ij}|A_{ij}|$$ is the entry-wise max-norm. This problem has exact solution for the Frobenius and spectral matrix norm (see for example here). Is there a closed-form solution for the max-norm? Is there an efficient algorithm to calculate the projection and what is the computational cost (for $$n\times n$$ complex matrix)?

## 1 Answer

Partial answer regarding an algorithm to find projection, not a closed form.

The problem is of the following convex SDP: $$\min_{t,M} ~~~~~~~t\\ \mbox{subject to}\\ \hspace{5cm} |A_{i,j}-M_{i,j}|\leq t, ~\forall ~i,j\\ \hspace{3cm}M\succeq 0.$$ This can be solved using CVXPY (or a software alike). You might want to check Boyd's Convex Optimization for the exact details of the computational complexity of interior point methods.