Unit 4, continued: Low-dimensional projections of nearly orthogonal tensors

This part studies Theorem 4.1, Lemma 4.2, and their proofs in B §4, pp.11–14. The argument concerns finite-dimensional Hilbert spaces and uses neither mixing, selected lengths, nor distal structure. Its application to ergodic averages with point-dependent lengths comes later, in B §5.

The paper calls the result tensor packing. The quantity being estimated is concrete: among a sequence of nearly orthogonal rank-one tensors, how many can have a large projection onto the same low-dimensional subspace?

1. The full statement

All Hilbert spaces are real, tensor products are Hilbert tensor products, and logarithms are natural. Fix

where $d,L$ are integers. Let $x_1,\ldots,x_m$ and $y_1,\ldots,y_m$ lie in the unit balls of $H_1,H_2$, respectively.

For the $x$ sequence, suppose a graph on $\{1,\ldots,m\}$ of maximum degree at most $L$ contains all pairs satisfying

The $y$ sequence satisfies the same condition, possibly with a different exceptional graph. The threshold obeys

B Theorem 4.1 (p.11, equation (4.1)) asserts that there is an absolute constant $C$ such that every orthogonal projection of rank at most $d$, denoted $P:H_1\otimes H_2\to H_1\otimes H_2$, satisfies

The constant is independent of both ambient Hilbert-space dimensions. Here $d$ bounds the projection rank; it is unrelated to the number of functions in an ergodic average.

2. Small inner products off the graph bound the average vector

Source: B p.12, equation (4.5) in the proof.

Suppose unit-ball vectors $v_n$ have an exceptional graph of maximum degree $L$ and satisfy $|\langle v_i,v_j\rangle|\le\eta$ outside that graph. For every nonempty index set $A$,

Expand the square. There are $|A|$ diagonal terms, each at most $1$, and at most $L|A|$ ordered exceptional pairs, each of absolute value at most $1$. Every other term has absolute value at most $\eta$. Dividing by $|A|^2$ proves (Mean).

Conversely, if the average of a collection of vectors has norm at least $a>0$ and $a^2>\eta$, then

This observation will be used twice: first to count indices concentrated in high-covariance directions, and then to count indices with nearby projection coefficients.

3. Reduction to finite dimensions and a matrix representation

3.1 The finite-dimensional reduction does not decrease the count

Source: B p.12, the reduction to finite linear spans.

Let $H'_1$ and $H'_2$ be the spans of the finite sequences $x_n$ and $y_n$, and let $Q$ project onto $H'_1\otimes H'_2$. Replace the original projection subspace $E=\operatorname{Ran}P$ by $E'=Q(E)$, and let $P'$ be the orthogonal projection onto $E'$. The space $E'$ is finite-dimensional, with $\dim E'\le d$.

For $z\in H'_1\otimes H'_2$,

The second equality uses $Qz=z$. The last step uses $Qu\in E'$ and $\|Qu\|\le1$. A counting bound for the new projection therefore bounds the original count. Henceforth regard $H_1,H_2$ as finite-dimensional and write $P$ for the new projection.

3.2 A Hilbert–Schmidt orthonormal basis and two covariance matrices

Identify $x\otimes y$ with a rank-one matrix from $H_2$ to $H_1$. Choose a Hilbert–Schmidt orthonormal basis $A_1,\ldots,A_r$ for the projection subspace, with $r\le d$. If $r=0$, the count is zero and there is nothing further to prove.

Define

Both matrices are positive semidefinite, and

Let $E_1,E_2$ be the respective spans of eigenvectors with eigenvalues greater than $\sqrt d$. Each space has dimension at most $\sqrt d$: every such eigenvalue contributes at least $\sqrt d$ to a trace bounded by $d$.

4. Removing the few indices in high-covariance directions

Source: B pp.12–13, equation (4.6).

4.1 The size of a finite net

In the $k$-dimensional Euclidean unit ball, choose a maximal set of points with pairwise distances greater than $\rho$. Balls of radius $\rho$ cover the unit ball. Balls of radius $\rho/2$ around the selected points are disjoint and lie in a ball of radius $1+\rho/2$. Comparing volumes bounds the number of points by

Take $\rho=\varepsilon/40$ and $k\le\sqrt d$. The unit ball of either $E_1$ or $E_2$ can therefore be covered by at most

balls of radius $\varepsilon/40$.

4.2 How many large projections can lie in one small ball?

First remove indices satisfying $\|P_{E_1}x_n\|>\varepsilon/10$. Suppose $s$ of these projections lie in one net ball. Any one of them is within $\varepsilon/20$ of all the others, so their average has norm at least $\varepsilon/20$. The average of the original vectors has at least the norm of the average of their orthogonal projections.

By (Mean),

Since $\eta\le\varepsilon^2/10^4$, we obtain $s\le C(1+L)\varepsilon^{-2}$. Sum over the net balls and repeat the removal for $y_n,E_2$. The total number removed is at most

