Section 6.5: Least-Squares Problems

Definition: If 𝐴 is an 𝑚×𝑛 matrix and 𝑏∈ℝ𝑚, then a least-squares solution of 𝐴𝑥=𝑏 is 𝑥̂∈ℝ𝑛 such that?

||𝑏−𝐴𝑥̂||≤||𝑏−𝐴𝑥||

Inconsistent systems often arise in applications, meaning we cannot solve 𝐴𝑥=𝑏 (that is, 𝑏 is not in the range of 𝐴, or 𝑏∉𝐶𝑜𝑙𝐴.) Instead, we can find the value 𝑥̂ so that?

𝐴𝑥̂ is closest to 𝑏.

𝐴^𝑇𝐴𝑥̂=?

𝐴^𝑇𝑏

The system of equations 𝐴^𝑇𝐴𝑥̂=𝐴^𝑇𝑏 is called_____.

the normal equations for Ax=b

Theorem: The set of least-squares solutions of 𝐴𝑥=𝑏 coincides _______

with the nonempty set of solutions of the normal equations 𝐴^𝑇𝐴𝑥=𝐴^𝑇𝑏.

Theorem: Let 𝐴 be an 𝑚×𝑛 matrix. The following are equivalent:

a. 𝐴𝑥=𝑏 has a unique ______solution

b. The columns of 𝐴 are ______.

c. The matrix 𝐴^𝑇𝐴 is ______.

When these are true, the least-squares solution is ?.

a. least-squares

b. linearly independent

c. invertible

𝑥̂=(𝐴^𝑇𝐴)⁻¹𝐴^𝑇𝑏

Definition: The least-squares error is the distance ?

||𝑏−𝐴𝑥̂||

Theorem: Given an 𝑚×𝑛 matrix 𝐴 with linearly independent columns, let 𝐴=𝑄𝑅 be a 𝑄𝑅 factorization of 𝐴. Then for each 𝑏∈ℝ𝑚, the equation 𝐴𝑥=𝑏 has a unique least-squares solution given by ?.

𝑥̂=𝑅⁻¹𝑄^𝑇𝑏

Linear Regression: Given a set of data points, we want to find the line that best fits the data. That is, a line 𝑦=? that minimizes the error between the observed values (𝑥_𝑖,𝑦_𝑖) and the predicted values, called the “residuals.”

𝑦=𝛽₀+𝛽₁𝑥

(T/F) The general least-squares problem is to find an x that makes Ax as close as possible to b.

true

(T/F) If b is in the column space of A, then every solution of Ax=b is a least-squares solution.

true

(T/F) A least-squares solution of Ax=b is a vector xˆ that satisfies Axˆ=bˆ, where bˆ is the orthogonal projection of b onto Col A.

true

(T/F) A least-squares solution of Ax=b is a vector xˆ such that ∥b−Ax∥≤∥b−Axˆ∥ for all x in ℝn.

true

T/F) Any solution of ATAx=ATb is a least-squares solution of Ax=b.

true

(T/F) If the columns of A are linearly independent, then the equation Ax=b has exactly one least-squares solution.

true

(T/F) The least-squares solution of Ax=b is the point in the column space of A closest to b.

true

(T/F) A least-squares solution of Ax=b is a list of weights that, when applied to the columns of A, produces the orthogonal projection of b onto Col A.

true

(T/F) The normal equations always provide a reliable method for computing least-squares solutions.

false

(T/F) If A has a QR factorization, say A=QR, then the best way to find the least-squares solution of Ax=b is to compute xˆ=R−1QTb.

true