= Incidence pseudoinverse decomposition
{title2=$D^\dagger D=I-\mathbf1\mathbf1^\top/n$}
For a <connected graph>, the <Moore-Penrose inverse> of its <oriented incidence matrix> satisfies $D^\dagger D=I-\Pi_1$, because this product is the <orthogonal projection> onto $(\ker D)^\perp$. Thus every signal decomposes into its constant mean and $D^\dagger D\theta$. Writing $L=\max_e\|(D^\dagger)_{\cdot,e}\|_2$, a <sub-Gaussian random vector> noise gives a simultaneous bound on $\|(D^\dagger)^\top z\|_\infty$ with scale $L\sqrt{\log(m/\delta)}$.
Back to article page