The two sequences may use different exceptional graphs; estimate them separately and add the bounds.

5. Coefficient vectors and a separated subset of the remaining indices

Source: B p.13, from the compressed matrices $B_j$ to a maximal separated set.

5.1 Large coefficients survive compression

Let $Q_i$ be the orthogonal projections onto $E_i^\perp$, and set

For every retained index,

The coefficient map $z\mapsto(\langle A_j,z\rangle_{\mathrm{HS}})_j$ is a contraction because $A_j$ is orthonormal. For an index still satisfying $\|P(x_n\otimes y_n)\|\ge\varepsilon$, define

Then $\|v_n\|\ge\varepsilon-\varepsilon/5\ge\varepsilon/2$. The map from the original tensor $x_n\otimes y_n$ to $v_n$ remains a contraction.

5.2 Bounding the number of coefficients in one ball

The union of the two exceptional graphs has maximum degree at most $2L$. Outside this union,

If a collection of coefficient vectors lies in the ball centered at some $v_{n_0}$ with radius $\varepsilon/8$, its average has norm at least

The original tensor average has at least this norm, since the coefficient map is a contraction. Apply (Mean) to the tensors, with exceptional degree $2L$ and threshold $\eta^2$. The collection contains at most $C(1+L)\varepsilon^{-2}$ indices.

Choose a maximal $\varepsilon/8$-separated subset of the remaining coefficient vectors and denote its size by $\ell$. Maximality puts every remaining vector within $\varepsilon/8$ of a selected point. The remaining count is therefore at most

The task is now to bound $\ell$, avoiding a net for the full $r$-dimensional coefficient ball whose size would be exponential in $d$.

6. A Gaussian matrix estimate

Source: B Lemma 4.2, pp.11–12, equations (4.3)–(4.4).

6.1 Self-adjoint dilation

Let $B_1,\ldots,B_r$ be matrices between finite-dimensional real Hilbert spaces, and define

Assume

For independent standard normal variables $g_j$, Lemma 4.2 asserts

Set $H=\sum_jg_jH_j$ and $G=\sum_jg_jB_j$. Then $H$ is the displayed self-adjoint dilation of $G$, and $\|H\|_{\mathrm{op}}=\|G\|_{\mathrm{op}}$.

6.2 Gaussian integration by parts and differentiation of matrix powers

For an integer $q\ge2$, first write

Apply the standard normal integration-by-parts identity $\mathbb E[g_jF(g)]=\mathbb E[\partial_{g_j}F(g)]$ and differentiate the matrix power term by term. This yields

The function $F$ is a polynomial and all Gaussian moments are finite, so integration by parts is justified.

6.3 Controlling the noncommuting matrix terms

Fix a self-adjoint matrix $H$ and write its eigenvalues in an eigenbasis as $\lambda_u$. For any self-adjoint $K$, set $p=2q-2$. Then

Weighted arithmetic–geometric mean gives

Using $|K_{uv}|=|K_{vu}|$, the two terms agree after summation over $u,v$. Consequently,

Sum over $j$ and use positive semidefiniteness of $S$ to obtain

The last step does not require $S$ and $H$ to commute. Since $0\le S\le\|S\|I$, it suffices to pair this inequality with the positive semidefinite matrix $|H|^{2q-2}$ and take the trace.

6.4 The trace enters only once

Direct computation gives $\mathbb E\operatorname{tr}H^2=\operatorname{tr}S$. Iterating the preceding bound yields

Using $\|H\|^{2q}\le\operatorname{tr}H^{2q}$ and Hölder's inequality,

Choose $q=\max\{2,\lceil\log(2+d)\rceil\}$. The last factor is bounded by an absolute constant, and $\sqrt q\le C\sqrt{\log(2+d)}$. This proves (Gaussian).

The argument uses $\operatorname{tr}S\le2d$ rather than ambient dimension times $\|S\|$. No factor depending on $\dim H_1$ or $\dim H_2$ appears.

7. A finite Gaussian comparison bounds the separated set

Source: B p.13, equation (4.7) and the subsequent Gaussian interpolation argument.

7.1 The precise comparison statement

Let $(X_1,\ldots,X_\ell)$ and $(Y_1,\ldots,Y_\ell)$ be centered finite Gaussian vectors. Suppose that, for every $i,j$,

Then

Equality of the corresponding coordinate variances is not required. This finite comparison is usually called the Sudakov–Fernique inequality.

7.2 Proof using a smooth maximum

Realize the two vectors independently. For $\beta>0$, set

Then $\partial_if_\beta=p_i$, and

Consider the independent Gaussian interpolation $Z_t=\sqrt t\,X+\sqrt{1-t}\,Y$. Write the covariance difference matrix as $\Delta C=C_X-C_Y$. Differentiate the expectation on $0<t<1$, then integrate by parts in the Gaussian variables:

