📘

Weighted Least Squares

HardOptimization 📚 CV: Model Fitting and Optimization

Implement a weighted least squares method to fit a line to a set of points, where each point has a weight indicating its importance. This technique is crucial in model fitting and optimization as it allows for more accurate predictions by giving more influence to certain points.

The concept of weighted least squares is an extension of the ordinary least squares method, which minimizes the sum of the squared errors between observed responses and predicted responses. In weighted least squares, each point is assigned a weight $w_i$ , and the goal is to minimize the weighted sum of the squared errors $E = \sum_i w_i(y_i - (mx_i + b))^2$ .

Here are the steps to achieve this:

Calculate the weighted sum of $x$ values, $y$ values, $x^2$ values, and $xy$ values.
Use these weighted sums to calculate the slope $m$ and intercept $b$ of the line.

E = \sum_i w_i(y_i - (mx_i + b))^2

This technique is widely used in computer vision applications.

Example:

Input:

weighted_fit_line([(0,0,1), (1,2,1), (2,2,2)])

Output:

[1.0, 0.25]

Reasoning:

First, list the data with weights: $(x_i, y_i, w_i) = (0,0,1), (1,2,1), (2,2,2)$ , and compute weighted sums: $\sum w_i = 4$ , $\sum w_ix_i = 0\cdot1 + 1\cdot1 + 2\cdot2 = 5$ , $\sum w_iy_i = 0\cdot1 + 2\cdot1 + 2\cdot2 = 6$ , $\sum w_ix_i^2 = 0^2\cdot1 + 1^2\cdot1 + 2^2\cdot2 = 9$ , $\sum w_ix_iy_i = 0\cdot0\cdot1 + 1\cdot2\cdot1 + 2\cdot2\cdot2 = 12$ .
Then, use the weighted least squares formulas for slope $m$ and intercept $b$ :
- $m = \dfrac{\sum w_i x_i y_i - \frac{1}{\sum w_i}(\sum w_i x_i)(\sum w_i y_i)}{\sum w_i x_i^2 - \frac{1}{\sum w_i}(\sum w_i x_i)^2} = \dfrac{12 - \frac{5\cdot6}{4}}{9 - \frac{5^2}{4}} = \dfrac{4.5}{4.5} = 1.0$
- $b = \dfrac{\sum w_i y_i - m \sum w_i x_i}{\sum w_i} = \dfrac{6 - 1\cdot5}{4} = 0.25$
The final output is the fitted line parameters $[m, b] = [1.0, 0.25]`.

Constraints:

points is a list of (x, y, weight) tuples
Return [m, b] rounded to 4 decimal places

More from CV: Model Fitting and Optimization

RANSAC Homography EstimationMedium RANSAC Line FittingMedium RANSAC Line FitHard Line from Two PointsEasy Count InliersEasy

Weighted Least Squares: Background and Implementation Guide

Background Knowledge

Ordinary Least Squares (OLS) Foundation

Ordinary least squares is a fundamental technique for fitting a line to data by minimizing the sum of squared residuals: $\sum_i (y_i - (mx_i + b))^2$ . This approach treats all data points equally, assuming they have equal reliability or importance. However, in real-world scenarios, measurements often have different levels of uncertainty or importance. Some observations may come from more reliable instruments, have lower measurement error, or represent more critical cases than others.

Weighted Least Squares (WLS) Extension

Weighted least squares extends OLS by introducing weights $w_i$ for each point, creating the objective function you've described: $E =$ \sum $_i w_i(y_i - (mx_i + b))^2$ . The weights allow you to control how much each residual contributes to the total error. Points with higher weights have larger residuals penalized more heavily, effectively "pulling" the fitted line closer to those points. This is particularly useful when dealing with heteroscedastic data (unequal error variances) or when you have prior knowledge about measurement reliability.

Mathematical Intuition

The key insight is that WLS can be viewed as an optimization problem where you're finding the line that minimizes a weighted sum of squared errors. Geometrically, this is equivalent to solving a system of linear equations derived from setting the partial derivatives of $E$ with respect to $m$ and $b$ equal to zero. The solution involves matrix operations that incorporate the weight information directly into the fitting process.

Algorithm/Approach

The standard approach to solving WLS involves calculus-based optimization:

Formulate the objective function with weights incorporated
Take partial derivatives with respect to the unknown parameters ( $m$ and $b$ )
Set derivatives to zero to find the critical points (normal equations)
Solve the resulting system of linear equations to obtain optimal parameters

Alternatively, you can use a matrix-based approach where the problem is reformulated as: $\mathbf{w}^{1/2}$ \mathbf{y} $=$ \mathbf{w} $^{1/2}$ \mathbf{X} $\boldsymbol{$ \beta $}$ , transforming the weighted problem into an unweighted one that can be solved using standard linear algebra techniques.

Step-by-Step Strategy

Step 1: Set up the normal equations

Take the partial derivatives of $E$ with respect to $m$ and $b$ :

$\frac{$ \partial $E}{$ \partial $m} = -2$ \sum $_i w_i x_i(y_i - mx_i - b) = 0$
$\frac{$ \partial $E}{$ \partial $b} = -2$ \sum $_i w_i(y_i - mx_i - b) = 0$

Step 2: Rearrange into standard form

Expand and rearrange the equations to isolate terms involving $m$ and $b$ :

$m$ \sum $_i w_i x_i^2 + b$ \sum $_i w_i x_i =$ \sum $_i w_i x_i y_i$
$m$ \sum $_i w_i x_i + b$ \sum $_i w_i =$ \sum $_i w_i y_i$

Step 3: Express as a matrix equation

Write this system in matrix form: $\mathbf{A}\boldsymbol{$ \beta $} = \mathbf{c}$ , where $\boldsymbol{$ \beta $} = [m, b]^T$

Step 4: Solve the linear system

Use standard linear algebra techniques (Gaussian elimination, matrix inversion, or numerical solvers) to find $m$ and $b$

Step 5: Validate your solution

Verify that the computed line minimizes the weighted error by checking that the residuals are reasonable and the solution makes intuitive sense (points with higher weights should be closer to the fitted line)

Common Pitfalls

Numerical instability: When weights vary dramatically in magnitude, the matrix system can become ill-conditioned. Consider normalizing weights or using robust numerical methods.
Zero or negative weights: Ensure all weights are positive. Zero weights effectively remove points from consideration, which may be intentional but should be handled explicitly.
Forgetting the weight matrix structure: The weights must be incorporated into every summation in the normal equations. Missing a weight in even one term will produce incorrect results.
Matrix singularity: If your design matrix is singular (e.g., all $x$ values are identical), the system has no unique solution. Check for degenerate cases.
Floating-point precision: When computing sums of weighted products, accumulate errors can occur. Consider using higher precision arithmetic if needed.

Time & Space Complexity

Time Complexity: $O(n)$ for computing the sums needed for the normal equations, plus $O(1)$ for solving the 2×2 linear system (since you have exactly two unknowns). Overall: $O(n)$
Space Complexity: $O(1)$ if you accumulate sums iteratively, or $O(n)$ if you store all intermediate values. The matrix system itself is constant size (2×2).

The linear time complexity makes WLS highly efficient even for large datasets, making it practical for real-world applications where you need to incorporate measurement reliability information into your model fitting process.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.