RAS algorithm - Revision history

David Eppstein: if it's identical to Iterative proportional fitting, it should be a redirect, not a separate article

2009-07-05T03:14:57Z

if it's identical to Iterative proportional fitting, it should be a redirect, not a separate article

← Previous revision		Revision as of 03:14, 5 July 2009
Line 1:		Line 1:
			#REDIRECT [[Iterative proportional fitting]]
	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).
			{{R from alternative name}}


	== Notes ==
	{{reflist}}

	[[Category:Categorical data]]
	[[Category:Statistical algorithms]]

84.155.164.109 at 20:12, 3 July 2009

2009-07-03T20:12:31Z

← Previous revision		Revision as of 20:12, 3 July 2009
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 ~~similar~~ to the [[Iterative_proportional_fitting\|Iterative Proportional Fitting Procedure]] (IPFP). Both algorithms iteratively apply interchanging row and column fitting steps to achieve [[entropy]] minimization and [[maximum-likelihood_estimation\|maximum-likelihood estimation]] under certain distributional assumptions.		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 ==

Hanzzoid: /* Algorithm */

2009-07-03T16:26:39Z

Algorithm

← Previous revision		Revision as of 16:26, 3 July 2009
Line 20:		Line 20:
	<math>A^{(2t + 1)} = diag(r^{(t+1)})A^{(2t)}</math>		<math>A^{(2t + 1)} = diag(r^{(t+1)})A^{(2t)}</math>

	<math>A^{(2t + 2)} = A^{(2t)}diag(s^{(t+1)})</math>		<math>A^{(2t + 2)} = A^{(2t+1)}diag(s^{(t+1)})</math>

	where		where

Hanzzoid at 16:11, 3 July 2009

2009-07-03T16:11:56Z

← Previous revision		Revision as of 16:11, 3 July 2009
Line 3:		Line 3:
	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.		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)}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 ==

Hanzzoid: ←Created page with 'The '''RAS algorithm''' proposed by Bacharach (1965) estimates a nonnegative matrix from its marginals{{cite journal |last=Bacharach|first=M.|year=1965|title=E...'

2009-07-03T15:37:05Z

←Created page with 'The '''RAS algorithm''' proposed by Bacharach (1965) estimates a nonnegative matrix from its marginals<ref>{{cite journal |last=Bacharach|first=M.|year=1965|title=E...'

New page

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 similar to the [[Iterative_proportional_fitting|Iterative Proportional Fitting Procedure]] (IPFP). Both algorithms iteratively apply interchanging row and column fitting steps to achieve [[entropy]] minimization and [[maximum-likelihood_estimation|maximum-likelihood estimation]] under certain distributional assumptions.

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.

== Notes ==
{{reflist}}

[[Category:Categorical data]]
[[Category:Statistical algorithms]]