<p>d(X.col(i), X.col(j)) = d(W H.col(i), W H.col(j)).</p>

<p>For the L2 distance (which is fine for now), we can show that this is the Mahalanobis distance with M^{-1} = W^T W.  Decompose M^{-1} = L L^T (Cholesky decomposition), and then multiply H by L^T to obtain H' (this takes O(r^2 n) time).  Then, once this is done,</p>

<p>d(X.col(i), X.col(j)) = d(H'.col(i), H'.col(j))</p>

<p>and each distance calculation takes only O(r) time.  We can use simple nearest neighbor search out of the box on H', then.</p>

<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">&mdash;<br>Reply to this email directly or <a href="https://github.com/mlpack/mlpack/issues/406#issuecomment-86233475">view it on GitHub</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFD2F56cc07Zz_Oji3IzsEHHv8Wjtks5n4yn5gaJpZM4Di-rj.gif" width="1" /></p>
<div itemscope itemtype="http://schema.org/EmailMessage">
  <div itemprop="action" itemscope itemtype="http://schema.org/ViewAction">
    <link itemprop="url" href="https://github.com/mlpack/mlpack/issues/406#issuecomment-86233475"></link>
    <meta itemprop="name" content="View Issue"></meta>
  </div>
  <meta itemprop="description" content="View this Issue on GitHub"></meta>
</div>