[mlpack-git] master: Address some stylistic issues (66e6220)

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


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

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

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

commit 66e6220d6026ce6ff59d6a7f9ceb99c6c487ba7c
Author: Stephen Tu <tu.stephenl at gmail.com>
Date:   Sun Jan 11 15:35:24 2015 -0800

    Address some stylistic issues
    
    also add more comments and better error messages


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

66e6220d6026ce6ff59d6a7f9ceb99c6c487ba7c
 .../matrix_completion/matrix_completion.hpp        | 25 +++++----------
 .../matrix_completion/matrix_completion_impl.hpp   | 37 ++++++++++++++--------
 src/mlpack/tests/matrix_completion_test.cpp        | 21 +++++++++---
 3 files changed, 48 insertions(+), 35 deletions(-)

diff --git a/src/mlpack/methods/matrix_completion/matrix_completion.hpp b/src/mlpack/methods/matrix_completion/matrix_completion.hpp
index 25a2ddf..382b748 100644
--- a/src/mlpack/methods/matrix_completion/matrix_completion.hpp
+++ b/src/mlpack/methods/matrix_completion/matrix_completion.hpp
@@ -33,13 +33,13 @@ namespace matrix_completion {
  * An example of how to use this class is shown below:
  *
  * @code
- * size_t m, n;        // size of unknown matrix
- * arma::umat indices; // contains the known indices [2 x n_entries]
- * arma::vec values;   // contains the known values [n_entries]
+ * size_t m, n;         // size of unknown matrix
+ * arma::umat indices;  // contains the known indices [2 x n_entries]
+ * arma::vec values;    // contains the known values [n_entries]
+ * arma::mat recovered; // will contain the completed matrix
  *
  * MatrixCompletion mc(m, n, indices, values);
- * mc.Recover();
- * mc.Recovered();     // access completed matrix
+ * mc.Recover(recovered);
  * @endcode
  *
  * @see LRSDP
@@ -101,17 +101,16 @@ class MatrixCompletion
 
   /**
    * Solve the underlying SDP to fill in the remaining values.
+   *
+   * @param recovered Will contain the completed matrix.
    */
-  void Recover();
+  void Recover(arma::mat& recovered);
 
   //! Return the underlying SDP.
   const optimization::LRSDP& Sdp() const { return sdp; }
   //! Modify the underlying SDP.
   optimization::LRSDP& Sdp() { return sdp; }
 
-  //! Return the recovered matrix.
-  const arma::mat& Recovered() const { return recovered; }
-
  private:
   size_t m;
 
@@ -123,8 +122,6 @@ class MatrixCompletion
 
   optimization::LRSDP sdp;
 
-  arma::mat recovered;
-
   void checkValues();
 
   void initSdp();
@@ -133,12 +130,6 @@ class MatrixCompletion
   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
diff --git a/src/mlpack/methods/matrix_completion/matrix_completion_impl.hpp b/src/mlpack/methods/matrix_completion/matrix_completion_impl.hpp
index 1ceb5c9..f40e2c2 100644
--- a/src/mlpack/methods/matrix_completion/matrix_completion_impl.hpp
+++ b/src/mlpack/methods/matrix_completion/matrix_completion_impl.hpp
@@ -16,7 +16,7 @@ MatrixCompletion::MatrixCompletion(const size_t m,
                                    const arma::vec& values,
                                    const size_t r)
   : m(m), n(n), indices(indices), values(values),
-    sdp(indices.n_cols, 0, CreateInitialPoint(m, n, r))
+    sdp(indices.n_cols, 0, arma::randu<arma::mat>(m + n, r))
 {
   checkValues();
   initSdp();
@@ -39,7 +39,9 @@ MatrixCompletion::MatrixCompletion(const size_t m,
                                    const arma::umat& indices,
                                    const arma::vec& values)
   : m(m), n(n), indices(indices), values(values),
-    sdp(indices.n_cols, 0, CreateInitialPoint(m, n, DefaultRank(m, n, indices.n_cols)))
+    sdp(indices.n_cols, 0,
+        arma::randu<arma::mat>(m + n,
+                               DefaultRank(m, n, indices.n_cols)))
 {
   checkValues();
   initSdp();
@@ -48,15 +50,22 @@ MatrixCompletion::MatrixCompletion(const size_t m,
 void MatrixCompletion::checkValues()
 {
   if (indices.n_rows != 2)
-    Log::Fatal << "indices.n_rows != 2" << std::endl;
+    Log::Fatal << "matrix of constraint indices does not have 2 rows"
+      << std::endl;
 
   if (indices.n_cols != values.n_elem)
-    Log::Fatal << "indices.n_cols != values.n_elem" << std::endl;
+    Log::Fatal << "the number of constraint indices "
+      << "(columns of constraint indices matrix) "
+      << "does not match the number of constraint values "
+      << "(length of constraint value vector)"
+      << std::endl;
 
   for (size_t i = 0; i < values.n_elem; i++)
   {
     if (indices(0, i) >= m || indices(1, i) >= n)
-      Log::Fatal << "index out of bounds" << std::endl;
+      Log::Fatal << "indices (" << indices(0, i) << ", " << indices(1, i) << ")"
+        << " are out of bounds for matrix of size " << m << " x " << "n"
+        << std::endl;
   }
 }
 
@@ -73,7 +82,7 @@ void MatrixCompletion::initSdp()
   }
 }
 
-void MatrixCompletion::Recover()
+void MatrixCompletion::Recover(arma::mat& recovered)
 {
   recovered = sdp.Function().GetInitialPoint();
   sdp.Optimize(recovered);
@@ -85,6 +94,14 @@ size_t MatrixCompletion::DefaultRank(const size_t m,
                                      const size_t n,
                                      const size_t p)
 {
+  // If r = O(sqrt(p)), then we are guaranteed an exact solution.
+  // For more details, see
+  //
+  //   On the rank of extreme matrices in semidefinite programs and the
+  //   multiplicity of optimal eigenvalues.
+  //   Pablo Moscato, Michael Norman, and Gabor Pataki.
+  //   Math Oper. Res., 23(2). 1998.
+
   const size_t mpn = m + n;
   float r = 0.5 + sqrt(0.25 + 2 * p);
   if (ceil(r) > mpn)
@@ -92,14 +109,6 @@ size_t MatrixCompletion::DefaultRank(const size_t m,
   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
 
diff --git a/src/mlpack/tests/matrix_completion_test.cpp b/src/mlpack/tests/matrix_completion_test.cpp
index 6392c9d..df7020f 100644
--- a/src/mlpack/tests/matrix_completion_test.cpp
+++ b/src/mlpack/tests/matrix_completion_test.cpp
@@ -15,7 +15,19 @@ using namespace mlpack::matrix_completion;
 
 BOOST_AUTO_TEST_SUITE(MatrixCompletionTest);
 
-BOOST_AUTO_TEST_CASE(GaussianMatrixCompletionSDP)
+/**
+ * A matrix completion test.
+ *
+ * The matrix X = F1 F2^T was generated such that the entries of Fi were iid
+ * from the uniform distribution on [0, 1]. Then, enough random samples
+ * (without replacement) were taking from X such that exact recovered was
+ * possible.
+ *
+ * X is stored in the file "completion_X.csv" and the indices are stored in the
+ * file "completion_indices.csv". Recovery was verified by solving the SDP with
+ * Mosek.
+ */
+BOOST_AUTO_TEST_CASE(UniformMatrixCompletionSDP)
 {
   arma::mat Xorig, values;
   arma::umat indices;
@@ -29,18 +41,19 @@ BOOST_AUTO_TEST_CASE(GaussianMatrixCompletionSDP)
     values(i) = Xorig(indices(0, i), indices(1, i));
   }
 
+  arma::mat recovered;
   MatrixCompletion mc(Xorig.n_rows, Xorig.n_cols, indices, values);
-  mc.Recover();
+  mc.Recover(recovered);
 
   const double err =
-    arma::norm(Xorig - mc.Recovered(), "fro") /
+    arma::norm(Xorig - recovered, "fro") /
     arma::norm(Xorig, "fro");
   BOOST_REQUIRE_SMALL(err, 1e-5);
 
   for (size_t i = 0; i < indices.n_cols; ++i)
   {
     BOOST_REQUIRE_CLOSE(
-      mc.Recovered()(indices(0, i), indices(1, i)),
+      recovered(indices(0, i), indices(1, i)),
       Xorig(indices(0, i), indices(1, i)),
       1e-5);
   }



More information about the mlpack-git mailing list