3
$\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$
0
$\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$

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.