1 Background and Motivation

1.1 The QR factorization and its basic properties

The QR factorization decomposes a matrix \(A \in \mathbb{R}^{m\times n}\) (or \(\mathbb{C}^{m\times n}\)) into \(A = QR\), where \(Q\) has orthonormal (unitary) columns and \(R\) is upper triangular (or upper trapezoidal for rectangular cases). This structure makes the action of \(A\) easy to compute through orthogonal transformations: applying \(Q^\ast\) or multiplying by \(Q\) is numerically stable, and triangular systems involving \(R\) are straightforward to solve.

Two properties underlie much of truncated QR’s usefulness: (1) orthogonality preserves norms and angles, and (2) triangular factors permit efficient back substitution. For least-squares and projection methods, these properties translate directly into reliable residual computation and controlled propagation of rounding errors.

1.2 Why truncation is useful (cost, memory, and model reduction)

“Truncated QR” keeps only a portion of a QR factorization—typically a reduced number of columns of \(Q\) and the corresponding leading block of \(R\). If the full factorization would be large, truncation can reduce both runtime and storage. The savings become significant when only a low-dimensional subspace is needed, such as in reduced-order modeling, exploratory data analysis, or iterative workflows where a full factorization is unnecessary.

Truncation also supports model reduction: rather than representing the action of \(A\) in all directions, it focuses on dominant components captured by a smaller orthogonal basis. In this setting, truncated QR is less about producing an exact decomposition and more about producing an efficient approximation with controlled accuracy.

1.3 Relationships to least squares and orthogonal projections

Least-squares problems often use QR to compute solutions via orthogonal projections. For an overdetermined system \(Ax \approx b\), the QR factorization enables rewriting the problem as \[ Ax = QRx,\quad Q^\ast b = \begin{bmatrix} y_1 \\ y_2 \end{bmatrix}, \] where the residual depends on the component of \(b\) orthogonal to the column space of \(A\). Truncating the QR factorization corresponds to projecting onto a smaller subspace, thereby producing an approximate least-squares solution within a reduced orthogonal basis.

This viewpoint clarifies why truncated QR is common in practical pipelines: it provides a structured way to trade accuracy for efficiency while maintaining a clear geometric interpretation through orthogonality.

2 Forms of Truncated QR

2.1 Thin QR versus truncated QR

A “thin” QR factorization typically means computing \(Q\) with only \(n\) (or \(\min(m,n)\)) columns and \(R\) with compatible triangular structure, without discarding information beyond what rectangularity requires. Truncated QR goes further: even within the thin factors, it keeps only a subset of columns corresponding to a target dimension \(k < \min(m,n)\). Thus, thin QR reduces dimension because of matrix shape; truncated QR reduces dimension because of a prescribed approximation goal.

Conceptually, thin QR answers “how do we avoid unnecessary columns for the exact factorization?” while truncated QR answers “how do we avoid unnecessary columns for an approximation?”

2.2 Rank-k (partial) QR factorization

A common form of truncated QR retains the first \(k\) orthonormal columns of \(Q\) and the corresponding leading \(k \times k\) upper triangular factor. In an idealized rank-\(k\) situation, one can write a partial factorization that approximates the action of \(A\) through \[ A \approx Q_k R_k, \] where \(Q_k \in \mathbb{R}^{m\times k}\) (or \(\mathbb{C}^{m\times k}\)) has orthonormal columns and \(R_k \in \mathbb{R}^{k\times n}\) (upper trapezoidal/triangular structure depending on the formulation).

In practice, the approximation quality depends on how truncation is chosen and how close the numerical rank is to \(k\). For “rank-\(k\)” QR, the goal is to approximate the dominant column space of \(A\) using only \(k\) orthogonal directions.

2.3 Economy-size QR for rectangular matrices

For rectangular matrices, economy-size QR typically produces the minimal orthogonal factor needed to represent \(A\) exactly (within numerical arithmetic). Truncated QR can be viewed as an additional reduction layered on top of economy-size QR: the orthogonal basis is first minimized due to shape, then further reduced due to a target dimension or tolerance criterion.

This interaction matters in implementations because the intermediate sizes (and thus performance) can depend strongly on whether the code starts from a full QR, thin QR, or an economy-size variant.

2.4 Truncation based on rank or tolerance

Truncation is often specified either by:

  • Target rank \(k\): keep \(k\) orthogonal directions and associated triangular factors.
  • Tolerance criterion: decide \(k\) by an error measure, such as an estimate of the neglected norm, a threshold on column norms, or a monotone surrogate derived during factorization.

Different criteria yield different truncation points and thus different approximation properties. Tolerance-based truncation is attractive because it can adapt automatically to the numerical spectrum of the matrix rather than requiring manual selection of \(k\).

