# 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!