Using ${L}_{1}$ Optimization for Ellipse Fitting

For a point ${\left[ x, y \right]}^{\top} \in \mathbb{R}^{2}$ to be on ellipse parameterized by $\boldsymbol{s} = {\left[ a, b, c, d, e, f \right]}^{\top}$ it must obey:

$$ a {x}^{2} + b x y + c {y}^{2} + d x + e y + f = 0 $$

Given a set $\left\{ {\left[ {x}_{i}, {y}_{i} \right]}^{T} \right\}_{i = 1}^{n}$ of points on an ellipse, one could formulate the problem:

$$ \arg \min_{\boldsymbol{s}} \frac{1}{2} {\left\| \boldsymbol{Z} \boldsymbol{s} \right\|}_{2}^{2} $$

Where the $i$ -th row of $\boldsymbol{Z}$ is given by ${\left[ {x}_{i}^{2}, {x}_{i} {y}_{i}, {y}_{i}^{2}, {x}_{i}, {y}_{1}, 1 \right]}^{\top}$.

In order to guarantee the 2nd order polynomial matches Ellipse (Avoid Parabola / Hyperbola) one can enforce $ {b}^{2} - 4 a c < 0 $.

Which yields:

$$ \begin{align*} \arg \min_{\boldsymbol{s}} \quad & \frac{1}{2} {\left\| \boldsymbol{Z} \boldsymbol{s} \right\|}_{2}^{2} \\ \text{subject to} \quad & \begin{aligned} \boldsymbol{s}^{\top} \boldsymbol{C} \boldsymbol{s} & = 1 \\ \end{aligned} \end{align*}, \quad \boldsymbol{C} = \begin{bmatrix} 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} $$

Since the solution for $\boldsymbol{s}$ holds up to scaling, one could force any positive value on $\boldsymbol{s}^{\top} \boldsymbol{C} \boldsymbol{s}$ to force the inequality.

The above is not a Convex Problem (Though it can be solved efficiently) as the equality constraint is not linear and $\boldsymbol{C}$ is indefinite.
On top of that, as known, using Least Squares formulation is highly sensitive to outliers.
One way to make it robust is using a robust formulation by utilizing the ${L}_{1}$ norm (See Least Absolute Deviation (LAD) Line Fitting / Regression (Robust Regression):

$$ \begin{align*} \arg \min_{\boldsymbol{s}} \quad & {\left\| \boldsymbol{Z} \boldsymbol{s} \right\|}_{1} \\ \text{subject to} \quad & \begin{aligned} \boldsymbol{s}^{\top} \boldsymbol{C} \boldsymbol{s} & = 1 \\ \end{aligned} \end{align*} $$

You may formulate it as:

$$ \begin{align*} \arg \min_{\boldsymbol{s}} \quad & {\left\| \boldsymbol{Z} \boldsymbol{s} \right\|}_{1} \\ \text{subject to} \quad & \begin{aligned} 1 - \boldsymbol{s}^{\top} \boldsymbol{C} \boldsymbol{s} & \leq 0 \\ \end{aligned} \end{align*} $$

Formulate it as a Lagrangian and use ADMM based method solve.
The issue is this direct solution is numerically not stable for the case all points are practically noiseless as in your case.
If you check your code, the condition number of $\boldsymbol{D}$ is extreme.

One way to overcome it is to use the formulation in Radim Halir, Jan Flusser - Numerically Stable Direct Least Squares Fitting of Ellipses.

Remarks:

• In practice, when solving the original formulation of the problem, normalizing the data to have zero mean and unit variance (Columns of $\boldsymbol{Z}$).
• It seems your derivation is taken from Gang Zhou, Kai Zhong, Zhongwei Li, Yusheng Shi - Direct Least Absolute Deviation Fitting of Ellipses. They also created a formulation using the ${L}_{0}$ Pseudo Norm: Direct Ellipse Fitting by Minimizing the L0 Algebraic Distance.