3 Algorithms for Computing Truncated QR

3.1 Householder-based partial QR

Householder transformations are widely used to compute QR factorization because they apply orthogonal maps efficiently and stably. A truncated QR algorithm can be implemented by performing QR steps only until enough reflectors have been constructed to produce \(Q_k\) and the associated upper triangular portion \(R_k\). Depending on the stopping rule, the algorithm may avoid forming the remaining reflectors.

When truncation is based on a predetermined \(k\), the process is straightforward: build the first \(k\) Householder reflectors and then extract the corresponding reduced factors. When truncation is based on tolerance, the algorithm typically tracks a quantity correlated with the remaining “unexplained” part to decide whether further steps are necessary.

3.2 Modified Gram–Schmidt with truncation

Modified Gram–Schmidt (MGS) orthogonalizes columns against previously computed basis vectors. In truncated QR, the orthogonalization can stop once \(k\) basis vectors have been formed or once an error indicator suggests the remaining directions are below a specified relevance threshold.

MGS-based approaches can be effective, particularly in block or streaming contexts where columns arrive progressively. However, numerical performance can depend on re-orthogonalization strategies and on how the truncation threshold interacts with floating-point rounding.

3.3 Givens rotations and targeted elimination

Givens rotations zero out selected entries using plane rotations. Truncated QR using Givens rotations can be organized to eliminate only parts of the matrix necessary for building the reduced triangular factor, or to focus computation around directions likely to contribute to the retained subspace.

This approach can be convenient for sparse matrices or when targeted elimination is advantageous. The trade-off is that, depending on matrix structure, Givens-based methods may require more rotation operations than reflector-based approaches, so performance can be problem dependent.

3.4 Incremental/online construction (updating QR factors)

In incremental settings, new rows or columns may be added over time. Truncated QR can be maintained using update formulas that adjust the existing reduced factors while preventing growth in storage by keeping only a fixed \(k\) (or an adaptively chosen dimension).

This style of algorithm is common in streaming least squares and online system identification, where recomputing a full factorization at every step would be too expensive. Truncation also acts as a practical mechanism to control numerical drift by periodically discarding directions judged insignificant.

4 Rank and Error Interpretation

4.1 Approximation quality and residual norms

Truncating a QR factorization yields an approximate representation \(A \approx Q_k R_k\). The quality of this approximation is often assessed by norms of the difference \(A - Q_k R_k\) or by the impact on least-squares residuals when solving \(Ax \approx b\).

A key observation is that orthogonality simplifies residual analysis: projecting \(b\) onto the retained subspace produces a residual that can be interpreted as the component orthogonal to that subspace. Therefore, changes in residual norms can be directly linked to whether the retained basis captures the important directions of \(A\).

4.2 Connection to best low-rank approximations (conceptual comparison)

The best rank-\(k\) approximation of a matrix in the spectral or Frobenius norm is given by truncating its singular value decomposition (SVD). Truncated QR is not generally identical to SVD truncation, because it depends on how the QR factors are formed and which directions are selected.

Nevertheless, QR truncation can be viewed as a way to approximate the action of \(A\) using an orthogonal basis that is computationally cheaper to obtain than an SVD. Conceptually, truncated QR aims to capture a similar low-dimensional structure, but the closeness to the SVD optimum depends on the matrix and the truncation strategy.

4.3 Interpretation through orthogonal subspaces

Since \(Q_k\) spans a \(k\)-dimensional subspace, truncated QR is fundamentally about selecting a subspace approximating the column space of \(A\). The retained \(Q_k\) defines a projector \(P_k = Q_k Q_k^\ast\), and the approximation can be expressed as projecting \(A\) onto that subspace (modulo how \(R_k\) is structured).

This provides a geometric interpretation: if the subspace spanned by \(Q_k\) aligns well with the dominant directions of \(A\), then both approximation error and downstream solution errors tend to be small.

4.4 Practical error bounds and stopping criteria

In many practical algorithms, stopping criteria are based on quantities computable during factorization without explicitly forming full error norms. Examples include:

  • thresholds on remaining diagonal or norm-like entries in the triangular factor,
  • estimated contributions of omitted columns to the projection,
  • checks tied to the monotonic decay of certain norms.

While rigorous bounds depend on assumptions about pivoting, conditioning, and numerical rank behavior, the common goal is the same: stop truncating when additional basis vectors would not materially improve the approximation relative to the application’s accuracy needs.

5 Numerical Stability and Conditioning

5.1 Stability considerations in orthogonalization

QR factorization is generally stable because it relies on orthogonal transformations that preserve norms. In truncated QR, stability depends on how orthogonality is maintained among the computed basis vectors and how the truncation point is chosen.

