Non-recursive Algorithm for Solving Systems of Linear Equations

156 Views Asked by At

I'm looking to duplicate Excel's LINEST() functionality using DAX. To do this, I plan to use an ordinary least squares approach which means I need to be able to solve the following matrix equation for $\boldsymbol{\beta}$ where $\mathbf X$ and $\mathbf y$ are known:

$$(\mathbf X^{\rm T} \mathbf X ) {\boldsymbol{\beta}}= \mathbf X^{\rm T} \mathbf y.$$

This boils down to solving a generic linear system $\mathbf A \mathbf x = \mathbf b$, where $\mathbf A$ is a positive semi-definite square matrix.

The wrinkle is that the DAX language doesn't handle recursion well. It has functions that iterate over columns so that you can do things like matrix multiplication, as I've demonstrated in this SO answer, but it can't do recursion within a loop since it doesn't really have loops. I can set and update variables/tables, but the number of times I can do this has to be constant rather than dependent on matrix size.

I'm not particularly worried about computational complexity since $\mathbf X^{\rm T} \mathbf X$ is not going to be larger than say $12 \times 12$ for my applications, so $O(n^3)$ is fine and even $O(n!)$ might work in a pinch.

I've looked at Gaussian elimination and Cramer's rule, but am struggling to reformulate these algorithms non-recursively. I'm considering using the Leibniz or Laplace expansion along with Cramer's rule to brute-force it in $O(n!)$, but getting the enumerations and signs of all the permutations seems like a headache.

Can anyone point me in the right direction or indicate if this is even possible? Anyone know of any references that address this sort of thing?