# Update QR factorization by adding a column for orthogonal matching pursuit

**URL:** https://discourse.julialang.org/t/update-qr-factorization-by-adding-a-column-for-orthogonal-matching-pursuit/56368
**Category:** Numerics
**Created:** [March 2, 2021, 9:44pm UTC](https://discourse.julialang.org/t/update-qr-factorization-by-adding-a-column-for-orthogonal-matching-pursuit/56368 "2021-03-02T21:44:35Z")
**Posts on this page:** 1
**Page:** 1

<div class="post-metadata">

### Author: ![mleprovost](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mleprovost/32/7166_2.png) [@mleprovost](https://discourse.julialang.org/u/mleprovost)
#### Post date: [March 2, 2021, 9:44pm UTC](https://discourse.julialang.org/t/update-qr-factorization-by-adding-a-column-for-orthogonal-matching-pursuit/56368/1 "2021-03-02T21:44:36Z")

</div>

Hello,

I am working on the orthogonal matching pursuit algorithm to select a sparse set of features to solve Ax = b. In this algorithm, we add in a greedy fashion a new column (i.e. feature) at each step. The residual at step k is r^{(k)} = A^{(k)}x^{(k)} - b, where A^{(k)} contains the selected columns of A at the step k.  
We want to avoid to solve the linear system A^{(k)}x^{(k)} = b to compute the norm of the residual error \delta^{(k)} = ||r^{(k)}||\_2 at each step. To do so, Baptista et al. ([Redirecting](https://doi.org/10.1016/j.jcp.2019.01.035)) sequentially update a QR factorization of A^{(k)} = Q^{(k)} R^{(k)} to efficiently compute the norm of the residual error \delta^{(k)} (equations (14) - (18)).

There are a few options in Julia to update a QR factorization by adding a new column to the right of A^{(k)}:

`QRupdate.jl` ([https://github.com/mpf/QRupdate.jl](https://github.com/mpf/QRupdate.jl)), but this one only updates the R matrix, (and not Q), and squares the conditioning number for R.

`GeneralQP.jl` ([https://github.com/oxfordcontrol/GeneralQP.jl/blob/master/src/linear\_algebra.jl](https://github.com/oxfordcontrol/GeneralQP.jl/blob/master/src/linear_algebra.jl)) but does not seem to be maintained anymore (last commit in June 2019).

Is there a better option to perform this QR factorization?