[mlpack-git] master: First cut at matrix completion method implementation (602a2a9)

gitdub at big.cc.gt.atl.ga.us gitdub at big.cc.gt.atl.ga.us
Thu Mar 5 22:10:17 EST 2015


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

On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40

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

commit 602a2a9408f30e2c7a46f69b90bf117332689dec
Author: Stephen Tu <stephent at berkeley.edu>
Date:   Sun Jan 4 01:09:56 2015 -0800

    First cut at matrix completion method implementation


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

602a2a9408f30e2c7a46f69b90bf117332689dec
 src/mlpack/methods/CMakeLists.txt                  |  1 +
 .../{quic_svd => matrix_completion}/CMakeLists.txt |  4 +-
 .../matrix_completion/matrix_completion.hpp        | 66 +++++++++++++++++
 .../matrix_completion/matrix_completion_impl.hpp   | 83 ++++++++++++++++++++++
 src/mlpack/tests/CMakeLists.txt                    |  1 +
 src/mlpack/tests/matrix_completion_test.cpp        | 18 +++++
 6 files changed, 171 insertions(+), 2 deletions(-)

diff --git a/src/mlpack/methods/CMakeLists.txt b/src/mlpack/methods/CMakeLists.txt
index 8aefd69..6215b2c 100644
--- a/src/mlpack/methods/CMakeLists.txt
+++ b/src/mlpack/methods/CMakeLists.txt
@@ -17,6 +17,7 @@ set(DIRS
   logistic_regression
   lsh
 #  mvu
+  matrix_completion
   naive_bayes
   nca
   neighbor_search
diff --git a/src/mlpack/methods/quic_svd/CMakeLists.txt b/src/mlpack/methods/matrix_completion/CMakeLists.txt
similarity index 88%
copy from src/mlpack/methods/quic_svd/CMakeLists.txt
copy to src/mlpack/methods/matrix_completion/CMakeLists.txt
index c89b866..282021f 100644
--- a/src/mlpack/methods/quic_svd/CMakeLists.txt
+++ b/src/mlpack/methods/matrix_completion/CMakeLists.txt
@@ -1,8 +1,8 @@
 # Define the files we need to compile.
 # Anything not in this list will not be compiled into MLPACK.
 set(SOURCES
-  quic_svd.hpp
-  quic_svd_impl.hpp
+  matrix_completion.hpp
+  matrix_completion_impl.hpp
 )
 
 # Add directory name to sources.
diff --git a/src/mlpack/methods/matrix_completion/matrix_completion.hpp b/src/mlpack/methods/matrix_completion/matrix_completion.hpp
new file mode 100644
index 0000000..0353459
--- /dev/null
+++ b/src/mlpack/methods/matrix_completion/matrix_completion.hpp
@@ -0,0 +1,66 @@
+/**
+ * @file matrix_completion.hpp
+ * @author Stephen Tu
+ *
+ * A thin wrapper around nuclear norm minimization to solve
+ * low rank matrix completion problems.
+ */
+#ifndef __MLPACK_METHODS_MATRIX_COMPLETION_MATRIX_COMPLETION_HPP
+#define __MLPACK_METHODS_MATRIX_COMPLETION_MATRIX_COMPLETION_HPP
+
+#include <mlpack/core/optimizers/lrsdp/lrsdp.hpp>
+
+namespace mlpack {
+namespace matrix_completion {
+
+class MatrixCompletion
+{
+public:
+  MatrixCompletion(const size_t m,
+                   const size_t n,
+                   const arma::mat& entries,
+                   const size_t r);
+
+  MatrixCompletion(const size_t m,
+                   const size_t n,
+                   const arma::mat& entries,
+                   const arma::mat& initialPoint);
+
+  MatrixCompletion(const size_t m,
+                   const size_t n,
+                   const arma::mat& entries);
+
+  void Recover();
+
+  const arma::mat& Recovered() const { return recovered; }
+  arma::mat& Recovered() { return recovered; }
+
+private:
+  size_t m;
+  size_t n;
+  arma::mat entries;
+
+  optimization::LRSDP sdp;
+  arma::mat recovered;
+
+  void initSdp();
+
+  static size_t
+  DefaultRank(const size_t m,
+              const size_t n,
+              const size_t p);
+
+  static arma::mat
+  CreateInitialPoint(const size_t m,
+                     const size_t n,
+                     const size_t r);
+
+};
+
+} // namespace matrix_completion
+} // namespace mlpack
+
+// Include implementation.
+#include "matrix_completion_impl.hpp"
+
+#endif
diff --git a/src/mlpack/methods/matrix_completion/matrix_completion_impl.hpp b/src/mlpack/methods/matrix_completion/matrix_completion_impl.hpp
new file mode 100644
index 0000000..1a8fdad
--- /dev/null
+++ b/src/mlpack/methods/matrix_completion/matrix_completion_impl.hpp
@@ -0,0 +1,83 @@
+/**
+ * @file matrix_completion_impl.hpp
+ * @author Stephen Tu
+ *
+ * Implementation of MatrixCompletion class.
+ */
+#ifndef __MLPACK_METHODS_MATRIX_COMPLETION_MATRIX_COMPLETION_IMPL_HPP
+#define __MLPACK_METHODS_MATRIX_COMPLETION_MATRIX_COMPLETION_IMPL_HPP
+
+namespace mlpack {
+namespace matrix_completion {
+
+MatrixCompletion::MatrixCompletion(const size_t m,
+                                   const size_t n,
+                                   const arma::mat& entries,
+                                   const size_t r)
+  : m(m), n(n), entries(entries),
+    sdp(entries.n_cols, 0, CreateInitialPoint(m, n, r))
+{
+  initSdp();
+}
+
+MatrixCompletion::MatrixCompletion(const size_t m,
+                                   const size_t n,
+                                   const arma::mat& entries,
+                                   const arma::mat& initialPoint)
+  : m(m), n(n), entries(entries),
+    sdp(entries.n_cols, 0, initialPoint)
+{
+  initSdp();
+}
+
+MatrixCompletion::MatrixCompletion(const size_t m,
+                                   const size_t n,
+                                   const arma::mat& entries)
+  : m(m), n(n), entries(entries),
+    sdp(entries.n_cols, 0, CreateInitialPoint(m, n, DefaultRank(m, n, entries.n_cols)))
+{
+  initSdp();
+}
+
+void MatrixCompletion::initSdp()
+{
+  sdp.SparseC().eye(m + n, m + n);
+  sdp.SparseB() = 2. * entries.row(2);
+  const size_t p = entries.n_cols;
+  for (size_t i = 0; i < p; i++)
+  {
+    sdp.SparseA()[i].zeros(m + n, m + n);
+    sdp.SparseA()[i](entries(0, i), m + entries(1, i)) = 1.;
+    sdp.SparseA()[i](m + entries(1, i), entries(0, i)) = 1.;
+  }
+}
+
+void MatrixCompletion::Recover()
+{
+  recovered = sdp.Function().GetInitialPoint();
+  sdp.Optimize(recovered);
+}
+
+size_t MatrixCompletion::DefaultRank(const size_t m,
+                                     const size_t n,
+                                     const size_t p)
+{
+  const size_t mpn = m + n;
+  float r = 0.5 + sqrt(0.25 + 2 * p);
+  if (ceil(r) > mpn)
+    r = mpn; // An upper bound on the dimension.
+  return ceil(r);
+}
+
+arma::mat MatrixCompletion::CreateInitialPoint(const size_t m,
+                                               const size_t n,
+                                               const size_t r)
+{
+  const size_t mpn = m + n;
+  return arma::randu<arma::mat>(mpn, r);
+}
+
+} // namespace matrix_completion
+} // namespace mlpack
+
+#endif
diff --git a/src/mlpack/tests/CMakeLists.txt b/src/mlpack/tests/CMakeLists.txt
index b985d26..37a4291 100644
--- a/src/mlpack/tests/CMakeLists.txt
+++ b/src/mlpack/tests/CMakeLists.txt
@@ -31,6 +31,7 @@ add_executable(mlpack_test
   lrsdp_test.cpp
   lsh_test.cpp
   math_test.cpp
+  matrix_completion_test.cpp
   metric_test.cpp
   nbc_test.cpp
   nca_test.cpp
diff --git a/src/mlpack/tests/matrix_completion_test.cpp b/src/mlpack/tests/matrix_completion_test.cpp
new file mode 100644
index 0000000..b325696
--- /dev/null
+++ b/src/mlpack/tests/matrix_completion_test.cpp
@@ -0,0 +1,18 @@
+/**
+ * @file matrix_completion_test.cpp
+ * @author Stephen Tu
+ *
+ * Tests for matrix completion
+ */
+#include <mlpack/core.hpp>
+#include <mlpack/methods/matrix_completion/matrix_completion.hpp>
+
+#include <boost/test/unit_test.hpp>
+#include "old_boost_test_definitions.hpp"
+
+using namespace mlpack;
+using namespace mlpack::matrix_completion;
+
+BOOST_AUTO_TEST_SUITE(MatrixCompletionTest);
+
+BOOST_AUTO_TEST_SUITE_END();



More information about the mlpack-git mailing list