4
$\begingroup$

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)?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .