Orthogonal Greedy Algorithm (OGA) — Kurzüberblick (paperkonform)

Definition (abstrakt)

Sei $(H,\langle\cdot,\cdot\rangle_H)$ Hilbertraum, $\mathbb D\subset H$ symmetrisches Dictionary, Ziel $u\in H$.

$$ u_0=0,\quad r_{n-1}=u-u_{n-1},\quad g_n=\arg\max_{g\in\mathbb D}|\langle g,r_{n-1}\rangle_H|,\\ V_n=\mathrm{span}\{g_1,\dots,g_n\},\quad u_n=P_{V_n}(u). $$

Quadratischer Verlust $L(v)=\tfrac12\|v-u\|_H^2$ hat Gradient $\nabla L(v)=v-u$; daher $r_{n-1}=-\nabla L(u_{n-1})$ und die Selektion ist “max. Korrelation mit dem Residuum”.

Diskretisierung (Poisson)

Quadraturpunkte $x_i$, Gewichte $w_i>0$. Diskrete Energie:

$$ \mathcal R_N(v)=\tfrac12\sum_{i=1}^N w_i\,|\nabla v(x_i)|^2 -\sum_{i=1}^N w_i\,f(x_i)\,v(x_i). $$

Evaluationsoperator und Skalarprodukt (nur Gradienten):

$$ I_{1,N}(v)=\bigl(v(x_i),\,\nabla v(x_i)\bigr)_{i=1}^N,\qquad \langle z,y\rangle_{H,N}=\sum_{i=1}^N w_i\,z_{\nabla,i}\cdot y_{\nabla,i}. $$

Mit Datenvektor $u_N=(0,\dots,0,\;f(x_1),\dots,f(x_N))^\top$ gilt

$$ \mathcal R_N(v)=\tfrac12\bigl\|I_{1,N}(v)-u_N\bigr\|_{H,N}^2+C_N. $$

Diskreter OGA

$$ U_{0,N}=0,\quad R_{n-1}=u_N-U_{n-1,N},\\ v_n=\arg\max_{g\in\mathbb D}\bigl|\langle I_{1,N}(g),R_{n-1}\rangle_{H,N}\bigr|,\\ V_n=\mathrm{span}\{v_1,\dots,v_n\},\quad U_{n,N}=P_{V_n}^{(H,N)}(u_N)=\sum_{i=1}^n c_i v_i, $$

Projektion via Gram-System $G c=b$, $G_{ij}=\langle v_i,v_j\rangle_{H,N}$, $b_i=\langle u_N,v_i\rangle_{H,N}$.

Spezialfall: 1D-Poisson auf $(0,\pi)$

$-u''=f,\ u(0)=u(\pi)=0$, $H=H_0^1(0,\pi)$, $\langle v,w\rangle_H=\int_0^\pi v' w'\,dx$.

Nur Gradient-Slots aktiv; $\langle I_{1,N}(g),u_N\rangle_{H,N}\approx \langle u,g\rangle_H$.

Konvergenz (kurz)

Wenn $\epsilon_n(B_1(\mathbb D))_H\lesssim n^{-1/2-\gamma}$, dann $\|u_n-u\|_H^2\lesssim n^{-1-2\gamma}$ (bis auf Approximationsfehler der besten $v\in\mathcal K_1(\mathbb D)$).
Gilt z. B. für geeignete Wörterbücher (flache ReLU$^k$-Modelle etc.).
Wichtig: OGA setzt ein quadratisches (lineares) Funktionsal voraus; für nichtlineare PDE-Energien nicht direkt einsetzbar.

Ergebnisse (1D-Test, OGA)

Harte Randbedingung (Formfunktion): $u=\Phi\,\hat u$ mit $\Phi|_{\partial\Omega}=0$ ⇒ Rand exakt.
Beobachtung: Fehler bis ca. $10^{-7}$.
Penalty/„Delta“-Randbedingung: Dirichlet über Strafterm.
Beobachtung: Plateau um ca. $10^{-5}$.

Warum besser mit Formfunktion? Kein Straf-Bias, bessere Kondition (keine $1/\delta$-Skalierung), stabilere Selektion (weniger Randrauschen), glatteres Restproblem für OGA.

Git & Quelle

Repository: git.numexp.org/ferdinandkruppa/pde-oga

Clone

git clone https://git.numexp.org/ferdinandkruppa/pde-oga.git

Quelle

Siegel, Hong, Jin, Hao, Xu: Greedy Training Algorithms for Neural Networks and Applications to PDEs, arXiv:2107.04466.