[mlpack-git] master: Merge remote-tracking branch 'mlpack/master' into testsensing (98afef2)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Thu Mar 5 22:10:40 EST 2015
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40
>---------------------------------------------------------------
commit 98afef2651b59dcae8093439dd5fed156f9452ad
Merge: 0243bd5 3ffdd14
Author: Stephen Tu <tu.stephenl at gmail.com>
Date: Mon Jan 5 15:22:54 2015 -0800
Merge remote-tracking branch 'mlpack/master' into testsensing
>---------------------------------------------------------------
98afef2651b59dcae8093439dd5fed156f9452ad
COPYRIGHT.txt | 5 +-
src/mlpack/core.hpp | 1 +
.../simple_residue_termination.hpp | 2 +-
.../layer/{bias_layer.hpp => softmax_layer.hpp} | 55 +-
.../ann/performance_functions/cee_function.hpp | 55 +
.../ann/performance_functions/mse_function.hpp | 42 +
.../ann/performance_functions/sse_function.hpp | 42 +
src/mlpack/tests/activation_functions_test.cpp | 380 ++++++
src/mlpack/tests/connection_traits_test.cpp | 82 ++
src/mlpack/tests/data/erdosrenyi-n100.csv | 1440 ++++++++++++++++++++
src/mlpack/tests/init_rules_test.cpp | 75 +
src/mlpack/tests/layer_traits_test.cpp | 68 +
src/mlpack/tests/lrsdp_test.cpp | 73 +-
src/mlpack/tests/nmf_test.cpp | 8 +-
14 files changed, 2280 insertions(+), 48 deletions(-)
diff --cc src/mlpack/tests/lrsdp_test.cpp
index 3f84fc1,d9b1697..843a870
--- a/src/mlpack/tests/lrsdp_test.cpp
+++ b/src/mlpack/tests/lrsdp_test.cpp
@@@ -118,94 -118,74 +118,161 @@@ BOOST_AUTO_TEST_CASE(Johnson844LovaszTh
}
}
+
+ /**
+ * Create an unweighted graph laplacian from the edges.
+ */
+ void CreateSparseGraphLaplacian(const arma::mat& edges,
+ arma::sp_mat& laplacian)
+ {
+ // Get the number of vertices in the problem.
+ const size_t vertices = max(max(edges)) + 1;
+
+ laplacian.zeros(vertices, vertices);
+
+ for (size_t i = 0; i < edges.n_cols; ++i)
+ {
+ laplacian(edges(0, i), edges(1, i)) = -1.0;
+ laplacian(edges(1, i), edges(0, i)) = -1.0;
+ }
+
+ for (size_t i = 0; i < vertices; ++i)
+ {
+ laplacian(i, i) = -arma::accu(laplacian.row(i));
+ }
+ }
+
+ BOOST_AUTO_TEST_CASE(ErdosRenyiRandomGraphMaxCutSDP)
+ {
+ // Load the edges.
+ arma::mat edges;
+ data::Load("erdosrenyi-n100.csv", edges, true);
+
+ arma::sp_mat laplacian;
+ CreateSparseGraphLaplacian(edges, laplacian);
+
+ float r = 0.5 + sqrt(0.25 + 2 * edges.n_cols);
+ if (ceil(r) > laplacian.n_rows)
+ r = laplacian.n_rows;
+
+ // initialize coordinates to a feasible point
+ arma::mat coordinates(laplacian.n_rows, ceil(r));
+ coordinates.zeros();
+ for (size_t i = 0; i < coordinates.n_rows; ++i)
+ {
+ coordinates(i, i % coordinates.n_cols) = 1.;
+ }
+
+ LRSDP maxcut(laplacian.n_rows, 0, coordinates);
+ maxcut.SparseC() = laplacian;
+ maxcut.SparseC() *= -1.; // need to minimize the negative
+ maxcut.SparseB().ones(laplacian.n_rows);
+ for (size_t i = 0; i < laplacian.n_rows; ++i)
+ {
+ maxcut.SparseA()[i].zeros(laplacian.n_rows, laplacian.n_rows);
+ maxcut.SparseA()[i](i, i) = 1.;
+ }
+
+ const double finalValue = maxcut.Optimize(coordinates);
+ const arma::mat rrt = coordinates * trans(coordinates);
+
+ for (size_t i = 0; i < laplacian.n_rows; ++i)
+ {
+ BOOST_REQUIRE_CLOSE(rrt(i, i), 1., 1e-5);
+ }
+
+ // Final value taken by solving with Mosek
+ BOOST_REQUIRE_CLOSE(finalValue, -3672.7, 1e-1);
+ }
+
/**
+ * Test a nuclear norm minimization SDP.
+ *
+ * Specifically, fix an unknown m x n matrix X. Our goal is to recover X from p
+ * measurements of X, where the i-th measurement is of the form
+ *
+ * b_i = dot(A_i, X)
+ *
+ * where the A_i's have iid entries from Normal(0, 1/p). We do this by solving the
+ * the following semi-definite program
+ *
+ * min ||X||_* subj to dot(A_i, X) = b_i, i=1,...,p
+ *
+ * where ||X||_* denotes the nuclear norm (sum of singular values) of X. The equivalent
+ * SDP is
+ *
+ * min tr(W1) + tr(W2) : [ W1, X ; X', W2 ] is PSD, dot(A_i, X) = b_i, i=1,...,p
+ *
+ * For more details on matrix sensing and nuclear norm minimization, see
+ *
+ * Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear
+ * Norm Minimization.
+ * Benjamin Recht, Maryam Fazel, Pablo Parrilo.
+ * SIAM Review 2010.
+ *
+ */
+BOOST_AUTO_TEST_CASE(GaussianMatrixSensingSDP)
+{
+ arma::mat Xorig, A;
+
+ // read the unknown matrix X and the measurement matrices A_i in
+ data::Load("sensing_X.csv", Xorig, true, false);
+ data::Load("sensing_A.csv", A, true, false);
+
+ const size_t m = Xorig.n_rows;
+ const size_t n = Xorig.n_cols;
+ const size_t p = A.n_rows;
+ assert(A.n_cols == m * m);
+
+ arma::vec b(p);
+ for (size_t i = 0; i < p; ++i)
+ {
+ const auto Ai = arma::reshape(A.row(i), n, m);
+ b(i) = arma::dot(trans(Ai), Xorig);
+ }
+
+ float r = 0.5 + sqrt(0.25 + 2 * p);
+ if (ceil(r) > m + n)
+ r = m + n;
+
+ arma::mat coordinates;
+ coordinates.eye(m + n, ceil(r));
+
+ LRSDP sensing(0, p, coordinates);
+ sensing.SparseC().eye(m + n, m + n);
+ sensing.DenseB() = 2. * b;
+
+ const auto block_rows = arma::span(0, m - 1);
+ const auto block_cols = arma::span(m, m + n - 1);
+
+ for (size_t i = 0; i < p; ++i)
+ {
+ const auto Ai = arma::reshape(A.row(i), n, m);
+ sensing.DenseA()[i].zeros(m + n, m + n);
+ sensing.DenseA()[i](block_rows, block_cols) = trans(Ai);
+ sensing.DenseA()[i](block_cols, block_rows) = Ai;
+ }
+
+ double finalValue = sensing.Optimize(coordinates);
+ BOOST_REQUIRE_CLOSE(finalValue, 44.7550132629, 1e-1);
+
+ const arma::mat rrt = coordinates * trans(coordinates);
+ for (size_t i = 0; i < p; ++i)
+ {
+ const auto Ai = arma::reshape(A.row(i), n, m);
+ const double measurement =
+ arma::dot(trans(Ai), rrt(block_rows, block_cols));
+ BOOST_REQUIRE_CLOSE(measurement, b(i), 1e-3);
+ }
+
+ // check matrix recovery
+ const double err =
+ arma::norm(Xorig - rrt(block_rows, block_cols), "fro") /
+ arma::norm(Xorig, "fro");
+ BOOST_REQUIRE_SMALL(err, 1e-3);
+}
+
+/**
* keller4.co test case for Lovasz-Theta LRSDP.
* This is commented out because it takes a long time to run.
* See Monteiro and Burer 2004.
More information about the mlpack-git
mailing list