<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta charset="utf-8" />
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="pandoc" />
<meta name="author" content="Jason Willwerscheid" />
<title>A more memory-efficient backfitting algorithm</title>
<script src="site_libs/jquery-1.11.3/jquery.min.js"></script>
<meta name="viewport" content="width=device-width, initial-scale=1" />
<link href="site_libs/bootstrap-3.3.5/css/cosmo.min.css" rel="stylesheet" />
<script src="site_libs/bootstrap-3.3.5/js/bootstrap.min.js"></script>
<script src="site_libs/bootstrap-3.3.5/shim/html5shiv.min.js"></script>
<script src="site_libs/bootstrap-3.3.5/shim/respond.min.js"></script>
<script src="site_libs/jqueryui-1.11.4/jquery-ui.min.js"></script>
<link href="site_libs/tocify-1.9.1/jquery.tocify.css" rel="stylesheet" />
<script src="site_libs/tocify-1.9.1/jquery.tocify.js"></script>
<script src="site_libs/navigation-1.1/tabsets.js"></script>
<link href="site_libs/highlightjs-9.12.0/textmate.css" rel="stylesheet" />
<script src="site_libs/highlightjs-9.12.0/highlight.js"></script>
<link href="site_libs/font-awesome-4.5.0/css/font-awesome.min.css" rel="stylesheet" />
<style type="text/css">code{white-space: pre;}</style>
<style type="text/css">
pre:not([class]) {
background-color: white;
}
</style>
<script type="text/javascript">
if (window.hljs) {
hljs.configure({languages: []});
hljs.initHighlightingOnLoad();
if (document.readyState && document.readyState === "complete") {
window.setTimeout(function() { hljs.initHighlighting(); }, 0);
}
}
</script>
<style type="text/css">
h1 {
font-size: 34px;
}
h1.title {
font-size: 38px;
}
h2 {
font-size: 30px;
}
h3 {
font-size: 24px;
}
h4 {
font-size: 18px;
}
h5 {
font-size: 16px;
}
h6 {
font-size: 12px;
}
.table th:not([align]) {
text-align: left;
}
</style>
</head>
<body>
<style type = "text/css">
.main-container {
max-width: 940px;
margin-left: auto;
margin-right: auto;
}
code {
color: inherit;
background-color: rgba(0, 0, 0, 0.04);
}
img {
max-width:100%;
height: auto;
}
.tabbed-pane {
padding-top: 12px;
}
button.code-folding-btn:focus {
outline: none;
}
</style>
<style type="text/css">
/* padding for bootstrap navbar */
body {
padding-top: 51px;
padding-bottom: 40px;
}
/* offset scroll position for anchor links (for fixed navbar) */
.section h1 {
padding-top: 56px;
margin-top: -56px;
}
.section h2 {
padding-top: 56px;
margin-top: -56px;
}
.section h3 {
padding-top: 56px;
margin-top: -56px;
}
.section h4 {
padding-top: 56px;
margin-top: -56px;
}
.section h5 {
padding-top: 56px;
margin-top: -56px;
}
.section h6 {
padding-top: 56px;
margin-top: -56px;
}
</style>
<script>
// manage active state of menu based on current page
$(document).ready(function () {
// active menu anchor
href = window.location.pathname
href = href.substr(href.lastIndexOf('/') + 1)
if (href === "")
href = "index.html";
var menuAnchor = $('a[href="' + href + '"]');
// mark it active
menuAnchor.parent().addClass('active');
// if it's got a parent navbar menu mark it active as well
menuAnchor.closest('li.dropdown').addClass('active');
});
</script>
<div class="container-fluid main-container">
<!-- tabsets -->
<script>
$(document).ready(function () {
window.buildTabsets("TOC");
});
</script>
<!-- code folding -->
<script>
$(document).ready(function () {
// move toc-ignore selectors from section div to header
$('div.section.toc-ignore')
.removeClass('toc-ignore')
.children('h1,h2,h3,h4,h5').addClass('toc-ignore');
// establish options
var options = {
selectors: "h1,h2,h3",
theme: "bootstrap3",
context: '.toc-content',
hashGenerator: function (text) {
return text.replace(/[.\\/?&!#<>]/g, '').replace(/\s/g, '_').toLowerCase();
},
ignoreSelector: ".toc-ignore",
scrollTo: 0
};
options.showAndHide = true;
options.smoothScroll = true;
// tocify
var toc = $("#TOC").tocify(options).data("toc-tocify");
});
</script>
<style type="text/css">
#TOC {
margin: 25px 0px 20px 0px;
}
@media (max-width: 768px) {
#TOC {
position: relative;
width: 100%;
}
}
.toc-content {
padding-left: 30px;
padding-right: 40px;
}
div.main-container {
max-width: 1200px;
}
div.tocify {
width: 20%;
max-width: 260px;
max-height: 85%;
}
@media (min-width: 768px) and (max-width: 991px) {
div.tocify {
width: 25%;
}
}
@media (max-width: 767px) {
div.tocify {
width: 100%;
max-width: none;
}
}
.tocify ul, .tocify li {
line-height: 20px;
}
.tocify-subheader .tocify-item {
font-size: 0.90em;
padding-left: 25px;
text-indent: 0;
}
.tocify .list-group-item {
border-radius: 0px;
}
</style>
<!-- setup 3col/9col grid for toc_float and main content -->
<div class="row-fluid">
<div class="col-xs-12 col-sm-4 col-md-3">
<div id="TOC" class="tocify">
</div>
</div>
<div class="toc-content col-xs-12 col-sm-8 col-md-9">
<div class="navbar navbar-default navbar-fixed-top" role="navigation">
<div class="container">
<div class="navbar-header">
<button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#navbar">
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</button>
<a class="navbar-brand" href="index.html">FLASHvestigations</a>
</div>
<div id="navbar" class="navbar-collapse collapse">
<ul class="nav navbar-nav">
<li>
<a href="index.html">Home</a>
</li>
<li>
<a href="about.html">About</a>
</li>
</ul>
<ul class="nav navbar-nav navbar-right">
<li>
<a href="https://github.com/willwerscheid/FLASHvestigations">
<span class="fa fa-github"></span>
</a>
</li>
</ul>
</div><!--/.nav-collapse -->
</div><!--/.container -->
</div><!--/.navbar -->
<!-- Add a small amount of space between sections. -->
<style type="text/css">
div.section {
padding-top: 12px;
}
</style>
<div class="fluid-row" id="header">
<h1 class="title toc-ignore">A more memory-efficient backfitting algorithm</h1>
<h4 class="author"><em>Jason Willwerscheid</em></h4>
<h4 class="date"><em>11/4/2018</em></h4>
</div>
<p><strong>Last updated:</strong> 2018-11-05</p>
<strong>workflowr checks:</strong> <small>(Click a bullet for more information)</small>
<ul>
<li>
<p><details> <summary> <strong style="color:blue;">✔</strong> <strong>R Markdown file:</strong> up-to-date </summary></p>
<p>Great! Since the R Markdown file has been committed to the Git repository, you know the exact version of the code that produced these results.</p>
</details>
</li>
<li>
<p><details> <summary> <strong style="color:blue;">✔</strong> <strong>Environment:</strong> empty </summary></p>
<p>Great job! The global environment was empty. Objects defined in the global environment can affect the analysis in your R Markdown file in unknown ways. For reproduciblity it’s best to always run the code in an empty environment.</p>
</details>
</li>
<li>
<p><details> <summary> <strong style="color:blue;">✔</strong> <strong>Seed:</strong> <code>set.seed(20180714)</code> </summary></p>
<p>The command <code>set.seed(20180714)</code> was run prior to running the code in the R Markdown file. Setting a seed ensures that any results that rely on randomness, e.g. subsampling or permutations, are reproducible.</p>
</details>
</li>
<li>
<p><details> <summary> <strong style="color:blue;">✔</strong> <strong>Session information:</strong> recorded </summary></p>
<p>Great job! Recording the operating system, R version, and package versions is critical for reproducibility.</p>
</details>
</li>
<li>
<p><details> <summary> <strong style="color:blue;">✔</strong> <strong>Repository version:</strong> <a href="https://github.com/willwerscheid/FLASHvestigations/tree/1eda9afdc1ea05d8145c5e2647028fd1421d962b" target="_blank">1eda9af</a> </summary></p>
Great! You are using Git for version control. Tracking code development and connecting the code version to the results is critical for reproducibility. The version displayed above was the version of the Git repository at the time these results were generated. <br><br> Note that you need to be careful to ensure that all relevant files for the analysis have been committed to Git prior to generating the results (you can use <code>wflow_publish</code> or <code>wflow_git_commit</code>). workflowr only checks the R Markdown file, but you know if there are other scripts or data files that it depends on. Below is the status of the Git repository when the results were generated:
<pre><code>
Ignored files:
Ignored: .DS_Store
Ignored: .Rhistory
Ignored: .Rproj.user/
Ignored: docs/.DS_Store
Ignored: docs/figure/.DS_Store
Untracked files:
Untracked: analysis/gd_notes.Rmd
</code></pre>
Note that any generated files, e.g. HTML, png, CSS, etc., are not included in this status report because it is ok for generated content to have uncommitted changes. </details>
</li>
</ul>
<details> <summary> <small><strong>Expand here to see past versions:</strong></small> </summary>
<ul>
<table style="border-collapse:separate; border-spacing:5px;">
<thead>
<tr>
<th style="text-align:left;">
File
</th>
<th style="text-align:left;">
Version
</th>
<th style="text-align:left;">
Author
</th>
<th style="text-align:left;">
Date
</th>
<th style="text-align:left;">
Message
</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:left;">
Rmd
</td>
<td style="text-align:left;">
<a href="https://github.com/willwerscheid/FLASHvestigations/blob/1eda9afdc1ea05d8145c5e2647028fd1421d962b/analysis/matrix_ops.Rmd" target="_blank">1eda9af</a>
</td>
<td style="text-align:left;">
Jason Willwerscheid
</td>
<td style="text-align:left;">
2018-11-05
</td>
<td style="text-align:left;">
wflow_publish(“analysis/matrix_ops.Rmd”)
</td>
</tr>
</tbody>
</table>
</ul>
<p></details></p>
<hr />
<div id="updating-sigma2" class="section level2">
<h2>Updating <span class="math inline">\(\sigma^2\)</span></h2>
<p>Let <span class="math inline">\(Y\)</span> have zeroes where data is missing and let <span class="math inline">\(Z\)</span> be an indicator matrix with ones where data is non-missing and zeroes where data is missing. Write</p>
<p><span class="math display">\[
\begin{aligned}
R^2 = Y^2
&- 2 Y \odot (EL) (EF)'
+ Z \odot ((EL) (EF)')^2 \\
&+ Z \odot (EL^2) (EF^2)'
- Z \odot (EL)^2 ((EF)^2)'
\end{aligned}
\]</span></p>
<div id="var_type-constant" class="section level3">
<h3>var_type = constant</h3>
<p>Let <span class="math inline">\(m\)</span> be the number of non-missing entries in <span class="math inline">\(Y\)</span>. We can write</p>
<p><span class="math display">\[\begin{aligned}
\sigma^2
= \frac{1}{m} (
\text{sum}(Y^2)
&- 2 \cdot \text{sum}((EL) \odot Y (EF))
+ \text{sum}((EL) \odot Z(EF))^2 \\
&+ \text{sum}((EL^2) \odot Z (EF^2))
- \text{sum}((EL)^2 \odot Z (EF)^2)
)
\end{aligned}\]</span></p>
<p>The most expensive operations are the four multiplications of an <span class="math inline">\(n \times p\)</span> matrix by a <span class="math inline">\(p \times k\)</span> matrix. The three involving <span class="math inline">\(Z\)</span> are very cheap if there is no missing data. The old implementation required three multiplications of a <span class="math inline">\(n \times k\)</span> by a <span class="math inline">\(k \times p\)</span> matrix, so there is not likely to be any speedup unless there is missing data. Much more importantly, though, the new implementation does not require the formation of any new <span class="math inline">\(n \times p\)</span> matrices.</p>
</div>
<div id="var_type-by_row" class="section level3">
<h3>var_type = by_row</h3>
<p>Now let <span class="math inline">\(m\)</span> be an <span class="math inline">\(n\)</span>-vector, where <span class="math inline">\(m_i\)</span> denotes the number of non-missing entries in row <span class="math inline">\(Y_{i \bullet}\)</span>. <span class="math inline">\(\sigma^2\)</span> is now an <span class="math inline">\(n\)</span>-vector:</p>
<p><span class="math display">\[\begin{aligned}
\sigma^2
= (1 / m) \odot (\text{rowSums}(Y^2)
&- 2 \cdot \text{rowSums}((EL) \odot Y (EF))
+ \text{rowSums}((EL) \odot Z(EF))^2 \\
&+ \text{rowSums}((EL^2) \odot Z (EF^2))
- \text{rowSums}((EL)^2 \odot Z (EF)^2))
\end{aligned}\]</span></p>
</div>
<div id="var_type-by_column" class="section level3">
<h3>var_type = by_column</h3>
<p>With <span class="math inline">\(m\)</span> a <span class="math inline">\(p\)</span>-vector, where <span class="math inline">\(m_j\)</span> denotes the number of non-missing entries in column <span class="math inline">\(Y_{\bullet j}\)</span>:</p>
<p><span class="math display">\[\begin{aligned}
\sigma^2
= (1 / m) \odot (\text{colSums}(Y^2)
&- 2 \cdot \text{rowSums}(t(EF) \odot (t(EL))Y)
+ \text{rowSums}(t(EF) \odot (t(EL))Z)^2 \\
&+ \text{rowSums}(t(EF^2) \odot (t(EL^2))Z))
- \text{rowSums}(t(EF)^2 \odot t(EL)^2 Z))
\end{aligned}\]</span></p>
<p>(I write it in this form to avoid transposing <span class="math inline">\(Y\)</span>.)</p>
</div>
<div id="greedy-updates" class="section level3">
<h3>Greedy updates</h3>
<p>In the course of optimizing a single factor/loading pair, one can exploit the fact that only one column in each of <span class="math inline">\(EL\)</span>, <span class="math inline">\(EF\)</span>, <span class="math inline">\(EL^2\)</span>, and <span class="math inline">\(EF^2\)</span> change.</p>
</div>
</div>
<div id="updating-loadings" class="section level2">
<h2>Updating loadings</h2>
<p>Instead of updating loading 1, then factor 1, then loading 2, etc., one can much more efficiently update all loadings (potentially in parallel), then all factors.</p>
<div id="calculating-the-ebnm-s2s" class="section level3">
<h3>Calculating the EBNM <code>s2</code>s</h3>
<p>The old algorithm calculates <code>s2 = 1/(tau %*% f$EF2[, k])</code>, where the entries of <code>tau</code> corresponding to missing data have been set to zero.</p>
<p>Let <span class="math inline">\(S\)</span> be the matrix of <code>s2</code>s, with the <span class="math inline">\(i\)</span>th column giving the <code>s2</code>s for the <span class="math inline">\(i\)</span>th loading. Then for <code>var_type = constant</code> or <code>var_type = by_row</code>, <span class="math inline">\(S\)</span> may be calculated as <span class="math display">\[ S = \sigma^2 / Z(EF^2), \]</span> where “<span class="math inline">\(/\)</span>” is elementwise for <code>var_type = by_row</code>. Again the calculation is simplified if there is no missing data: here, <span class="math inline">\(Z(EF^2)\)</span> is simply a matrix where each row is the <span class="math inline">\(k\)</span>-vector <span class="math inline">\(\text{colSums}(EF^2)\)</span>.</p>
<p>For <code>var_type = by_column</code>, <span class="math display">\[ S = 1 / Z(\tau \odot_b EF^2), \]</span> where <span class="math inline">\(\odot_b\)</span> denotes that broadcasting is to be performed (in the sense that <code>R</code> uses it).</p>
<p>This is essentially the same as before, but <code>tau</code> does not need to be stored as a matrix.</p>
</div>
<div id="calculating-the-ebnm-xs" class="section level3">
<h3>Calculating the EBNM <code>x</code>s</h3>
<p>The old algorithm calculates <code>x = ((Rk * tau) %*% f$EF[, k]) * s2</code>, which requires storing and updating <code>Rk</code>. For <code>var_type = constant</code> and <code>var_type = by_row</code>, one may write:</p>
<p><span class="math display">\[ X_{\bullet k} = \tau \odot (Y - \sum_{i: i \ne k} Z \odot (EL)_{\bullet i}(EF)_{\bullet i}') (EF)_{\bullet k} \odot S_{\bullet k}. \]</span></p>
<p>Note that <span class="math inline">\((Z \odot (EL)_{\bullet i} (EF)_{\bullet i}') (EF)_{\bullet k}\)</span> can be written as <span class="math display">\[ (EL)_{\bullet i} \odot Z ((EF)_{\bullet i} \odot (EF)_{\bullet k}) \]</span> so <span class="math display">\[\left(\sum_{i: i \ne k} Z \odot (EL)_{\bullet i}(EF)_{\bullet i}'\right) (EF)_{\bullet k}
= \text{rowSums} \left((EL)_{\bullet -k} \odot Z((EF)_{\bullet k} \odot_b (EF)_{\bullet -k}) \right).\]</span></p>
<p>Again, the performance savings are not likely to be substantial unless there is no missing data, but this method does not require the formation of any new <span class="math inline">\(n \times p\)</span> matrices.</p>
<p>For <code>var_type = by_column</code>, write <span class="math display">\[ X_{\bullet k} = (Y - \sum_{i: i \ne k} Z \odot (EL)_{\bullet i}(EF)_{\bullet i}') (\tau \odot (EF)_{\bullet k}) \odot S_{\bullet k}. \]</span></p>
</div>
<div id="an-idea-for-parallelizing-the-ebnm-problems" class="section level3">
<h3>An idea for parallelizing the EBNM problems</h3>
<p>The above could also be implemented as follows:</p>
<ol style="list-style-type: decimal">
<li><p>Calculate the <span class="math inline">\(n \times k\)</span> matrix <span class="math inline">\(W = (Y - Z \odot (EL) (EF)')(EF)\)</span>. When there is missing data, this does require the temporary formation of a new <span class="math inline">\(n \times p\)</span> matrix, but it does not need to be stored.</p></li>
<li><p><span class="math inline">\((Z \odot (EL)_{\bullet k} (EF)_{\bullet k}') (EF)_{\bullet k}\)</span> can be written as <span class="math display">\[ (EL)_{\bullet k} \odot Z ((EF)_{\bullet k}^2). \]</span> Form the <span class="math inline">\(n \times k\)</span> matrix <span class="math inline">\(U = (EL) \odot Z(EF)^2\)</span> in one go.</p></li>
<li><p>For <span class="math inline">\(k = 1\)</span>, calculate <span class="math display">\[ X_{\bullet 1} = \tau \odot (W_{\bullet 1} + U_{\bullet 1}) \odot S_{\bullet 1}\]</span> and solve the EBNM problem. This changes <span class="math inline">\((EL)_{\bullet k}\)</span>, so <span class="math inline">\(W\)</span> needs to be updated:</p></li>
</ol>
<p><span class="math display">\[\begin{aligned}
W^{\text{new}}
&= W^{\text{old}}
+ \left( Z \odot ((EL)_{\bullet k}^{\text{old}} - (EL)_{\bullet k}^{\text{new}}) (EF)_{\bullet k}' \right) (EF) \\
&= W^{\text{old}}
+ ((EL)_{\bullet k}^{\text{old}} - (EL)_{\bullet k}^{\text{new}})
\odot Z((EF)_{\bullet k} \odot_b (EF)),
\end{aligned}\]</span></p>
<p>Then repeat for <span class="math inline">\(k = 2, 3, \ldots\)</span></p>
<p>But if one simply omits the update of of <span class="math inline">\(W\)</span>, parallelization is simple. If the updates of <span class="math inline">\((EL)\)</span> are small, then this omission might be justified.</p>
</div>
</div>
<div id="updating-factors" class="section level2">
<h2>Updating factors</h2>
<p>Factor updates can easily be obtained by reversing the roles of, on the one hand, <span class="math inline">\(EL\)</span> and <span class="math inline">\(EF\)</span> and, on the other, <code>var_type = by_row</code> and <code>var_type = by_column</code>.</p>
</div>
<div id="summary" class="section level2">
<h2>Summary</h2>
<p>With this implementation, the only <span class="math inline">\(n \times p\)</span> matrices that ever need to be handled are <span class="math inline">\(Y\)</span> and, if data is missing, <span class="math inline">\(Z\)</span> (and <span class="math inline">\(Z\)</span> can be stored as a matrix of integers). So it should be possible to fit a flash object using only slightly more memory than that required to store the data itself.</p>
</div>
<div id="session-information" class="section level2">
<h2>Session information</h2>
<pre class="r"><code>sessionInfo()</code></pre>
<pre><code>R version 3.4.3 (2017-11-30)
Platform: x86_64-apple-darwin15.6.0 (64-bit)
Running under: macOS High Sierra 10.13.6
Matrix products: default
BLAS: /Library/Frameworks/R.framework/Versions/3.4/Resources/lib/libRblas.0.dylib
LAPACK: /Library/Frameworks/R.framework/Versions/3.4/Resources/lib/libRlapack.dylib
locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8
attached base packages:
[1] stats graphics grDevices utils datasets methods base
loaded via a namespace (and not attached):
[1] workflowr_1.0.1 Rcpp_0.12.19 digest_0.6.15
[4] rprojroot_1.3-2 R.methodsS3_1.7.1 backports_1.1.2
[7] git2r_0.21.0 magrittr_1.5 evaluate_0.10.1
[10] stringi_1.2.4 whisker_0.3-2 R.oo_1.21.0
[13] R.utils_2.6.0 rmarkdown_1.8 tools_3.4.3
[16] stringr_1.3.0 yaml_2.1.17 compiler_3.4.3
[19] htmltools_0.3.6 knitr_1.20 </code></pre>
</div>
<!-- Adjust MathJax settings so that all math formulae are shown using
TeX fonts only; see
http://docs.mathjax.org/en/latest/configuration.html. This will make
the presentation more consistent at the cost of the webpage sometimes
taking slightly longer to load. Note that this only works because the
footer is added to webpages before the MathJax javascript. -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
"HTML-CSS": { availableFonts: ["TeX"] }
});
</script>
<hr>
<p>
This reproducible <a href="http://rmarkdown.rstudio.com">R Markdown</a>
analysis was created with
<a href="https://github.com/jdblischak/workflowr">workflowr</a> 1.0.1
</p>
<hr>
</div>
</div>
</div>
<script>
// add bootstrap table styles to pandoc tables
function bootstrapStylePandocTables() {
$('tr.header').parent('thead').parent('table').addClass('table table-condensed');
}
$(document).ready(function () {
bootstrapStylePandocTables();
});
</script>
<!-- dynamically load mathjax for compatibility with self-contained -->
<script>
(function () {
var script = document.createElement("script");
script.type = "text/javascript";
script.src = "https://mathjax.rstudio.com/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML";
document.getElementsByTagName("head")[0].appendChild(script);
})();
</script>
</body>
</html>