Operator norm of a masked SDP matrix

Question

Let $\Sigma$ be a $d\times d$ semi-definite positive matrix (SDP). Let $I\subset\{1,\ldots, d\}\times \{1, \ldots, d\}$ be a symmetric subset of indices (i.e. if $(p,q)\in I$ then $(q,p)\in I$). We denote by $||.||_{op}$ the operator norm over $\mathbb{R}^{d\times d}$. Is it possible to find an absolute constant $c$ (independent of $d$ and $\Sigma$) such that $$||\Sigma_I||_{op}\leq c ||\Sigma||_{op}$$ where $\Sigma_I$ is the symmetric matrices with entries equal to $\Sigma_{pq}$ when $(p,q)\in I$ and $0$ everywhere else.

Answer 1

No, no such constant exists. For example, if $I = \{(i,j) \mid i<j\}$, then $\Sigma\mapsto \Sigma_I$ is the usual triangular projection, and the norm is of order $\log n$, see for example Norm of the upper triangular part of symmetric matrix (the fact that you restrict to positive definite matrices does not change much, see below).

Of course, this $I$ is not symmetric, but it can be made symmetric by a standard $2$-by-$2$ matrix trick. Namely, if $I \subset \{1,\dots,2d\}\times \{1,\dots,2d\}$ is defined by $\{(i,d+j) \mid i<j\leq d\}\cup \{(j+d,i)\mid i<j\leq d\}$ then the norm of $\Sigma \mapsto \Sigma_I$ is of order $\log n$.

Actually, an old theorem by Grothendieck allows to compute almost exactly the best constant $c$. Almost, because Grothendieck's theorem allows to compute exactly the norm of $\Sigma\mapsto \Sigma_I$ on the space of all matrices (real or complex). But, writing any matrix as a sum $\Sigma=\Sigma_1-\Sigma_2+i\Sigma_3-i\Sigma_4$ with $\|\Sigma_k\|_{op} \leq \|\Sigma\|_{op}$, one sees that the norm of the restriction to positive definite matrices is, up to a factor $4$, equivalent to the norm.

Grothendieck's theorem says that the norm of $\Sigma\mapsto \Sigma_I$ is equal to the infimum of $\max_{i,j} \|v_i\| \|w_j\|$ over all euclidean spaces $H$ and vectors $v_1,\dots,v_d,w_1,\dots,w_d \in H$ such that $$\langle v_i,w_j\rangle = \begin{cases} 1 & if\ (i,j)\in I\\ 0 & \textrm{otherwise}\end{cases}$$

The same formula holds similarly if you replace the indicator function of $I$ by an arbitrary function $\varphi:\{1,\dots,d\}\times \{1,\dots,d\}\to \mathbf{C}$, and the map $\Sigma\mapsto \Sigma_I$ by $\Sigma\mapsto (\varphi(i,j)\Sigma_{i,j})$ (a Schur multiplier).

See for example Chapter 5 in Pisier's book Similarity problems and completely bounded maps.

Added on June 9 The best constant $c=c(d)$ such that $\|\Sigma_I\|_{op} \leq c(d) \|\Sigma\|_{op}$ for every positive definite $d \times d$ matrix $\Sigma$ and every symmetric $I \subset \{1,\dots,d\} \times \{1,\dots,d\}$ is of order $\sqrt{d}$. The inequality $c(d) \leq \sqrt{d}$ is easy from Grothendieck's characterization, and the reverse inequality $c(d) \geq \sqrt{t}/100$ follows by considering for $\Sigma$ a Hadamard unitary. All this is explained in section 2 of

Doust, I., Norms of 0-1 matrices in Cp, pp 50-55, Proc. Centre Math. Appl. Austral. Nat. Univ., 39, Austral. Nat. Univ., Canberra, 2001.

available on the author's webpage.