[mlpack-git] master: Add implementation of convolution using svd to speeded up the computation. (1068cf5)

[gitdub at big.cc.gt.atl.ga.us]

Repository : https://github.com/mlpack/mlpack

On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/e2beb217f3e17729b73f9edc05601195e92f775d...8f85309ae9be40e819b301b39c9a940aa28f3bb2

>---------------------------------------------------------------

commit 1068cf5cfc18982bcd4a671cc08242948f7730e3
Author: Marcus Edel <marcus.edel at fu-berlin.de>
Date:   Tue Apr 21 22:39:19 2015 +0200

    Add implementation of convolution using svd to speeded up the computation.


>---------------------------------------------------------------

1068cf5cfc18982bcd4a671cc08242948f7730e3
 .../ann/convolution_rules/svd_convolution.hpp      | 109 +++++++++++++++++++++
 1 file changed, 109 insertions(+)

diff --git a/src/mlpack/methods/ann/convolution_rules/svd_convolution.hpp b/src/mlpack/methods/ann/convolution_rules/svd_convolution.hpp
new file mode 100644
index 0000000..d2352de
--- /dev/null
+++ b/src/mlpack/methods/ann/convolution_rules/svd_convolution.hpp
@@ -0,0 +1,109 @@
+/**
+ * @file svd_convolution.hpp
+ * @author Marcus Edel
+ *
+ * Implementation of the convolution using the singular value decomposition to
+ * speeded up the computation.
+ */
+#ifndef __MLPACK_METHODS_ANN_CONVOLUTION_RULES_SVD_CONVOLUTION_HPP
+#define __MLPACK_METHODS_ANN_CONVOLUTION_RULES_SVD_CONVOLUTION_HPP
+
+#include <mlpack/core.hpp>
+#include "border_modes.hpp"
+#include "fft_convolution.hpp"
+#include "naive_convolution.hpp"
+
+namespace mlpack {
+namespace ann /** Artificial Neural Network. */ {
+
+/**
+ * Computes the two-dimensional convolution using singular value decomposition.
+ * This class allows specification of the type of the border type. The
+ * convolution can be compute with the valid border type of the full border
+ * type (default).
+ *
+ * FullConvolution: returns the full two-dimensional convolution.
+ * ValidConvolution: returns only those parts of the convolution that are
+ * computed without the zero-padded edges.
+ *
+ * @tparam BorderMode Type of the border mode (FullConvolution or
+ * ValidConvolution).
+ */
+template<typename BorderMode = FullConvolution>
+class SVDConvolution
+{
+ public:
+  /*
+   * Perform a convolution (valid or full mode) using singular value
+   * decomposition. By using singular value decomposition of the filter matrix
+   * the convolution can be expressed as a sum of outer products. Each product
+   * can be computed efficiently as convolution with a row and a column vector.
+   * The individual convolutions are computed with the naive implementation wich
+   * is fast if the filter is low-dimensional.
+   *
+   * @param input Input used to perform the convolution.
+   * @param filter Filter used to perform the conolution.
+   * @param output Output data that contains the results of the convolution.
+   */
+  template<typename eT>
+  static void Convolution(const arma::Mat<eT>& input,
+                          const arma::Mat<eT>& filter,
+                          arma::Mat<eT>& output)
+  {
+    // Use the naive convolution in case the filter isn't two dimensional or the
+    // filter is bigger than the input.
+    if (filter.n_rows > input.n_rows || filter.n_cols > input.n_cols ||
+        filter.n_rows == 1 || filter.n_cols == 1)
+    {
+      NaiveConvolution<BorderMode>::Convolution(input, filter, output);
+    }
+    else
+    {
+      arma::Mat<eT> U, V, subOutput;
+      arma::Col<eT> s;
+
+      arma::svd_econ(U, s, V, filter);
+
+      // Rank approximation using the singular values calculated with singular
+      // value decomposition of dense filter matrix.
+      const size_t rank = arma::sum(s > (s.n_elem * arma::max(s) *
+          arma::datum::eps));
+
+      // Test for separability based on the rank of the kernel and take
+      // advantage of the low rank.
+      if (rank * (filter.n_rows + filter.n_cols) < filter.n_elem)
+      {
+        arma::Mat<eT> subFilter = V.unsafe_col(0) * s(0);
+        NaiveConvolution<BorderMode>::Convolution(input, subFilter, subOutput);
+
+        subOutput = subOutput.t();
+        NaiveConvolution<BorderMode>::Convolution(subOutput, U.unsafe_col(0),
+            output);
+
+        for (size_t r = 1; r < rank; r++)
+        {
+          subFilter = V.unsafe_col(r) * s(r);
+          NaiveConvolution<BorderMode>::Convolution(input, subFilter,
+              subOutput);
+
+          arma::Mat<eT> temp;
+          subOutput = subOutput.t();
+          NaiveConvolution<BorderMode>::Convolution(subOutput, U.unsafe_col(r),
+              temp);
+          output += temp;
+        }
+
+        output = output.t();
+      }
+      else
+      {
+        FFTConvolution<BorderMode>::Convolution(input, filter, output);
+      }
+    }
+  }
+};  // class SVDConvolution
+
+}; // namespace ann
+}; // namespace mlpack
+
+#endif