Glossary

7.2 QR decomposition

5 min read•august 16, 2024

is a powerful matrix factorization technique that breaks down a matrix into an Q and an R. It's super useful for solving linear systems, least squares problems, and eigenvalue computations.

The is the classic way to compute QR decomposition. It works by orthogonalizing each column of the input matrix with respect to the previous columns. This method is key for understanding how QR decomposition actually works in practice.

QR Decomposition

Matrix Factorization and Properties

Top images from around the web for Matrix Factorization and Properties

  • Variational Quantum Singular Value Decomposition – Quantum View original

    Is this image relevant?

  • Variational Quantum Singular Value Decomposition – Quantum View original

    Is this image relevant?

1 of 2

Top images from around the web for Matrix Factorization and Properties

  • Variational Quantum Singular Value Decomposition – Quantum View original

    Is this image relevant?

  • Variational Quantum Singular Value Decomposition – Quantum View original

    Is this image relevant?

1 of 2
  • QR decomposition factorizes a matrix A into the product of an orthogonal matrix Q and an upper triangular matrix R
  • Unique for square matrices with non-zero diagonal elements in R
  • For an m × n matrix A, Q is m × m orthogonal, and R is m × n upper triangular
  • Q columns form an orthonormal basis for A's column space
  • Applications include solving linear systems, least squares problems, and eigenvalue computations (Singular Value Decomposition)
  • Preserves the rank of the original matrix A
  • Versatile for both square and rectangular matrices in various linear algebra problems

Mathematical Representation and Examples

  • Matrix factorization expressed as A=QRA = QR
  • Orthogonal matrix Q property: QTQ=QQT=IQ^TQ = QQ^T = I
  • Example for a 3x3 matrix A: A=[123456789]A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} Q=[−0.123−0.904−0.408−0.492−0.3010.816−0.8620.301−0.408]Q = \begin{bmatrix} -0.123 & -0.904 & -0.408 \\ -0.492 & -0.301 & 0.816 \\ -0.862 & 0.301 & -0.408 \end{bmatrix} R=[−8.124−9.817−11.5100−0.904−1.808000]R = \begin{bmatrix} -8.124 & -9.817 & -11.510 \\ 0 & -0.904 & -1.808 \\ 0 & 0 & 0 \end{bmatrix}
  • Rectangular matrix example (2x3): A=[123456]A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} Q=[−0.243−0.970−0.9700.243]Q = \begin{bmatrix} -0.243 & -0.970 \\ -0.970 & 0.243 \end{bmatrix} R=[−4.123−5.477−6.8310−0.730−1.460]R = \begin{bmatrix} -4.123 & -5.477 & -6.831 \\ 0 & -0.730 & -1.460 \end{bmatrix}

Gram-Schmidt Orthogonalization

Process and Implementation

  • Classical method for computing QR decomposition
  • Iteratively orthogonalizes each column of input matrix A with respect to previously orthogonalized columns
  • For each column vector a_k, computes projection onto subspace spanned by previous orthogonalized vectors
  • Subtracts projection from a_k to obtain orthogonal component, becoming k-th column of Q after normalization
  • Projection coefficients form elements of upper triangular matrix R
  • Implemented using classical or modified algorithms, with modified version offering better numerical stability
  • Computational complexity O(mn^2) for an m × n matrix

Mathematical Steps and Examples

  • Gram-Schmidt process for vectors u1, u2, ..., un:
    1. e1=u1∣∣u1∣∣e_1 = \frac{u_1}{||u_1||}
    2. e2=u2−(u2⋅e1)e1∣∣u2−(u2⋅e1)e1∣∣e_2 = \frac{u_2 - (u_2 \cdot e_1)e_1}{||u_2 - (u_2 \cdot e_1)e_1||}
    3. e3=u3−(u3⋅e1)e1−(u3⋅e2)e2∣∣u3−(u3⋅e1)e1−(u3⋅e2)e2∣∣e_3 = \frac{u_3 - (u_3 \cdot e_1)e_1 - (u_3 \cdot e_2)e_2}{||u_3 - (u_3 \cdot e_1)e_1 - (u_3 \cdot e_2)e_2||}
  • Example with 2x2 matrix: A=[3142]A = \begin{bmatrix} 3 & 1 \\ 4 & 2 \end{bmatrix}
    1. u1=[34],e1=125[34]=[0.60.8]u_1 = \begin{bmatrix} 3 \\ 4 \end{bmatrix}, e_1 = \frac{1}{\sqrt{25}}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}
    2. u2=[12],e2=[12]−2[0.60.8]0.22+0.42=[−0.80.6]u_2 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}, e_2 = \frac{\begin{bmatrix} 1 \\ 2 \end{bmatrix} - 2\begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}}{\sqrt{0.2^2 + 0.4^2}} = \begin{bmatrix} -0.8 \\ 0.6 \end{bmatrix} Resulting in: Q=[0.6−0.80.80.6],R=[5300.6]Q = \begin{bmatrix} 0.6 & -0.8 \\ 0.8 & 0.6 \end{bmatrix}, R = \begin{bmatrix} 5 & 3 \\ 0 & 0.6 \end{bmatrix}

