How hard (P, NP, NP-hard) is it to compute Schur norms of matrices (as multipliers)?

Question

Given a matrix $A\in M_n(\mathbb{C})$, I will denote by $||A||_\infty$ the operator norm of $A$, as seen acting on the Hilbert space $\mathbb{C}^n$. This makes $M_n(\mathbb{C})$ into a Banach space (actually a Banach algebra, actually a $C^*$ algebra).

We will define a new norm on $M_n(\mathbb{C})$ in the following way: A matrix $T$ acts on $M_n(\mathbb{C})$ by pointwise multiplication (i.e. Schur product), giving rise to an operator $M_T:M_n(\mathbb{C})\longrightarrow M_n(\mathbb{C})$. For example for

$$T=\left[\begin{array}{cc} 1 & 2 \\ 3 & 4 \end{array}\right]$$ we have

$$M_T\left(\left[\begin{array}{cc} a & b \\ c & d \end{array}\right]\right)= \left[\begin{array}{cc} a & 2b \\ 3c & 4d \end{array}\right]$$

We will denote by $||T||_{Schur}$ the norm of the operator $M_T$, as an operator of the Banach space $M_n(\mathbb{C})$. How hard is it to compute/estimate this norm? Are there polynomial algorithms (in $n$ and the approximation error) that can do it? Is it actually NP?

Answer 1

It turns out that this norm can be computed efficiently (i.e., it is in $P$). This wasn't known at the time that the Davidson paper (originally linked in a comment above) was written, which is why it suggests that the computation is hard.

To compute the norm, first use the equivalence of points (1) and (2) in Theorem 1.1 of the Davidson paper. This tells us that $\|T\|_{schur} = \|T\|_{cb}$, where $\|\cdot\|_{cb}$ refers to the "completely bounded" norm of $T$.

It was shown in "J. Watrous. Semidefinite programs for completely bounded norms. Theory of Computing, 5:217-238, 2009" that the completely bounded norm can be computed efficiently via semidefinite programming.

For what it's worth, using this method tells me that the norm $\|\cdot\|_{schur}$ of the map stated in the question is $4$. However, this norm is not always equal to $\max_{i,j}\{t_{i,j}\}$. The simplest example I have been able to find to demonstrate this fact is $$ T = \begin{bmatrix}0 & 1 \\ 1 & 1\end{bmatrix}, $$ which has $\|T\|_{schur} = 2/\sqrt{3} > 1$.

Edit: Here is some (surprisingly simple) MATLAB code that computes this norm. You must first install CVX before running this code. Just modify the first line of code with whatever operator $T$ you want to compute the norm of.

T = [1 2;3 4];

n = length(T);
cvx_begin sdp quiet
    cvx_precision high;
    variable Y0(n,n) hermitian
    variable Y1(n,n) hermitian
    minimize max(diag(Y0))/2 + max(diag(Y1))/2
    subject to
        [Y0, T; T', Y1] >= 0;
        Y0 >= 0;
        Y1 >= 0;
cvx_end
cvx_optval

Answer 2

EDIT. In light of Nathaniel's answer above, I must admit that the hardness intuition was wrong, and the problem is indeed tractable. However, I'm leaving the original answer as is, to preserve the context.

---

Too long for a comment, but some background information that suggests why it might be usually very hard to compute $\|T\|_{\text{S}}$.

The following theorem is usually attributed to Haagerup (though the Davidson paper cited above suggests that it was already known to previous authors, and it could also be essentially attributed to Grothendieck).

Thm. Let $T$ be any matrix. Then \begin{equation*} \|T\|_S = \min\{ \|X\|_{\infty,2} \|Y\|_{\infty,2} \mid T = X^*Y\}, \end{equation*} where $\|\cdot\|_S$ denotes the Schur-multiplier norm, while $\|X\|_{\infty,2} = \max_{1 \le j \le n} \|x_j\|_2$, where $x_j$ is the $j$-th column of $X$.

If $T$ is unitary, then $\|T\|_S=1$; if $T$ is symmetric positive definite, then $\|T\|_S = \max_i t_{ii}$. For many other special matrix structures, this norm can be computed, and the Davidson paper linked to in my comment to the OP provides several such examples.