MATH 685/ CSI 700/ OR 682 Lecture Notes Lecture 4. Least squares
Method of least squares Measurement errors are inevitable in observational and experimental sciences
Errors can be smoothed out by averaging over many cases, i.e., taking more measurements than are strictly necessary to determine parameters of system Resulting system is overdetermined, so usually there is no exact
solution In effect, higher dimensional data are projected into lower dimensional space to suppress irrelevant detail Such projection is most conveniently accomplished by
method of least squares Linear least squares
Data fitting Data fitting
Example Example
Example Existence/Uniqueness
Normal Equations Orthogonality
Orthogonality Orthogonal Projector
Pseudoinverse Sensitivity and Conditioning
Sensitivity and Conditioning Solving normal equations
Example Example
Shortcomings Augmented system method
Augmented system method Orthogonal Transformations
Triangular Least Squares Triangular Least Squares
QR Factorization Orthogonal Bases
Computing QR factorization To compute QR factorization of m n matrix A, with m > n, we
annihilate subdiagonal entries of successive columns of A, eventually reaching upper triangular form
Similar to LU factorization by Gaussian elimination, but use orthogonal transformations instead of elementary elimination matrices
Possible methods include
Householder transformations Givens rotations Gram-Schmidt orthogonalization
Householder Transformation Example
Householder QR factorization Householder QR factorization
Householder QR factorization For solving linear least squares problem, product Q of Householder transformations need not be formed explicitly
R can be stored in upper triangle of array initially containing A
Householder vectors v can be stored in (now zero) lower triangular portion of A (almost)
Householder transformations most easily applied in this form anyway
Example Example
Example Example
Givens Rotations Givens Rotations
Example Givens QR factorization
Givens QR factorization Straightforward implementation of Givens method requires about 50% more work than Householder method, and also
requires more storage, since each rotation requires two numbers, c and s, to define it
These disadvantages can be overcome, but requires more complicated implementation
Givens can be advantageous for computing QR factorization when many entries of matrix are already zero, since those annihilations can then be skipped
Gram-Schmidt orthogonalization Gram-Schmidt algorithm
Modified Gram-Schmidt Modified Gram-Schmidt
QR factorization Rank Deficiency If rank(A) < n, then QR factorization still exists, but yields
singular upper triangular factor R, and multiple vectors x give minimum residual norm
Common practice selects minimum residual solution x having smallest norm
Can be computed by QR factorization with column pivoting or by singular value decomposition (SVD)
Rank of matrix is often not clear cut in practice, so relative tolerance is used to determine rank
Near Rank Deficiency QR with Column Pivoting
QR with Column Pivoting Singular Value Decomposition
Example: SVD Applications of SVD
Pseudoinverse Orthogonal Bases
Lower-rank Matrix Approximation Total Least Squares
Ordinary least squares is applicable when right-hand side b is subject to random error but matrix A is known accurately
When all data, including A, are subject to error, then
total least squares is more appropriate
Total least squares minimizes orthogonal distances, rather than vertical distances, between model and data
Total least squares solution can be computed from SVD of [A, b]
Comparison of Methods Comparison of Methods
Comparison of Methods