# Backsolving in Ruby

QR decomposition is a stable way to solve linear regression.

``````require "matrix"

x = Matrix.columns([[1, 1, 1, 1, 1], [1, 2, 3, 4, 5], [4, 2, 5, 6, 1]])
y = Matrix.column_vector([145, 225, 355, 465, 515])
``````

You can use the extendmatrix gem to do decomposition in pure Ruby. Givens rotations are faster, but the implementation appears to have a bug.

``````require "extendmatrix"

r = x.houseR
q = x.houseQ
``````

Next, split R into a p-by-p matrix and Q into a n-by-p matrix (see page 32 for reasoning).

``````r1 = r.minor(0...x.column_count, 0...x.column_count)
q1 = q.minor(0...x.row_count, 0...x.column_count)
``````

Finally, backsolve. Code ported from Stack Overflow.

``````def backsolve(a, b)
x = Matrix.zero(b.row_count, b.column_count)

# use an array since matrices
# are immutable in Ruby
x = x.to_a

c = 1.0 / a[-1, -1]
x[-1] = b.row(-1).map { |v| c * v }

(b.row_count - 2).downto(0) do |i|
c = 1.0 / a[i, i]
s = (a.minor(i..i, (i+1)..-1) * Matrix.rows(x[(i + 1)..-1])).to_a
x[i] = b.row(i).zip(s).map { |v, w| v - w }.map { |v| c * v }
end

Matrix.rows(x)
end
``````

Run it to get the coefficients

``````backsolve(r1, q1.transpose * y)
``````

Regression solved!

Published June 28, 2018

You might also enjoy

## Introducing Archer: Rails Console History for Heroku, Docker, and More

All code examples are public domain.
Use them however you’d like (licensed under CC0).