Solving Least Squares Problems

QR Decomposition Method

  • Provides numerically stable method for solving linear least squares problems
  • Transforms least squares problem min ||Ax - b||_2 into solving Rx = Q^T b, where R is upper triangular
  • Solving transformed system computationally efficient due to triangular structure of R
  • Less sensitive to rounding errors compared to normal equations
  • QR with column improves numerical stability for rank-deficient or ill-conditioned matrices
  • Extended to solve weighted least squares problems by incorporating weight matrix
  • Used in iterative refinement procedures to improve accuracy of least squares solutions

Implementation and Examples

  • Steps to solve Ax = b using QR decomposition:
    1. Compute QR decomposition of A
    2. Calculate Q^T b
    3. Solve Rx = Q^T b using back-substitution
  • Example solving 3x2 system: A=[111213],b=[234]A = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}, b = \begin{bmatrix} 2 \\ 3 \\ 4 \end{bmatrix}
    1. QR decomposition: Q=[−0.577−0.4080.707−0.577−0.816−0.707−0.5770.4080],R=[−1.732−3.4640−1.41400]Q = \begin{bmatrix} -0.577 & -0.408 & 0.707 \\ -0.577 & -0.816 & -0.707 \\ -0.577 & 0.408 & 0 \end{bmatrix}, R = \begin{bmatrix} -1.732 & -3.464 \\ 0 & -1.414 \\ 0 & 0 \end{bmatrix}
    2. Calculate Q^T b: QTb=[−5.196−1.4140.707]Q^T b = \begin{bmatrix} -5.196 \\ -1.414 \\ 0.707 \end{bmatrix}
    3. Solve Rx = Q^T b: [−1.732−3.4640−1.414][x1x2]=[−5.196−1.414]\begin{bmatrix} -1.732 & -3.464 \\ 0 & -1.414 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} -5.196 \\ -1.414 \end{bmatrix} Resulting in x = [1, 1]^T

Stability of QR Decomposition

Numerical Properties and Advantages

  • Numerically stable, preferable to other matrix factorization methods in many applications
  • of Q always 1, contributing to overall stability of decomposition
  • and offer alternative methods to Gram-Schmidt with better numerical properties
  • Backward stability ensures small perturbations in input data result in small perturbations in computed factors
  • QR decomposition with column pivoting improves numerical stability for rank-deficient or ill-conditioned matrices
  • Loss of in Q due to finite precision arithmetic mitigated using reorthogonalization techniques
  • Relative error in computed R factor bounded by small multiple of machine epsilon, ensuring high accuracy in most practical applications

Comparison and Error Analysis

  • QR decomposition vs LU decomposition:
    • QR more stable for solving linear systems and least squares problems
    • LU faster for certain operations (matrix inversion)
  • Error bounds for QR decomposition:
    • For computed factors Q̂ and R̂: ∣∣A−Q^R^∣∣F≤c(m,n)ε∣∣A∣∣F||A - Q̂R̂||_F ≤ c(m,n)ε||A||_F where c(m,n) is a function of matrix dimensions and ε is machine epsilon
  • Example of improved stability:
    • Hilbert matrix (notoriously ill-conditioned): Hij=1i+j−1H_{ij} = \frac{1}{i+j-1}
    • Solving Hx = b using QR decomposition produces more accurate results than direct methods for increasing matrix sizes (4x4, 8x8, 16x16)

Key Terms to Review (18)

