yat: Ticket #401: Weighted Quantile Normalization
https://dev.thep.lu.se/yat/ticket/401
<p>
related to <a class="closed ticket" href="https://dev.thep.lu.se/yat/ticket/478" title="#478: discussion: Generalize qQuantileNormalizer to work also on weighted data (closed: fixed)">ticket:478</a>
</p>
<p>
Same as the unweighted case, but working on MatrixWeighted rather than Matrix.
</p>
<p>
Though, it is not straight forward to generalize the algorithm. In the unweighted case each column has follows the same distribution. What does that post-condition imply in the weighted case?
</p>
en-usyat/yat/chrome/site/images/yat.png
https://dev.thep.lu.se/yat/ticket/401
Trac 1.2.3PeterWed, 23 Jul 2008 16:23:30 GMT
https://dev.thep.lu.se/yat/ticket/401#comment:1
https://dev.thep.lu.se/yat/ticket/401#comment:1
<p>
The unweighted Quantile Normalization algorithm has three steps (see <a class="closed ticket" href="https://dev.thep.lu.se/yat/ticket/288" title="#288: request: Quantile Normalization (closed: fixed)">#288</a>):
</p>
<ul><li>sort each column
</li><li>replace element with row average
</li><li>reverse sort in step 1
</li></ul><p>
To generalize this algorithm I will reformulate it as an optimization problem that can be generalized for the weighted case. If we let x be the matrix prior normalization, we can define the generalized rank as:
</p>
<p>
r_ij = sum_k w_kj * I(x_ij - x_kj)
</p>
<p>
where I(x)=1 if x>0, I(x)=1/2 if x=0, and I(x)=0 if x<0.
</p>
<p>
Then the quantile normalized matrix x' fulfills:
x'_ij <= x'_kl iff r_ij <= r_kl
</p>
<p>
and Q = sum_ij (x_ij - x'_ij)<sup>2</sup> is minimized.
</p>
<p>
In other words, we can view QN as a minimization problem with a number of inequality conditions.
This is straight forward to generalize to the weighted case:
</p>
<p>
The inequality conditions are good as they are, and the objective function to minimized could be modified to
</p>
<p>
Q = sum_ij w_ij (x_ij - x'_ij)<sup>2</sup>
</p>
<p>
The remaining problem is to find an algorithm that can find the solution fast.
</p>
TicketPeterWed, 15 Oct 2008 21:05:36 GMTowner, component changed
https://dev.thep.lu.se/yat/ticket/401#comment:2
https://dev.thep.lu.se/yat/ticket/401#comment:2
<ul>
<li><strong>owner</strong>
changed from <em>Jari Häkkinen</em> to <em>Peter</em>
</li>
<li><strong>component</strong>
changed from <em>utility</em> to <em>normalizer</em>
</li>
</ul>
<p>
A related question is how to take care of ties. Currently, two elements within a column being equal prior normalization, they are likely not equal after normalization.
</p>
TicketPeterFri, 16 Jan 2009 15:34:09 GMTdescription changed
https://dev.thep.lu.se/yat/ticket/401#comment:3
https://dev.thep.lu.se/yat/ticket/401#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/yat/ticket/401?action=diff&version=3">diff</a>)
</li>
</ul>
<p>
<a class="closed ticket" href="https://dev.thep.lu.se/yat/ticket/478" title="#478: discussion: Generalize qQuantileNormalizer to work also on weighted data (closed: fixed)">#478</a> was marked as related
</p>
Ticket