# Operator norm of a masked SDP matrix

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.

No, no such constant exists. For example, if $$I = \{(i,j) \mid i, 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 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.

• Thanks a lot Mikael ! I did not see Grothendieck theorem applying here. Jun 8 at 14:45
• Beware, this is not THE famous Grothendieck theorem, it is more a lemma. Jun 8 at 15:28
• Ok, is it the little GT from here ? I'm actually trying to compute $$max\left(\frac{||\Sigma_I||_{op}}{||\Sigma||_{op}}:|I|=s \mbox{and I is symmetric}\right)$$ Jun 8 at 15:34
• @guillaumelecue No, this is not little GT, but rather Proposition 3.3 in that same reference. Jun 8 at 19:28
• Thanks for the reference. Yes, the max over all $\Sigma$ would be great. Jun 9 at 9:31