Condition Number: The condition number of a matrix is a measure of how sensitive the solution of a system of linear equations is to changes in the input data. It quantifies how much the output value can change for a small change in the input, indicating the stability and reliability of numerical computations. A high condition number suggests that the matrix is ill-conditioned, meaning that even small errors in data can lead to large errors in results, which is crucial in various applications including solving linear systems and decompositions.
Dimensionality Reduction: Dimensionality reduction is a process used to reduce the number of random variables under consideration, obtaining a set of principal variables. It simplifies models, making them easier to interpret and visualize, while retaining important information from the data. This technique connects with various linear algebra concepts, allowing for the transformation and representation of data in lower dimensions without significant loss of information.
Givens Rotations: Givens rotations are a mathematical technique used to zero out specific elements in a vector through a rotation in the plane spanned by two coordinates. This method is particularly useful in QR decomposition, where the goal is to transform a matrix into an orthogonal matrix and an upper triangular matrix, simplifying calculations in numerical linear algebra. By applying these rotations, it becomes easier to solve linear systems and perform least squares fitting.
Gram-Schmidt Process: The Gram-Schmidt process is a method used in linear algebra to orthogonalize a set of vectors in an inner product space, transforming them into an orthogonal or orthonormal set. This process not only simplifies computations in various applications, such as data analysis and numerical methods but also underlies the concept of constructing orthonormal bases, making it foundational for techniques like QR decomposition.
Householder reflections: Householder reflections are a type of linear transformation used to zero out certain components of a vector, effectively simplifying matrix operations. They play a key role in QR decomposition by transforming a given matrix into an upper triangular form, which makes it easier to solve linear systems and perform least squares approximations. This method involves constructing an orthogonal reflection matrix that alters the input vector while preserving its norm.
Least squares solution: The least squares solution is a mathematical approach used to find the best-fitting line or hyperplane for a set of data points by minimizing the sum of the squares of the vertical distances (residuals) between the data points and the line. This technique is essential in regression analysis and optimization, as it provides a way to handle situations where an exact solution may not exist, especially when the system of equations is overdetermined.
Linear Regression: Linear regression is a statistical method used to model the relationship between a dependent variable and one or more independent variables by fitting a linear equation to observed data. This technique is foundational in understanding how changes in predictor variables can affect an outcome, and it connects directly with concepts such as least squares approximation, vector spaces, and various applications in data science.
Matrix Rank: Matrix rank is the dimension of the vector space generated by its rows or columns, reflecting the maximum number of linearly independent row or column vectors in the matrix. It serves as a crucial indicator of the properties of a matrix, such as its ability to solve linear equations, and is directly related to concepts like the solutions of systems of equations and transformations represented by the matrix.
Modified gram-schmidt: Modified Gram-Schmidt is an algorithm used to orthogonalize a set of vectors in a more numerically stable manner compared to the classical Gram-Schmidt process. It takes a set of linearly independent vectors and transforms them into an orthogonal set, which is essential for applications such as QR decomposition, where a matrix is expressed as the product of an orthogonal matrix and an upper triangular matrix.
Numerical accuracy: Numerical accuracy refers to the degree to which a computed or measured value represents the true or exact value. It is crucial in numerical methods and algorithms, as even slight errors in calculations can lead to significant deviations from the expected outcomes. In computational mathematics, maintaining high numerical accuracy ensures that results are reliable and valid, especially when working with complex data structures and iterative processes.
Orthogonal Matrix: An orthogonal matrix is a square matrix whose columns and rows are orthogonal unit vectors, meaning that the dot product of any two distinct columns (or rows) is zero and the dot product of each column (or row) with itself is one. This property ensures that the transpose of an orthogonal matrix is equal to its inverse, making it essential in various mathematical applications, including transformations and decompositions.
Orthogonality: Orthogonality refers to the concept in linear algebra where two vectors are perpendicular to each other, meaning their inner product equals zero. This idea plays a crucial role in many areas, including the creation of orthonormal bases that simplify calculations, the analysis of data using Singular Value Decomposition (SVD), and ensuring numerical stability in algorithms like QR decomposition.
Pivoting: Pivoting is a technique used in numerical methods to improve the stability and accuracy of matrix operations, especially during processes like row reduction or decomposition. It involves rearranging rows or columns in a matrix to ensure that the algorithm operates on the largest possible pivot element, which helps to minimize numerical errors and avoid issues such as division by very small numbers.
QR Algorithm: The QR algorithm is a numerical method used for computing the eigenvalues and eigenvectors of a matrix. It works by decomposing a given matrix into a product of an orthogonal matrix Q and an upper triangular matrix R, iteratively refining the estimates of the eigenvalues. This process connects directly to eigendecomposition, as it provides a way to obtain eigenvalues and eigenvectors without explicitly forming the eigendecomposition itself, making it particularly useful in data science applications.
QR Decomposition: QR decomposition is a method in linear algebra used to factor a matrix into the product of an orthogonal matrix and an upper triangular matrix. This technique is particularly useful for solving linear systems, performing least squares approximations, and understanding the underlying structure of data in various applications.
QR Factorization Theorem: The QR Factorization Theorem states that any matrix can be decomposed into the product of an orthogonal matrix Q and an upper triangular matrix R. This decomposition is significant in numerical linear algebra, particularly for solving linear systems, performing least squares fitting, and eigenvalue problems, because it provides a stable and efficient way to manipulate matrices without losing numerical accuracy.
Schmidt's Orthogonalization: Schmidt's Orthogonalization is a mathematical procedure used to convert a set of linearly independent vectors into an orthogonal set of vectors that spans the same subspace. This process is vital in simplifying many problems in linear algebra, particularly in contexts such as QR decomposition, where the goal is to represent a matrix as the product of an orthogonal matrix and an upper triangular matrix. By generating orthogonal vectors, this technique helps to minimize numerical errors in calculations and provides a foundation for various applications in data science and computational methods.
Upper Triangular Matrix: An upper triangular matrix is a square matrix where all the entries below the main diagonal are zero. This structure allows for easier computations, particularly in solving linear equations and determining properties like rank and nullity. Upper triangular matrices play a crucial role in matrix factorizations and decompositions, simplifying the process of solving systems of equations and analyzing linear transformations.
© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.
Back
Practice QuizGlossary
Practice QuizGlossary
Next guide