ChapterZero

Equivalence of the $\gamma_2$ norm and the $\|\cdot\|_{\infty \rightarrow 1}^\star$ norm

It turns out that the $\|\cdot\|_{\infty \rightarrow 1}^\star$ norm ( the trace dual of the $\|\cdot\|_{\infty \rightarrow 1}$ norm, explicitly given as $\|A\|_{\infty \rightarrow 1}^\star = \inf\{\|d\|_1 : A = G\text{diag}(d)G^t \text{ and } \|G\|_{1 \rightarrow \infty} \leq 1 \}$ ) is equivalent to the $\gamma_2$ factorization norm, which is defined as $\gamma_2(A) = \min_{X = UV^t} \|U\|_{2 \rightarrow \infty} \|V\|_{2 \rightarrow \infty}.$ Note that constraining the $\gamm_2$ norm constrains the Euclidean norms of the rows of and

A quick proof relies on Grothendieck’s inequality, which more or less states that

If is a real matrix, then for every choice of unit vectors in a real Hilbert space,
$\displaystyle \left|\sum_{i,j} a_{i,j} \langle x_i, y_j \rangle\right| \leq K_G \|A\|_{\infty \rightarrow 1},$
where is an absolute constant.

Note that the trace dual norm of $\gamma_2$ is
$\gamma_2^\star(A) = \max_{\gamma_2(M) = 1} \langle A, M \rangle = \sup_{\substack{\|U\|_{2\rightarrow \infty} =1 \\ \|V\|_{2 \rightarrow \infty} = 1}} \text{Tr}(AV^t U) = \sup_{\substack{\|u_i\|_2 = 1 \\ \|v_j\|_2 = 1}} \sum_{ij} a_{ij} \langle v_i, u_j \rangle,$
where the supremum is over all choices of lengths for u_i, v_j .

Therefore $\gamma_2^\star(A) \leq K_G \|A\|_{\infty \rightarrow 1},$ so $\gamma_2(A) \geq K_G^{-1} \|A\|_{\infty \rightarrow 1}^\star$ (it’s easy to check that if $\|\cdot\|_1 \leq \|\cdot\|_2$ then $\|\cdot\|_1^\star \geq \|\cdot\|_2^\star$ and that $(c\|\cdot\|)^\star = \frac{1}{c}\|\cdot\|^\star.$ )

To show the other direction, $\gamma_2(A) \geq \|A\|_{\infty \rightarrow 1}^\star$ , observe that
$\displaystyle \|A\|_{\infty \rightarrow 1} = \max_{\substack{\|x\|_\infty \leq 1 \\ \|y\|_\infty \leq 1}} \sum_{ij} a_ij x_i y_j \leq \sup_{\substack{\|x_i\|_2 = 1 \\ \|y_j\|_2 = 1}} \sum_{ij} a_{ij} \langle x_i, y_j \rangle = \gamma_2^\star(A)$
since the second maximum is taken over all lengths for x_i, y_j.

Putting the two inequalities together,
$K_G^{-1} \|A\|_{\infty \rightarrow 1}^\star \leq \gamma_2(A) \leq \|A\|_{\infty \rightarrow 1}^\star.$

As an aside, note that now we have the terminology, we can more concisely write Grothendieck’s inequality as

If is a real matrix, then $\gamma_2^\star(A) \leq K_G \|A\|_{\infty\rightarrow 1}.$

Possibly relevant posts:

Trace dual of the $\|\cdot\|_{\infty\rightarrow 1}$ norm (1/19/2010)
Factorization norm details (2/9/2010)
Spectral spread of Graphs (7/30/2010)

Tags: factorization, Grothendieck, inequality, matrix, norm

Equivalence of the $\gamma_2$ norm and the $\|\cdot\|_{\infty \rightarrow 1}^\star$ norm

Possibly relevant posts:

Leave a comment

Archives

intelligently designed

light and not filling

Tags

ChapterZero

Equivalence of the norm and the norm

Possibly relevant posts:

Leave a comment

Archives

intelligently designed

light and not filling

Tags

Equivalence of the $\gamma_2$ norm and the $\|\cdot\|_{\infty \rightarrow 1}^\star$ norm