```markdown
### Example of Dense Newton System with Structure

**Function Definition:**
\[ f(x) = \sum_{i=1}^{n} \psi_i(x_i) + \psi_0(Ax + b), \quad H = D + A^T H_0 A \]

- **Assumptions:**
  - \( A \in \mathbb{R}^{p \times n} \), dense, with \( p \ll n \)
  - \( D \) is diagonal with diagonal elements \(\psi''_i(x_i)\)
  - \( H_0 = \nabla^2 \psi_0(Ax + b) \)

**Method 1:**
- Form \( H \), solve via dense Cholesky factorization
- Cost: \((1/3)n^3\)

**Method 2:**
- Factor \( H_0 = L_0 L_0^T \)
- Write Newton system as:
  - \( D \Delta x + A^T L_0 w = -g \)
  - \( L_0^T A \Delta x - w = 0 \)
  
- Eliminate \(\Delta x\) from first equation; compute \( w \) and \(\Delta x\) from:
  - \( (I + L_0^T AD^{-1}A^T L_0)w = -L_0^T AD^{-1}g \)
  - \( D \Delta x = -g - A^T L_0 w \)

- Cost: \( 2p^2 n \) (dominated by computation of \( L_0^T AD^{-1}AL_0 \))

**Source:** A. d'Aspremont. Convex Optimization M2.
```
