Line Fitting

You want to find the line $y = mx + b$ that best fits a set of points $(x_i, y_i)$ by minimizing the sum of squared vertical errors:

$$E(m,b) = \sum_i (y_i - (mx_i + b))^2.$$

This is a classic linear least squares problem, whose solution can be derived from the normal equations of linear regression.

---

1. Background Knowledge (Key Concepts)

• Least squares idea You have noisy data points and want a model (here, a line) that explains them “on average” as well as possible. Least squares chooses parameters $m, b$ to minimize the sum of squared residuals (vertical differences between observed $y_i$ and predicted $\hat y_i = mx_i + b$). This gives a closed-form solution for linear models.

• Linear model as matrix equation Write the model in vector/matrix form:

$$\mathbf{y} \approx X\boldsymbol{\theta}, \quad\text{where}\quad \boldsymbol{\theta} = \begin{bmatrix} m \\ b \end{bmatrix}, \; X= \begin{bmatrix} x_1 & 1 \\ x_2 & 1 \\ \vdots & \vdots \\ x_n & 1 \end{bmatrix}, \; \mathbf{y}= \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix}.$$

The least squares solution minimizes $\|$\mathbf{y} - X\boldsymbol{\theta}\|^2.

• Normal equations Setting the gradient of the error to zero leads to the normal equations:

$$X^\top X \,\boldsymbol{\theta} = X^\top \mathbf{y}.$$

For a 2-parameter line, this is a $2\times 2$ linear system in $m$ and $b$ that you can solve analytically or numerically.

---

2. Algorithm / General Approach

For this kind of 1D line-fitting least squares problem, the general pattern is:

1. Set up the design matrix $X$ from your input data (one column for $x$, one column of 1s for the intercept).
2. Form the normal equations X^\top X \boldsymbol{\theta} = X^\top y.
3. Solve the small linear system for \boldsymbol{\theta} = [m, b]^T.
4. Use $m$ and $b$ to define your fitted line.

In practice, for a simple line you can also derive explicit formulas for $m$ and $b$ using sums of $x_i, y_i, x_i^2, x_i y_i$, but conceptually it’s the same as solving the normal equations.

---

3. Step-by-Step Strategy (Implementation View)

Assume you’re given arrays x[i], y[i] for $i = 1 \dots n$.

A. Using explicit sums (common in coding problems)

1. Compute aggregate sums

• $S_x =$\sum$_i x_i$
• $S_y =$\sum$_i y_i$
• $S_{xx} =$\sum$_i x_i^2$
• $S_{xy} =$\sum$_i x_i y_i$

2. Compute denominator

• $D = n S_{xx} - S_x^2$.

3. Solve for parameters

• $m = \dfrac{n S_{xy} - S_x S_y}{D}$
• $b = \dfrac{S_y S_{xx} - S_x S_{xy}}{D}$

4. Return or print $m$ and $b$ as the result.

B. Using the normal equations formulation (for understanding)

1. Construct:

# Conceptually:
X = [[x1, 1],
[x2, 1],
...
[xn, 1]]
y = [y1, y2,..., yn]

2. Compute:

$$A = X^\top X,\quad c = X^\top y$$

(in code, these are just sum combinations as above). 3. Solve the 2×2 system $A$\theta$= c$ for $\theta = [m, b]^T$.

---

4. Common Pitfalls

• Degenerate or nearly degenerate data

• If all $x_i$ are identical, then the denominator $D$ becomes zero: a vertical line cannot be represented as $y = mx + b$. You should handle this edge case explicitly if it can occur.

• Integer vs float division

• In many languages, dividing integers does integer division by default. Ensure you cast to floating point before division so $m$ and $b$ are not truncated.

• Overflow / precision

• For very large coordinates or many points, sums like $S_{xx}$ can get large. In typical coding problems this is usually within safe bounds, but be aware and use appropriate numeric types (e.g., double).

• Off-by-one errors

• Make sure your loop runs over all points, and that n is the actual number of points used in the sums.

---

5. Time & Space Complexity

• Time complexity

• You compute a constant number of sums in a single pass over the data.

• Complexity: $O(n)$ where $n$ is the number of points.

• Space complexity

• If you just iterate over the points and maintain running sums, you use a constant amount of extra memory.

• Complexity: $O(1)$ auxiliary space (aside from the input arrays).