Householder-based computations typically exhibit strong numerical stability. Gram–Schmidt variants can also be stable when implemented carefully (often with re-orthogonalization), but truncation can amplify sensitivity if it interacts with near-dependent columns.

5.2 Effects of truncation on conditioning

Truncation changes the effective problem being solved: instead of using the full column space of \(A\), one uses a reduced subspace. This can improve conditioning for certain tasks by removing nearly dependent directions. On the other hand, if the retained subspace misses important components of \(A\), the approximation error can dominate, producing poor overall results even if the reduced system is well-conditioned.

Thus, truncation can either help or hinder conditioning in practice, and good criteria aim to balance “numerical rank” with “application-relevant” directions.

5.3 Loss of orthogonality and mitigation strategies

Finite precision arithmetic may cause \(Q_k^\ast Q_k\) to deviate from the identity. Loss of orthogonality can lead to biased projections and inflated error estimates, particularly when truncation occurs close to the numerical rank transition.

Mitigation strategies include:

  • using stable orthogonalization schemes (e.g., Householder),
  • applying re-orthogonalization for Gram–Schmidt,
- monitoring orthogonality measures (such as \(\|Q_k^\ast Q_k - I\|\)) and adjusting procedures if thresholds are exceeded.

5.4 Handling near-rank-deficient matrices

Near-rank-deficient matrices have singular values that decay without a sharp gap. Truncated QR becomes a tool for separating meaningful directions from noise or numerical artifacts. When a matrix has no clear rank boundary, choosing \(k\) based on tolerance or error criteria is more robust than choosing a fixed rank blindly.

Additionally, pivoting or rank-revealing variants can help ensure that the retained columns better represent the dominant subspace, improving the practical interpretability of “discarded” components.

6 Truncated QR in Least-Squares Problems

6.1 Solving overdetermined systems with a reduced model

For overdetermined systems \(Ax \approx b\), truncated QR can be used to compute an approximate least-squares solution by projecting \(b\) onto the subspace spanned by \(Q_k\) and solving a reduced triangular system involving \(R_k\). The resulting solution minimizes the norm of the residual within the restricted range determined by the retained basis.

This approach reduces cost compared to solving with the full QR factors, especially when \(k\) is much smaller than \(\min(m,n)\).

6.2 Truncated QR for regularization intuition

Truncation can be interpreted as a form of regularization: components associated with directions deemed unimportant are omitted. While it is not identical to classical Tikhonov regularization, the effect is analogous—stabilizing solutions by restricting the hypothesis space.

This intuition is particularly helpful when the system matrix is ill-conditioned or when the data contains noise, making small singular-like directions unreliable for fitting.

6.3 Choosing truncation rank for data-fitting

Selecting \(k\) depends on the desired trade-off between bias (from omitting components) and variance (from fitting noisy directions). Common practical choices include:

  • matching \(k\) to an estimated numerical rank,
  • using a tolerance linked to a target residual level,
  • cross-validating on predictive performance when data supports it.

In applications where interpretability matters, \(k\) may also be chosen based on the dimensionality of meaningful features.

6.4 Diagnostics: residuals and leverage of truncated components

Diagnostics can assess whether truncation discards information that affects the fit. Useful signals include:

  • magnitude and evolution of residual norms as \(k\) increases,
  • stability of the reduced solution with respect to small changes in \(k\),
  • measures of leverage or influence of the retained basis vectors on the fitted response.

If residual norms plateau early while solution coefficients remain erratic, it may indicate either a subspace mismatch or numerical issues in computing the orthogonal basis.

7.1 Column-pivoted QR (QR with truncation interplay)

Column pivoting reorders columns during QR to improve the likelihood that early columns span the more significant subspace. In truncated QR, pivoting and truncation often work together: one computes a QR with column permutations, then truncates after identifying a set of influential directions.

The benefit is improved rank-revealing behavior, which can make the interpretation of truncation more reliable—especially when the matrix has strongly varying column norms or when a clear low-rank structure is suspected but not aligned with the original column order.

7.2 Pivoting strategies for rank-revealing behavior

Several pivoting rules exist, including greedy selection based on remaining column norms and more sophisticated variants. Rank-revealing QR aims to provide bounds that relate the chosen subspace to the matrix’s effective rank.

In truncated QR workflows, the pivoting strategy influences both computational cost and the quality of the truncated approximation. Greedy norm-based pivoting is often used for efficiency, while more elaborate methods may be chosen when higher-quality rank information is needed.

7.3 Connections to SVD-based truncation (high-level)

SVD-based truncation is the benchmark for best low-rank approximation, but it is more expensive. QR-based truncation offers a cheaper alternative that still produces an orthogonal basis, often using fewer transformations.

