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 · Tweet


You might also enjoy

Securing Sensitive Data in Rails

Introducing Dexter, the Automatic Indexer for Postgres

Rails, Meet Data Science


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