ETH_NumericalMethodsForCSE

Info

Doebel: https://publish.obsidian.md/ddoebel/Welcome
Dragos: https://polybox.ethz.ch/index.php/s/jgGpEyX6Ctf2KCD
- uploads faster than Popa
Popa: https://polybox.ethz.ch/index.php/s/roTjs6ppjc5fXW3
- (outdated: https://n.ethz.ch/~iopopa/)

Übungen

#timestamp 2025-09-19

![[NumCSE_week1_practice.cpp]]

#timestamp 2025-10-03

why squared loss?

differentiable
always positive
icreasesquadratically with distance

(-> but sth. oder would also be possible)

least square solution:

\begin{aligned} (α, β) & = a r g m i n \sum_{i = 1}^{m} | y_{i} - α x_{i} - β |^{2} \\ = a r g m i n L (α, β) \\ \frac{\partial L}{\partial α} & = \sum_{i = 1}^{m} 2 (y_{i} - α x_{i} - β) (- x_{i}) \overset{!}{=} 0 & ⟹ (\sum_{i = 1}^{m} x_{i}^{2}) α + (\sum_{i = 1}^{m} x_{i}) β = \sum_{i = 1}^{m} x_{i} y_{i} \\ \frac{\partial L}{\partial β} & = \sum_{i = 1}^{m} 2 (y_{i} - α x_{i} - β) (- 1) \overset{!}{=} 0 & ⟹ (\sum_{i = 1}^{m} x_{i}) α + n β = \sum_{i = 1}^{m} y_{i} \end{aligned}

[\begin{matrix} \sum x_{i}^{2} & \sum x_{i} \\ \sum x_{i} & n \end{matrix}] \cdot [\begin{matrix} α \\ β \end{matrix}] = [\begin{matrix} \sum_{i = 1}^{n} x_{i} y_{i} \\ \sum_{i = 1}^{n} y_{i} \end{matrix}]

A^{⊤} A x = A^{⊤} b

if matrix is sparse, we can introduce the residual $r = A x - b$

A^{⊤} A x = A^{⊤} b ⟹ A^{⊤} (A x - b) = 0 ⟹ A^{⊤} r = 0

r = A x - b ⟹ - r + A x = b

[\begin{matrix} - 1 & A \\ A^{⊤} & 0 \end{matrix}] [\begin{matrix} \vec{r} \\ \vec{x} \end{matrix}] = [\begin{matrix} b \\ 0 \end{matrix}]

#timestamp 2025-10-31

Pasted image 20251031084025.png

#timestamp 2025-11-29

do {
Eigen::Vector4d s = df(x).householderQr().solve(f(x));
x = x - s;
gn_update.push_back(s.norm());
// absolute stopping criteria
} while(gn_update.back() > tol);

Newton-Gauss method, see 8.11)d)

Hiptmair used

s.lpNorm<Eigen::Infinity>();

Infinity-norm stopping is better, because:

it is cheaper to compute,
it treats the largest component directly,
it is less sensitive to cancellation.

He also used

df(x).colPivHouseholderQr().solve(f(x));

The Jacobian in Gauss–Newton can easily become nearly rank-deficient, especially early in the iteration.
Without pivoting, householderQr() may produce an unstable or unusable step. colPivHouseholderQr() safeguards the solve by reordering the columns so that the effective conditioning is improved.