At a high level, the connection lies in subspace approximation: both methods aim to identify a reduced-dimensional space where the matrix’s action is captured. Differences arise because QR truncation selects a basis from QR structure and possibly pivoting decisions rather than directly from singular vectors.

7.4 QR-based randomized methods (overview level)

Randomized algorithms can accelerate low-rank approximation by sampling or sketching the column space. A QR-based randomized pipeline often computes an orthonormal basis for a sampled range and then applies QR (or related orthogonalization) to refine the reduced representation.

Truncation in such methods corresponds to selecting a target dimension based on oversampling and accuracy estimates derived from the sketch. This can yield substantial speedups in large-scale settings where deterministic factorizations are too costly.

8 Implementation Considerations

8.1 Complexity and storage analysis

Let \(m \times n\) be the matrix dimensions and \(k\) the retained rank (with \(k \ll \min(m,n)\)). Truncated QR aims to reduce the dominant arithmetic from full QR to approximately the operations needed to generate the first \(k\) orthogonal directions and the corresponding triangular data. Storage similarly drops from storing full \(Q\) to storing only \(Q_k\) plus the reduced triangular components.

Actual complexity depends on the chosen algorithm (Householder vs. Gram–Schmidt vs. Givens), whether pivoting is used, and whether computations are blocked for cache efficiency.

8.2 Block algorithms and cache-friendly strategies

High-performance implementations often use blocked Householder reflectors or block Gram–Schmidt to maximize data locality. Truncation can be incorporated by stopping after enough blocks to reach the desired dimension or tolerance, avoiding unnecessary trailing updates.

Block methods also help reduce synchronization overhead in parallel environments, improving scalability.

8.3 Parallelism and large-scale settings

For large matrices, truncated QR is used in contexts where parallel computation and memory bandwidth dominate. Blocked QR variants allow overlapping computation and communication, and truncation reduces the amount of data that must be transferred or stored.

In online or distributed settings, incremental truncated QR can distribute the work across time steps or partitions, keeping the reduced representation compact.

8.4 Practical input/output and tolerance handling

Real-world usage involves careful parameter selection and robust tolerance handling. Implementations typically expose parameters for:

  • target rank \(k\),
  • tolerance relative to norms of \(A\) or the right-hand side,
  • maximum iterations or reflector counts,
  • thresholds for stopping and pivot acceptance.

Practical considerations include ensuring that stopping rules are consistent across scales and that the computed reduced factors align with downstream solver expectations.

9 Applications

9.1 Model order reduction

Model order reduction replaces a high-dimensional dynamical or parametric model with a smaller one. Truncated QR provides a way to build reduced bases that capture dominant system behavior from snapshots or observed trajectories.

Because the reduced basis is orthonormal (in the ideal arithmetic sense), projecting equations onto that basis can yield stable and efficient reduced simulations.

9.2 Compressive sensing and sketching (broad overview)

In compressive sensing and sketching, one often seeks low-dimensional representations while preserving relevant information. QR-based randomized or sketching methods can build orthonormal bases from compressed measurements, then truncate to keep a manageable dimension.

While the specifics vary by method, truncated QR frequently appears as a practical tool for turning sampled data into a structured reduced representation.

9.3 Numerical experiments in scientific computing

Truncated QR is used in benchmarking and experimentation for numerical solvers, especially when comparing rank-revealing approximations, testing reduced least-squares models, or evaluating error versus cost.

Experiment design often studies how approximation quality changes with \(k\), tolerance settings, pivoting choices, and matrix conditioning.

9.4 Educational examples and benchmark problems

Educational use emphasizes the geometric interpretation of orthogonal projections and how truncation affects residuals. Benchmark problems often include matrices with known effective rank, controlled singular value decay, or structured noise, allowing learners to observe when truncation improves performance and when it leads to underfitting.

10 References and Further Reading

10.1 Foundational texts on QR and numerical linear algebra

Foundational coverage includes standard treatments of QR factorization, orthogonal projections, and numerical stability analysis. Texts focusing on numerical linear algebra typically discuss Householder reflectors, Gram–Schmidt variants, and implications for least-squares solvers.

10.2 Survey-style references on rank-revealing factorizations

Rank-revealing QR factorizations and related theory appear in survey papers and research monographs. These resources discuss how pivoting affects the ability to identify numerical rank and how truncation can be guided by computable surrogates for error.

10.3 Implementation guides and library documentation resources

Implementation guides and software documentation (for example, numerical libraries providing QR routines, pivoted QR, and least-squares solvers) are useful for understanding practical parameter choices, supported truncation interfaces, and recommended stability practices. These documents also clarify how tolerance is interpreted and how reduced factors are stored.