RAS algorithm: Difference between revisions
Content deleted Content added
No edit summary |
|||
| Line 1: | Line 1: | ||
The '''RAS algorithm''' proposed by Bacharach (1965) estimates a nonnegative matrix from its marginals<ref>{{cite journal |last=Bacharach|first=M.|year=1965|title=Estimating Nonnegative Matrices from Marginal Data|journal=International Economic Review|volume=6|pages=294-310|id={{JSTOR|2525582}}}}</ref>, a task frequently arising in [[input-output_analysis|input-output analysis]]. RAS is |
The '''RAS algorithm''' proposed by Bacharach (1965) estimates a nonnegative matrix from its marginals<ref>{{cite journal |last=Bacharach|first=M.|year=1965|title=Estimating Nonnegative Matrices from Marginal Data|journal=International Economic Review|volume=6|pages=294-310|id={{JSTOR|2525582}}}}</ref>, a task frequently arising in [[input-output_analysis|input-output analysis]]. RAS is '''identical''' to the [[Iterative_proportional_fitting|Iterative Proportional Fitting Procedure]] (IPFP). |
||
RAS generates a matrix <math>\hat{A}</math> similar to the intial matrix <math>A</math>, that is, small elements of <math>A</math> are small in <math>\hat{A}</math>. This is the property of structure conservation. Assuming an underlying multinomial distribution, the estimated matrix <math>\hat{A}</math> is the most probable one given the specified marginal constraints. |
|||
== The Problem == |
|||
Let <math>A \in \mathbb{R}^{m\times n}</math> be the initial matrix with nonnegative entries, <math>u \in \mathbb{R}^m</math> a vector of specified |
|||
row marginals (e.i. row sums) and <math>v \in \mathbb{R}^n</math> a vector of column marginals. We wish to compute a matrix <math>\hat{A} = (\hat{a}_{ij}) \in \mathbb{R}^{m\times n}</math> similar to ''A'' in the sense of structure conservation and with the given marginals, meaning |
|||
<math>\hat{a}_{i+} = \sum_{j=1}^n \hat{a}_{ij} = u_i</math> |
|||
and |
|||
<math>\hat{a}_{+j} = \sum_{i=1}^m \hat{a}_{ij} = v_j</math> |
|||
== Algorithm == |
|||
Define the diagonalization operator <math>diag: \mathbb{R}^k \longrightarrow \mathbb{R}^{k\times k}</math>, which produces a (diagonal) matrix with its input vector on the main diagonal and zero elsewhere. Then, for <math>t \geq 0</math>, set |
|||
<math>A^{(2t + 1)} = diag(r^{(t+1)})A^{(2t)}</math> |
|||
<math>A^{(2t + 2)} = A^{(2t+1)}diag(s^{(t+1)})</math> |
|||
where |
|||
<math>r_i^{t + 1} = \frac{u_i}{\sum_j a_{ij}^{(2t)}}</math> |
|||
<math>s_j^{t + 1} = \frac{v_j}{\sum_i a_{ij}^{(2t+1)}}</math> |
|||
Finally, we obtain <math>\hat{A} = \lim_{t\rightarrow\infty} A^{(t)}</math>. |
|||
== Notes == |
== Notes == |
||
Revision as of 20:12, 3 July 2009
The RAS algorithm proposed by Bacharach (1965) estimates a nonnegative matrix from its marginals[1], a task frequently arising in input-output analysis. RAS is identical to the Iterative Proportional Fitting Procedure (IPFP).