# Gram-Schmidt decomposition

**URL:** <https://discourse.julialang.org/t/gram-schmidt-decomposition/75417>\
**Category:** New to Julia\
**Tags:** linearalgebra\
**Created:** [January 29, 2022, 2:58pm UTC](https://discourse.julialang.org/t/gram-schmidt-decomposition/75417 "2022-01-29T14:58:34Z")\
**Posts on this page:** 1\
**Showing post:** 11

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [April 11, 2024, 5:58pm UTC](https://discourse.julialang.org/t/gram-schmidt-decomposition/75417/11 "2024-04-11T17:58:01Z")

</div>

> [@sgaure](#):
>
> There is also a fast orthonormalization via the Cholesky decomposition.

Note that this is not faster in the complexity sense — all of these algorithms are \Theta(mn^2) for an m \times n matrix A. But it is probably faster in actual time (i.e. a better “constant coefficient” of the mn^2) for m \gg n, similar to solving least-squares problems by the normal equations as discussed in [Efficient way of doing linear regression - #33 by stevengj](https://discourse.julialang.org/t/efficient-way-of-doing-linear-regression/31232/33) … at the expense of accuracy as you point out.

> [@sgaure](#):
>
> Though one must be a bit careful, it’s not as numerically stable as the QR method.

Technically, there is no such thing as “not as stable”. It’s a boolean choice: an algorithm is either numerically stable or not. It’s a question of whether the (backward) error goes to zero (at worst) linearly with the precision \varepsilon or not, i.e. whether the backward error is O(\varepsilon).

This algorithm (which squares the condition number of A) is definitely much _less accurate_ than Householder QR or modified Gram–Schmidt. I don’t know offhand whether it is numerically _unstable_ (i.e., its backward errors decrease more slowly than linearly), but my guess it is that it is probably unstable.

> [@sgaure](#):
>
> `B = A*inv(U) # orthonormal column vectors spanning the same subspace.`

Aside: One should get out of the habit of using matrix inverses for numerical calculations. One should instinctively do `A / U` rather than `A * inv(U)`. In this case, `A / U` exploits the fact that U is upper triangular to avoid the O(n^3) complexity of inversion.

---

_[View the full topic](https://discourse.julialang.org/t/gram-schmidt-decomposition/75417)._