OctoInformBeta

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

§4 (setting): electrical and weighted projections: Electrical and weighted projections, absolute row sums and retractions fixing the range of a real matrix

Projections onto spaces of edge gradients.

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

Projection estimates in finite real coordinate spaces involve operators on edge coordinates and the absolute sums of their rows. The electrical construction starts with oriented edges and conductances; the broader class considered here consists of retractions onto the range of a real matrix.

Let EE and II be finite sets of edges and vertices, respectively. A real matrix A∈ℝE×IA\in\mathbb R^{E\times I} maps vertex coordinates to edge coordinates. Write V=ran⁡AV=\operatorname{ran}A for its range, the normalized-gradient space when AA is the normalized-gradient matrix. For real parameters, r\sqrt r denotes the nonnegative square root of max⁡{r,0}\max\{r,0\}, and 0−1=00^{-1}=0.

The Gram matrix GG of AA is given by (1). Let UU be its orthonormal eigenvector matrix, with columns uku_k and corresponding eigenvalues λk\lambda_k, indexed by k∈Ik\in I. G=A𝖳A.G=A^{\mathsf T}A.(1) The Gram eigenbasis coordinate matrix W∈ℝE×IW\in\mathbb R^{E\times I} of AA is the matrix whose columns are the images under AA of the chosen orthonormal eigenvectors of its Gram matrix, as in (2). W=AU=(Auk)k∈I.W=AU=(Au_k)_{k\in I}.(2)✦

The Definition

Definition 1. Let s,t:E→Is,t:E\to I be the source and destination maps of the oriented edges, and let c,σ:E→ℝc,\sigma:E\to\mathbb R be real edge parameters.

The incidence matrix B∈ℝE×IB\in\mathbb R^{E\times I} of (s,t)(s,t) is the matrix whose entries are given by (3), where 𝟏\mathbf 1 denotes an indicator.✦ Bei=𝟏{s(e)=i}−𝟏{t(e)=i}.B_{ei}=\mathbf 1_{\{s(e)=i\}}-\mathbf 1_{\{t(e)=i\}}.(3)✦

The weighted incidence matrix C∈ℝE×IC\in\mathbb R^{E\times I} with conductance parameters cc is defined by (4).✦ C=diag⁡e∈E(ce)B.C=\operatorname{diag}_{e\in E}\bigl(\sqrt{c_e}\bigr)B.(4)✦

For A∈ℝE×IA\in\mathbb R^{E\times I}, the orthogonal range projection ΠA∈ℝE×E\Pi_A\in\mathbb R^{E\times E} is the matrix in (5), using the eigenvalues and coordinate matrix associated with AA.✦ The electrical projection associated with the weighted incidence matrix CC is its orthogonal range projection. ΠA=Wdiag⁡k∈I(λk−1)W𝖳.\Pi_A=W\operatorname{diag}_{k\in I}(\lambda_k^{-1})W^{\mathsf T}.(5)✦

Put Dσ=diag⁡e∈E(σe)D_\sigma=\operatorname{diag}_{e\in E}(\sqrt{\sigma_e}). The weighted projection Pσ(A)∈ℝE×EP_\sigma(A)\in\mathbb R^{E\times E} is defined by (6).✦ Pσ(A)=diag⁡e∈E((σe)−1)ΠDσADσ.P_\sigma(A)= \operatorname{diag}_{e\in E}\bigl((\sqrt{\sigma_e})^{-1}\bigr) \Pi_{D_\sigma A}D_\sigma.(6)✦

For an edge operator P∈ℝE×EP\in\mathbb R^{E\times E} and e∈Ee\in E, its row ℓ1\ell_1 norm re(P)r_e(P) is the absolute row sum in (7).✦ re(P)=∑f∈E|Pef|.r_e(P)=\sum_{f\in E}|P_{ef}|.(7)✦

The retractions onto V=ran⁡AV=\operatorname{ran}A form the set ℛ(A)⊆ℝE×E\mathcal R(A)\subseteq\mathbb R^{E\times E} defined by (8).✦ ℛ(A)={P∈ℝE×E:PA=AandP=ARfor some R∈ℝI×E}.\mathcal R(A)= \left\{P\in\mathbb R^{E\times E}: PA=A\ \text{and}\ P=AR\ \text{for some }R\in\mathbb R^{I\times E}\right\}.(8)✦

What Is Checked

These definitions are stated over finite edge and vertex sets, real matrices, and arbitrary real edge parameters. The Gram matrix A𝖳AA^{\mathsf T}A is symmetric.✦