- Home
- Linear Algebra
- Orthogonality and Least Squares
Least-squares problem
- Intro Lesson: a23:32
- Intro Lesson: b5:26
- Intro Lesson: c24:13
- Lesson: 16:36
- Lesson: 216:21
- Lesson: 35:40
- Lesson: 49:20
- Lesson: 511:17
Least-squares problem
Lessons
In linear algebra, we have dealt with questions in which Ax=b does not have a solution. When a solution does not exist, the best thing we can do is to approximate x. In this section, we will learn how to find a x such that it makes Ax as close as possible to b.
If A is an m×n matrix and b is a vector in Rn, then a least-squares solution of Ax=b is a x^ in Rn where
∥b−Ax^∥≤∥b−Ax∥
For all x in Rn.
The smaller the distance, the smaller the error. Thus, the better the approximation. So the smallest distance gives the best approximation for x. So we call the best approximation for x to be x^.
The Least-Squares Solution
The set of least-square solutions of Ax=b matches with the non-empty set of solutions of the matrix equation ATAx^=ATb.
In other words,
ATAx^=ATb
→x^=(ATA)−1ATb
Where x is the least square solutions of Ax=b.
Keep in mind that x is not always a unique solution. However, it is unique if one of the conditions hold:
1. The equation Ax=b has unique least-squares solution for each b in Rm.
2. The columns of A are linearly independent.
3. The matrix ATA is invertible.
The Least-Squares Error
To find the least-squares error of the least-squares solution of Ax=b, we compute
∥b−Ax^∥
Alternative Calculations to Least-Squares Solutions
Let A be a m×n matrix where a1,⋯,an are the columns of A. If Col(A)={a1,⋯,an} form an orthogonal set, then we can find the least-squares solutions using the equation
Ax^=b^
where b^=projCol(A)b.
Let A be a m×n matrix with linearly independent columns, and let A=QR be the QR factorization of A. Then for each b in Rm, the equation Ax=b has a unique least-squares solution where
x^=R−1QTb
→Rx^=QTb
If A is an m×n matrix and b is a vector in Rn, then a least-squares solution of Ax=b is a x^ in Rn where
For all x in Rn.
The smaller the distance, the smaller the error. Thus, the better the approximation. So the smallest distance gives the best approximation for x. So we call the best approximation for x to be x^.
The Least-Squares Solution
The set of least-square solutions of Ax=b matches with the non-empty set of solutions of the matrix equation ATAx^=ATb.
In other words,
→x^=(ATA)−1ATb
Where x is the least square solutions of Ax=b.
Keep in mind that x is not always a unique solution. However, it is unique if one of the conditions hold:
1. The equation Ax=b has unique least-squares solution for each b in Rm.
2. The columns of A are linearly independent.
3. The matrix ATA is invertible.
The Least-Squares Error
To find the least-squares error of the least-squares solution of Ax=b, we compute
Alternative Calculations to Least-Squares Solutions
Let A be a m×n matrix where a1,⋯,an are the columns of A. If Col(A)={a1,⋯,an} form an orthogonal set, then we can find the least-squares solutions using the equation
where b^=projCol(A)b.
Let A be a m×n matrix with linearly independent columns, and let A=QR be the QR factorization of A. Then for each b in Rm, the equation Ax=b has a unique least-squares solution where
→Rx^=QTb
- IntroductionLeast Squares Problem Overview:a)The Least Squares Solution
• Ax=b give no solution
• Approximate closest solution x^
• The least Squares Solution x^=(ATA)−1ATb
• Not always a unique solutionb)The Least Squares Error
• Finding the error of the solution x^
• Use the formula ∥b−Ax^∥c)Alternative Calculation to Least-Squares Solutions
• Orthogonal columns of A→Ax^=b^
• QR factorization A=QR→Rx^=QTb - 1.Finding the Least Squares Solutions with ATAx^=ATb
Find a least-squares solution of Ax=b if
- 2.Describe all least-squares solutions of equation Ax=b if
- 3.Finding the Least Squares Error
You are given that the least-squares solution of Ax=b is. Compute the least-square error if
- 4.Finding the Least Squares Solutions with Alternative Ways
Find the orthogonal projections of b onto the columns of A and find a least-squares solution of Ax=b.
- 5.Use the factorization A=QR to find the least-squares solution of Ax=b