Week 5-6

Chapter 4: Model Fitting and Optimization

Techniques for fitting models to data, handling outliers with RANSAC, and using regularization methods like Total Variation for robust computer vision.

Chapter Overview

Computer vision often requires finding mathematical models that explain observed data—whether it's a line through detected edge points, a transformation between images, or a surface representing an object. But real-world data is messy: sensors are noisy, features are misdetected, and outliers corrupt our measurements.

What is this chapter about? We study model fitting: given noisy, imperfect observations, how do we find the underlying model? This is fundamental to nearly every computer vision pipeline.

Why does this matter? Without robust fitting techniques, a single bad measurement can completely ruin your results. Imagine fitting a line to detected lane markers—one misdetection shouldn't send your self-driving car off the road.

How the topics connect: We start with Least Squares—the classic approach that works great when data is clean. Then we learn RANSAC, which elegantly handles outliers by finding consensus among the data. Finally, Total Variation shows how regularization can guide solutions toward realistic, edge-preserving results.

Chapter Roadmap

Click any topic to jump in

Least Squares

Linear regression, normal equations, and residuals — fitting models to data by minimizing error.

Least Squares CriterionNormal EquationsResiduals

Handling real-world data

Outlier robustness and regularization

RANSAC

Random sampling for robust fitting — handling outliers that break least squares.

RANSAC AlgorithmInlier ThresholdNumber of Iterations

Regularization

Total variation, ROF model, and edge preservation — adding priors to prevent overfitting.

Total VariationROF ModelEdge Preservation

We begin with the most fundamental fitting technique: least squares. When your data is mostly clean, this elegant approach gives you the mathematically optimal solution in closed form. Understanding least squares is essential because it forms the foundation for more advanced methods.

In this topic

1Least Squares Criterion

2Normal Equations

3Residuals

1 of 3

Least Squares Criterion

$E = \sum_i (y_i - f(x_i))^2$

The least squares criterion minimizes the sum of squared residuals—the vertical distances from data points to the fitted curve, squared and summed. Here:

$y_i$ is the observed value at point $i$
$f(x_i)$ is the model's prediction at that point
The squaring penalizes large errors more heavily than small ones

This is the optimal solution when errors are normally distributed (Gaussian noise). However, it's sensitive to outliers because squaring amplifies large deviations. A single outlier can dramatically shift the fitted line.

Mathematical Intuition

The least squares objective $E = \sum_i (y_i - f(x_i))^2 = \|\mathbf{b} - \mathbf{A}\mathbf{x}\|_2^2$ minimizes the squared $L^2$ norm of the residual vector. Setting the gradient $\nabla_\mathbf{x} E = -2 \mathbf{A}^T (\mathbf{b} - \mathbf{A}\mathbf{x}) = 0$ yields the normal equations. The quadratic form $E(\mathbf{x})$ defines a paraboloid in parameter space with a unique minimum when $\mathbf{A}^T \mathbf{A}$ is positive definite. Squaring penalizes large residuals disproportionately — a single outlier at distance $d$ contributes $d^2$ to the cost, giving it leverage proportional to $d^2$ on the solution.

Example:

Points (1,2), (2,3), (3,5) are fit with line y=x+1. Calculate the sum of squared errors.

2 of 3

Normal Equations

$(\mathbf{A}^T\mathbf{A})\mathbf{x} = \mathbf{A}^T\mathbf{b}$

The normal equations provide a closed-form solution to the least squares problem:

$\mathbf{A}$ is the design matrix, where each row contains features for one data point (e.g., $[x_i, 1]$ for linear regression)
$\mathbf{x}$ is the vector of parameters we're solving for (e.g., slope and intercept)
$\mathbf{b}$ is the vector of observed outputs (y values)
$\mathbf{A}^T$ is the transpose of $\mathbf{A}$

The solution is $\mathbf{x} = (\mathbf{A}^T\mathbf{A})^{-1}\mathbf{A}^T\mathbf{b}$ , which can be computed directly using matrix operations. This is efficient for small to medium datasets but can be numerically unstable for ill-conditioned problems.

Mathematical Intuition

The normal equations $(\mathbf{A}^T \mathbf{A})\mathbf{x} = \mathbf{A}^T \mathbf{b}$ project the observation vector $\mathbf{b}$ onto the column space of $\mathbf{A}$ . Geometrically, $\hat{\mathbf{b}} = \mathbf{A}\mathbf{x}$ is the point in $\text{col}(\mathbf{A})$ closest to $\mathbf{b}$ , and the residual $\mathbf{b} - \hat{\mathbf{b}}$ is orthogonal to every column of $\mathbf{A}$ — hence the name "normal" equations. The condition number $\kappa(\mathbf{A}^T\mathbf{A}) = \kappa(\mathbf{A})^2$ means numerical errors are amplified quadratically; for ill-conditioned problems, the SVD-based pseudoinverse $\mathbf{x} = \mathbf{A}^+ \mathbf{b}$ or QR decomposition is preferred.

Example:

For points (0,1), (1,3), write the design matrix A for fitting y=ax+b.

3 of 3

Residuals

$r_i = y_i - \hat{y}_i$

Residuals are the differences between observed values ( $y_i$ ) and predictions ( $\hat{y}_i$ ). Analyzing residuals helps validate your model:

Random scatter around zero: Good fit, model captures the pattern
Curved pattern: Model is missing nonlinear structure
Increasing spread: Heteroscedasticity—variance changes with $x$
Clustering: Possible outliers or model inadequacy

The sum of residuals in linear regression always equals zero, but the sum of squared residuals (RSS) measures overall fit quality.

Mathematical Intuition

The residual vector $\mathbf{r} = \mathbf{b} - \mathbf{A}\hat{\mathbf{x}}$ lies in the left null space of $\mathbf{A}$ (orthogonal complement of the column space). For a correctly specified linear model with i.i.d. Gaussian noise $\epsilon_i \sim \mathcal{N}(0, \sigma^2)$ , the residuals follow $\mathbf{r} \sim \mathcal{N}(\mathbf{0}, \sigma^2 (\mathbf{I} - \mathbf{H}))$ where $\mathbf{H} = \mathbf{A}(\mathbf{A}^T\mathbf{A})^{-1}\mathbf{A}^T$ is the hat matrix. The unbiased estimator $\hat{\sigma}^2 = \|\mathbf{r}\|^2 / (n - p)$ uses $n - p$ degrees of freedom because the projection $\mathbf{H}$ consumes $p$ of the $n$ original dimensions.

Example:

Fitted line predicts [10, 20, 30] but actual values are [12, 19, 32]. Compute residuals and RSS.

Theory Exercise

Problem:

Given 3 data points: (1, 2), (2, 4), (3, 5), fit a line y = ax + b using least squares. Calculate the optimal values of a and b.

Hints:

Set up the sums: Σx, Σy, Σxy, Σx²
Use the formulas: a = (nΣxy - ΣxΣy)/(nΣx² - (Σx)²)
Then: b = (Σy - aΣx)/n

Blogs

Ordinary Least Squares — Wikipedia

Image Processing

Deep Learning

Chapter 4: Model Fitting and Optimization

Chapter Overview

Chapter Roadmap

Least Squares

RANSAC

Regularization

Linear Regression and Least Squares

In this topic

Least Squares Criterion

Normal Equations

Residuals

Theory Exercise

Problem:

Hints:

RANSAC (Random Sample Consensus)

Total Variation and Regularization