[mlpack-git] master: Address some stylistic issues (132b7df)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Mon Jan 12 17:31:55 EST 2015
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/2f5aa71b3e3b9f14ed825a20a69759471edffb31...d81511957f5fcc5e46cee49c6103e3ae7ac1d45d
>---------------------------------------------------------------
commit 132b7dff3ec232c3ff17246fd726beaa52e0821c
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
>---------------------------------------------------------------
132b7dff3ec232c3ff17246fd726beaa52e0821c
.../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