Measurable selection of a matrix-depth maximizer

For fixed $u$, each function $(x,\mathrm{\Gamma })\mapsto (u^T{x}_i{)}^2-u^T\mathrm{\Gamma }u$ is continuous. Its nonpositive and nonnegative sets are closed, so their indicators are upper semicontinuous: outside a closed set the indicator is locally zero, and at a point of the set its limsup is at most one. Finite sums and the minimum of two upper semicontinuous maps are upper semicontinuous. The infimum over fixed $u\in U$ is also upper semicontinuous because its strict sublevel is the union of the strict sublevels for individual $u$. Thus $D$ is jointly upper semicontinuous in $(x,\mathrm{\Gamma })$. Every directional count minimum belongs to $\{0,1\mathrm{/}n,\dots ,1\}$; the infimum of a nonempty subset of this finite set belongs to the same set. Ties may give depth $1$, so the full grid is retained.

Put $R(x)={\max }_{i\le n}\mathrm{\parallel }{x}_i{\mathrm{\parallel }}_2^2$. If a positive semidefinite matrix $\mathrm{\Gamma }$ has $\mathrm{\parallel }\mathrm{\Gamma }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}>R(x)$, a top unit eigenvector $u$ gives $u^T\mathrm{\Gamma }u=\mathrm{\parallel }\mathrm{\Gamma }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}>(u^T{x}_i{)}^2$ for every $i$, so the empirical upper weak tail is zero and the dense depth is zero. In the global block-sparse class, write $\mathrm{\Gamma }$ as its symmetric block on some support $S$, $\mathrm{\mid }S\mathrm{\mid }\le s$, and its diagonal complement. The largest eigenvalue is attained either by a unit eigenvector in that block or by a coordinate vector in the complement; choose the former in a tie when the block is nonempty. Hence a norm-attaining vector has support of size at most $s$ or one, extends to a coordinate set of size $2s$, and belongs to $U_s$. The same strict inequality makes the sparse depth zero. This argument selects one appropriate eigenvector and does not claim every eigenvector is supported in a small block.

For $0\le j\le n$ and any fixed closed cube $Q\subseteq {\mathbb{R}}^d$, let $H_{j,Q}:=\{x:\mathrm{\exists }\mathrm{\Gamma }\in K\cap Q,D(x,\mathrm{\Gamma })\ge j\mathrm{/}n\}$. This is closed. Indeed its defining superlevel set is closed by step 1.1, and $K\cap Q$ is compact. If $x_0\mathrm{\notin }{H}_{j,Q}$, product-open rectangles in the complement of that superlevel set cover $\{x_0\}\times (K\cap Q)$. Finitely many matrix-coordinate neighborhoods cover $K\cap Q$; intersect their sample-coordinate neighborhoods to obtain a neighborhood of $x_0$ outside $H_{j,Q}$. The empty $K\cap Q$ case gives the empty hit set. The same argument with $Q={\mathbb{R}}^d$ gives a closed set $H_j:=\{x:{\max }_{K}D(x,\cdot )\ge j\mathrm{/}n\}$.

Set $H_{n+1}=\mathrm{\varnothing }$ and $E_j=H_j\setminus H_{j+1}$ for $0\le j\le n$. These are Borel by [F4] and partition $E$, since the maximum exists by [F2] and takes a value in the finite grid by step 1.1. On $E_j$, the argmax fiber is $A(x)=\{\mathrm{\Gamma }\in K:D(x,\mathrm{\Gamma })\ge j\mathrm{/}n\}$, so $A(x)$ hits a fixed closed cube $Q$ exactly when $x\in H_{j,Q}$.

Take a fixed closed cube $Q_0$ containing $K$; the entry bound in the proof of [F2] permits $Q_0=[-c,c{]}^d$. Repeatedly bisect each coordinate interval into two closed halves, ordering the $2^d$ child cubes lexicographically. On $E_j$, starting from $Q_0$, retain the first child cube $Q$ with $x\in H_{j,Q}$. A child exists because the children cover their parent and the parent meets $A(x)$. Inductively every selected-cube event is Borel: if $B$ is the event selecting a parent with ordered children $Q_1,\dots ,Q_{2^d}$, the event selecting $Q_r$ is $B\cap H_{j,Q_r}\setminus {\bigcup }_{\mathrm{\ell }<r}{H}_{j,Q_{\mathrm{\ell }}}$. Each level has finitely many cubes, so its selected center $a_m(x)$ is a finite-valued Borel map. The first-child rule remains unambiguous at overlapping cube boundaries.

For fixed $x$, the sets $A(x)\cap Q_m(x)$ are nested nonempty compact sets and the cubes have diameter $2c\sqrt{d}{2}^{-m}\to 0$. Their intersection is nonempty: otherwise their complements would cover the first compact set, and a finite subcover would contradict a later set's nonemptiness. The intersection has at most one point because its diameter is zero; denote the point by ${\widehat{\mathrm{\Gamma }}}_c(x)$. Since both it and $a_m(x)$ lie in $Q_m(x)$, $\mathrm{\parallel }{a}_m(x)-{\widehat{\mathrm{\Gamma }}}_c(x){\mathrm{\parallel }}_2$ is at most the cube diameter and tends to zero. Thus each coordinate of ${\widehat{\mathrm{\Gamma }}}_c$ is Borel by [F5], and the matrix-valued map is Borel by [F6]. It belongs to $A(x)$ for every sample. Taking $c=\beta M$ proves both original bounded-class selection claims.

The continuous function $R$ has a Borel integer majorant $k(x)=1+\lfloor R(x)\rfloor$, with $\{k=\mathrm{\ell }\}=\{\mathrm{\ell }-1\le R<\mathrm{\ell }\}$ for $\mathrm{\ell }\ge 1$. On that stratum, step 1.2 shows that every admissible matrix outside the fixed cap $\mathrm{\ell }$ has depth zero. The maximum over the cap is nonnegative, so any cap maximizer is a global maximizer. Apply the explicit construction of steps 1.1–5.1 with $c=\mathrm{\ell }$ for each integer $\mathrm{\ell }\ge 1$ and paste those Borel maps on the Borel strata $\{k=\mathrm{\ell }\}$. For any open set of matrices, the preimage under this pasted map is the countable union, over $\mathrm{\ell }\ge 1$, of the Borel stratum $\{k=\mathrm{\ell }\}$ intersected with the preimage under its fixed-cap Borel selector; hence the pasted map is Borel. This yields a Borel global maximizer in each class. Global argmax fibers need not be compact when the maximal depth is zero; only their compact capped subfibers are used. Division by the fixed $\beta >0$ preserves coordinatewise Borel measurability, proving the covariance-output claim for bounded and global selectors.