OctoInformBeta

OpenAI preprint, September 2026 · §4. A projection with controlled row sums

Lemma 4.2: Simultaneous weighted energy bounds for finitely many edge functions with values in a real Hilbert space

Retractions with controlled row sums.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let II be a finite vertex set, write n=|I|n=|I|, and let EE be a nonempty finite edge set with endpoint maps src,dst:E→I\mathrm{src},\mathrm{dst}:E\to I and positive scales δe\delta_e. The incidence matrix M∈ℝE×IM\in\mathbb R^{E\times I} records the difference of endpoint indicators✦, and the normalized gradient Aδ∈ℝE×IA_\delta\in\mathbb R^{E\times I} is obtained by dividing row ee of MM by δe\delta_e, as in (1).✦ The normalized-gradient space V⊆ℝEV\subseteq\mathbb R^E is the range of AδA_\delta. Mei=𝟏{src(e)=i}−𝟏{dst(e)=i},Aδ=diag⁡(δe−1)M,V=im⁡Aδ.M_{ei}=\mathbf 1_{\{\mathrm{src}(e)=i\}} -\mathbf 1_{\{\mathrm{dst}(e)=i\}}, \qquad A_\delta=\operatorname{diag}(\delta_e^{-1})M, \qquad V=\operatorname{im}A_\delta.(1)

For a real matrix A∈ℝE×IA\in\mathbb R^{E\times I}, a retraction onto its range is a matrix P∈ℝE×EP\in\mathbb R^{E\times E} that fixes that range and has all its values in it; the set of these retractions is given by (2). ℛ(A)={P∈ℝE×E:PA=A,P=AB for some B∈ℝI×E}.\mathcal R(A)=\bigl\{P\in\mathbb R^{E\times E}:PA=A,\quad P=AB\text{ for some }B\in\mathbb R^{I\times E}\bigr\}.(2)✦

The row ℓ1\ell_1 norm re(P)r_e(P) of PP is the sum of the absolute values of its entries in row ee.✦ For a real inner product space ℋ\mathcal H and data x:E→ℋx:E\to\mathcal H, the matrix action Px:E→ℋPx:E\to\mathcal H is the finite linear combination in (3), which also specifies re(P)r_e(P). re(P)=∑f∈E|Pef|,(Px)e=∑f∈EPefxf.r_e(P)=\sum_{f\in E}|P_{ef}|, \qquad (Px)_e=\sum_{f\in E}P_{ef}x_f.(3)

Weighted Projections

Choose an orthonormal eigenvector matrix UAU_A of the Gram matrix A𝖳AA^{\mathsf T}A, with corresponding eigenvalues μk\mu_k, k∈Ik\in I. The Gram eigenbasis coordinates CA∈ℝE×IC_A\in\mathbb R^{E\times I} and the orthogonal range projection ΠA∈ℝE×E\Pi_A\in\mathbb R^{E\times E} are the matrices in (4); here t†=t−1t^\dagger=t^{-1} for t≠0t\ne0 and 0†=00^\dagger=0. CA=AUA,ΠA=CAdiag⁡(μk†)CA𝖳.C_A=AU_A, \qquad \Pi_A=C_A\operatorname{diag}(\mu_k^\dagger)C_A^{\mathsf T}.(4)

For real row weights σ:E→ℝ\sigma:E\to\mathbb R, let Dσ=diag⁡(max⁡{σe,0})D_\sigma=\operatorname{diag}(\sqrt{\max\{\sigma_e,0\}}), and let Dσ†D_\sigma^\dagger be the diagonal matrix with reciprocal diagonal entries and the same convention at zero. The weighted orthogonal projection ΠA,σ∈ℝE×E\Pi_{A,\sigma}\in\mathbb R^{E\times E} is the matrix defined by (5). ΠA,σ=Dσ†ΠDσADσ.\Pi_{A,\sigma}=D_\sigma^\dagger\Pi_{D_\sigma A}D_\sigma.(5)✦ For strictly positive σ\sigma, write ℓ2(E,σ)\ell_2(E,\sigma) for ℝE\mathbb R^E with squared norm ∑e∈Eσeze2\sum_{e\in E}\sigma_e z_e^2.

The Claim

Theorem 1 (Weighted projection and controlled retraction). For any real matrix A∈ℝE×IA\in\mathbb R^{E\times I}, strictly positive weights σ\sigma, and x:E→ℋx:E\to\mathcal H, the weighted projection satisfies (6). ∑e∈Eσe∥(ΠA,σx)e∥2≤∑e∈Eσe∥xe∥2.\sum_{e\in E}\sigma_e\| (\Pi_{A,\sigma}x)_e\|^2 \le \sum_{e\in E}\sigma_e\|x_e\|^2.(6)✦

Suppose every vertex is incident to an edge and every two distinct vertices are joined by an edge. If σ\sigma is a strictly positive probability on EE, the normalized gradient satisfies the weighted row estimate (7). ∑e∈Eσere(ΠAδ,σ)2≤(2log⁡n)2.\sum_{e\in E}\sigma_e\,r_e(\Pi_{A_\delta,\sigma})^2 \le (2\log n)^2.(7)✦

Under these endpoint assumptions, suppose also n≥2n\ge2, let λ\lambda be a strictly positive probability on EE, and let JJ be finite. For data xj:E→ℋx^j:E\to\mathcal H, j∈Jj\in J, with ∥xej∥2≤1\|x^j_e\|^2\le1 for every j,ej,e, there is a matrix PP satisfying (8). P∈ℛ(Aδ),re(P)≤4log⁡n(e∈E),∑e∈Eλe∥(Pxj)e∥2≤4(j∈J).\begin{gathered} P\in\mathcal R(A_\delta),\qquad r_e(P)\le4\log n\quad(e\in E), \\ \sum_{e\in E}\lambda_e\|(Px^j)_e\|^2\le4\quad(j\in J). \end{gathered}(8)✦

Under the same assumptions on the endpoints, nn, and λ\lambda, let BjB_j, j∈Jj\in J, be positive bounds and let the data satisfy ∥xej∥2≤Bj\|x^j_e\|^2\le B_j for every j,ej,e. Then there is a matrix PP satisfying (9). P∈ℛ(Aδ),re(P)≤4log⁡n(e∈E),∑e∈Eλe∥(Pxj)e∥2≤4Bj(j∈J).\begin{gathered} P\in\mathcal R(A_\delta),\qquad r_e(P)\le4\log n\quad(e\in E), \\ \sum_{e\in E}\lambda_e\|(Px^j)_e\|^2\le4B_j\quad(j\in J). \end{gathered}(9)✦

In the paper, the result reads: for every strictly positive probability λ\lambda on EE, there is a probability σ\sigma with σe≥λe/2\sigma_e\ge\lambda_e/2 such that the orthogonal projection PP onto VV in ℓ2(E,σ)\ell_2(E,\sigma) satisfies max⁡e∑f|Pef|≤H=4log⁡(2n)\max_e\sum_f|P_{ef}|\le H=4\log(2n), hence ∥P∥∞→∞≤H\|P\|_{\infty\to\infty}\le H, and, with II denoting the identity on ℝE\mathbb R^E, both PP and I−PI-P are contractions on ℓ2(E,σ)\ell_2(E,\sigma).

What Is Checked

The energy estimate is stated for arbitrary finite real matrices and positive weights; the remaining statements concern normalized gradients with the indicated endpoint conditions, and the retraction statements allow finite families of data in an arbitrary real inner product space.

For every real matrix AA, its Gram matrix A𝖳AA^{\mathsf T}A is symmetric.✦