RAS algorithm: Difference between revisions

The RAS algorithm proposed by Bacharach (1965) estimates a nonnegative matrix from its marginals, a task frequently arising in input-output analysis. RAS is similar to the Iterative Proportional Fitting Procedure (IPFP). Both algorithms iteratively apply interchanging row and column fitting steps to achieve entropy minimization and maximum-likelihood estimation under certain distributional assumptions.

RAS generates a matrix ${\hat {A}}$ similar to the intial matrix $A$, that is, small elements of $A$ are small in ${\hat {A}}$. This is the property of structure conservation. Assuming an underlying multinomial distribution, the estimated matrix ${\hat {A}}$ is the most probable one given the specified marginal constraints.

The Problem

Let $A\in \mathbb {R} ^{m\times n}$ be the initial matrix with nonnegative entries, $u\in \mathbb {R} ^{m}$ a vector of specified row marginals (e.i. row sums) and $v\in \mathbb {R} ^{n}$ a vector of column marginals. We wish to compute a matrix ${\hat {A}}=({\hat {a}}_{ij})\in \mathbb {R} ^{m\times n}$ similar to A in the sense of structure conservation and with the given marginals, meaning

${\hat {a}}_{i+}=\sum _{j=1}^{n}{\hat {a}}_{ij}=u_{i}$

and

${\hat {a}}_{+j}=\sum _{i=1}^{m}{\hat {a}}_{ij}=v_{j}$

Algorithm

Define the diagonalization operator $diag:\mathbb {R} ^{k}\longrightarrow \mathbb {R} ^{k\times k}$, which produces a (diagonal) matrix with its input vector on the main diagonal and zero elsewhere. Then, for $t\geq 0$, set

$A^{(2t+1)}=diag(r^{(t+1)})A^{(2t)}$

$A^{(2t+2)}=A^{(2t)}diag(s^{(t+1)})$

where

$r_{i}^{t+1}={\frac {u_{i}}{\sum _{j}a_{ij}^{(2t)}}}$

$s_{j}^{t+1}={\frac {v_{j}}{\sum _{i}a_{ij}^{(2t+1)}}}$

Finally, we obtain ${\hat {A}}=\lim _{t\rightarrow \infty }A^{(t)}$.