The second equality uses $\sum_jp_j=1$ to combine the diagonal variance terms with the covariance term. The hypothesis makes the derivative nonnegative. Finite-dimensional Gaussian moments exist, and the first and second derivatives of $f_\beta$ are bounded. Integrate first over a closed subinterval of the interior, then use continuity at the endpoints to obtain $\mathbb E f_\beta(X)\ge\mathbb E f_\beta(Y)$. Degenerate covariances can also be handled by adding small independent Gaussian noise and passing to the limit.

Finally, use

and let $\beta\to\infty$ to prove (SF).

7.3 A lower bound for the maximum of independent normal variables

For independent standard normals $\xi_1,\ldots,\xi_\ell$, there is an absolute constant $c>0$ such that

This follows directly from a Gaussian tail estimate. For $u\ge1$, integrate only over $[u,u+1/u]$ to obtain

Take $u=\tfrac12\sqrt{\log\ell}$. For sufficiently large $\ell$, we have $\ell\mathbb P(\xi_1\ge u)\to\infty$, and independence gives

The negative part of the maximum must also be controlled. Write $M_\ell=\max_i\xi_i$. Then

Hence $\mathbb EM_\ell\ge u/2-o(1)\ge c\sqrt{\log\ell}$ for all sufficiently large $\ell$. For the remaining finitely many $\ell\ge2$, use monotonicity and

and reduce the absolute constant $c$ if needed. This proves the full range of (Normal).

7.4 Application to the compressed coefficient vectors

On the separated set from §5, define

These are centered Gaussian variables, with increment variances

Compare them with independent normal variables $Y_n$, each $Y_n$ having variance $\varepsilon^2/128$. Their pairwise increment variances are exactly $\varepsilon^2/64$. Equations (SF) and (Normal) therefore imply

The last step uses $\|x_n\|,\|y_n\|\le1$. The variables $Z_n$ need not be independent; independence is required of the comparison variables $Y_n$.

8. The compressed covariances satisfy the Gaussian matrix hypotheses

Source: B p.13, following (4.7).

By $B_j=Q_1A_jQ_2$ and $0\le Q_i\le I$,

The spectral cutoff in §3 bounds the operator norm on the right by $\sqrt d$ and its trace by $d$. Thus the self-adjoint dilation from §6 has

with $\|S\|_{\mathrm{op}}\le\sqrt d$ and $\operatorname{tr}S\le2d$. The Gaussian estimate applies.

Combine it with (Sep), square, and rearrange to obtain

If $\ell\le1$, the corresponding exponential bound holds automatically. By (Clusters), the remaining count is at most

Add the indices already removed in (Exceptional). Since $0<\varepsilon\le1$,

and $\log(2+d)$ has a positive absolute lower bound, this term is absorbed into the same expression. Increasing an absolute constant proves (Count).

9. Logarithmic dimension growth and the averaged estimate

Source: B (4.2) on p.11, the end of p.13, and (4.8) on p.14.

9.1 Why this dimension choice still gives a sublinear count

Set

As $m\to\infty$,

For each fixed $\varepsilon,L$, the right side of (Count) is therefore a constant times $\exp(o(\log m))$, hence $o(m)$. This $o(m)$ is uniform in the ambient Hilbert spaces, vector sequences, projection, and admissible $\eta$.

9.2 Average projection norm

Every projection norm is at most $1$. Split the indices into those with norm less than $\varepsilon$ and those with norm at least $\varepsilon$. Then

The order of quantifiers is: fix the accuracy $\varepsilon$, choose an admissible $\eta$ and its exceptional degree $L$, then let $m$ grow. The degree $L$ may depend on the previously chosen $\eta$, but must remain fixed during this limit $m\to\infty$.

This finite-dimensional estimate supplies no mixing rate. When qualitative correlation decay later produces a finite exceptional degree, the estimate is used in this order, without adding an unstated uniform decay rate.

Guide to the original text and scope of the proof

• B p.11, Theorem 4.1, equations (4.1)–(4.2): the counting bound and $d_m$.
• B pp.11–12, Lemma 4.2, equations (4.3)–(4.4): Gaussian matrix moment estimates.
• B p.12, equation (4.5): the average-norm bound under an exceptional-graph condition.
• B pp.12–13, equation (4.6): finite-net counting in high-covariance directions.
• B p.13, equation (4.7): separated coefficients, Gaussian comparison, and projection norms.
• B p.14, equation (4.8): the averaged form and order of parameter choices.

This part gives the full deduction of the finite Hilbert-space result, including the Gaussian comparison and lower bound for independent normal maxima that the original text states briefly. Applications to the ergodic construction must still verify the vector-sequence, exceptional-graph, and projection-rank hypotheses. The estimate alone does not imply fourfold pointwise convergence.