Least squares (least_squares) in SciPy - Time & Space Complexity

Time Complexity: Least squares (least_squares)

O(k * m * n)

Understanding Time Complexity

We want to understand how the time needed to solve a least squares problem grows as the problem size increases.

Specifically, how does the solver's work change when we have more data points or variables?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from scipy.optimize import least_squares
import numpy as np

def fun(x, A, b):
    return A @ x - b

A = np.random.rand(1000, 10)
b = np.random.rand(1000)
x0 = np.zeros(10)

res = least_squares(fun, x0, args=(A, b))
    

This code solves a least squares problem to find x that best fits A x = b.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Multiplying matrix A by vector x repeatedly during optimization.
• How many times: This happens many times as the solver iterates to improve the solution.

How Execution Grows With Input

As the number of rows (data points) or columns (variables) in A grows, the work to multiply and update grows too.

Input Size (n rows)	Approx. Operations
10	Thousands
100	Hundreds of thousands
1000	Millions

Pattern observation: The work grows roughly with the product of rows and columns, so bigger problems take much more time.

Final Time Complexity

Time Complexity: O(k * m * n)

This means the time grows with the number of iterations k, the number of data points m, and the number of variables n.

Common Mistake

[X] Wrong: "The solver runs in constant time no matter how big the data is."

[OK] Correct: The solver must process all data points and variables multiple times, so bigger problems take more time.

Interview Connect

Understanding how least squares solvers scale helps you explain performance in real data fitting tasks.

This skill shows you can think about how algorithms behave with bigger data, a key part of data science work.

Self-Check

"What if we changed the solver to use a sparse matrix for A? How would the time complexity change?"

Practice

1. What is the main purpose of using scipy.optimize.least_squares in data science?

easy

A. To find the best fit parameters by minimizing the difference between model predictions and data

B. To sort data points in ascending order

C. To calculate the mean of a dataset

D. To generate random numbers for simulations

Solution

1. Step 1: Understand the purpose of least squares

   Least squares is used to find parameters that minimize the error between a model and observed data.

2. Step 2: Match the purpose with the options

   Only To find the best fit parameters by minimizing the difference between model predictions and data describes minimizing differences to find best fit parameters.

3. Final Answer:

   To find the best fit parameters by minimizing the difference between model predictions and data -> Option A

4. Quick Check:

   Least squares = minimize error [OK]

Hint: Least squares minimizes errors to fit data best [OK]

Common Mistakes:

• Confusing least squares with sorting or averaging
• Thinking it generates random data
• Assuming it calculates statistics like mean

2. Which of the following is the correct way to call scipy.optimize.least_squares with a residual function fun and initial guess x0?

easy

A. least_squares(fun=x0, x0=fun)

B. least_squares(x0, fun)

C. least_squares(fun, x0)

D. least_squares(x0)

Solution

1. Step 1: Recall the function signature

   The correct call is least_squares(fun, x0) where fun is the residual function and x0 is the initial guess.

2. Step 2: Check each option

   least_squares(fun, x0) matches the correct order and parameters. Others have wrong order or missing arguments.

3. Final Answer:

   least_squares(fun, x0) -> Option C

4. Quick Check:

   Function first, initial guess second [OK]

Hint: Function first, initial guess second in least_squares call [OK]

Common Mistakes:

• Swapping the order of arguments
• Passing only one argument
• Using keyword arguments incorrectly

3. What will be the output of this code snippet?

import numpy as np
from scipy.optimize import least_squares

def residuals(x):
    return np.array([2*x[0] - 4, x[1] + 3])

result = least_squares(residuals, x0=[0, 0])
print(result.x)

medium

A. [-2.0, 3.0]

B. [4.0, 3.0]

C. [0.0, 0.0]

D. [2.0, -3.0]

Solution

1. Step 1: Understand the residual function

   The residuals are [2*x0 - 4, x1 + 3]. We want to find x that makes residuals close to zero.

2. Step 2: Solve equations for zero residuals

   Set 2*x0 - 4 = 0 => x0 = 2; and x1 + 3 = 0 => x1 = -3.

3. Final Answer:

   [2.0, -3.0] -> Option D

4. Quick Check:

   Zero residuals at x=[2, -3] [OK]

Hint: Set residuals to zero and solve for variables [OK]

Common Mistakes:

• Not solving residual equations correctly
• Confusing signs in equations
• Assuming initial guess is the answer

4. Identify the error in this code using least_squares:

import numpy as np
from scipy.optimize import least_squares

def residuals(x):
    return 2*x - 5

result = least_squares(residuals, x0=3)
print(result.x)

medium

A. Initial guess x0 should be a list or array, not a scalar

B. Residual function returns a scalar instead of an array

C. Missing import statement for numpy

D. least_squares requires a Jacobian function

Solution

1. Step 1: Check residual function output

   The residual function returns 2*x - 5, which is a scalar, but least_squares expects an array-like residual.

2. Step 2: Verify other parts

   x0 as scalar is allowed; numpy is imported; Jacobian is optional.

3. Final Answer:

   Residual function returns a scalar instead of an array -> Option B

4. Quick Check:

   Residuals must be array-like [OK]

Hint: Residuals must be array, not single number [OK]

Common Mistakes:

• Returning scalar residual instead of array
• Thinking initial guess must be array
• Assuming Jacobian is mandatory

5. You have noisy data points for a line: x = [0,1,2,3], y = [1.1, 2.0, 2.9, 4.2]. Using least_squares, which residual function best fits a line model y = m*x + c to estimate m and c?

hard

A. def residuals(p): return y - (p[0]*x + p[1])

B. def residuals(p): return p[0]*x + p[1]

C. def residuals(p): return (p[0]*x + p[1]) * y

D. def residuals(p): return y / (p[0]*x + p[1])

Solution

1. Step 1: Understand residuals for least squares

   Residuals are differences between observed y and model predictions m*x + c.

2. Step 2: Check residual function forms

   def residuals(p): return y - (p[0]*x + p[1]) returns y - model prediction (m*x + c), the standard residuals to minimize. def residuals(p): return p[0]*x + p[1] returns only the model predictions without subtracting y, so it minimizes the sum of squared model values instead of fitting errors.

3. Step 3: Eliminate incorrect options

   Options C and D multiply or divide, which is incorrect for residuals.

4. Final Answer:

   def residuals(p): return y - (p[0]*x + p[1]) -> Option A

5. Quick Check:

   Residual = observed - predicted [OK]

Hint: Residual = observed minus predicted values [OK]

Common Mistakes:

• Using multiplication or division instead of subtraction
• Forgetting to subtract the observed values
• Ignoring residuals should be array differences