[mlpack-git] master: First cut at matrix completion method implementation (13f101d)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Mon Jan 12 17:31:49 EST 2015
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/2f5aa71b3e3b9f14ed825a20a69759471edffb31...d81511957f5fcc5e46cee49c6103e3ae7ac1d45d
>---------------------------------------------------------------
commit 13f101d39180b1888efb75a59af8c70723fbf2a0
Author: Stephen Tu <stephent at berkeley.edu>
Date: Sun Jan 4 01:09:56 2015 -0800
First cut at matrix completion method implementation
>---------------------------------------------------------------
13f101d39180b1888efb75a59af8c70723fbf2a0
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