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[0]
    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

Learn Data Science

navigator.sendBeacon and Rails

Adding CSP to Rails


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