Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programming

Valentine Olanubi, Phineas Agar, Brendan Ames

We consider the densest submatrix problem, which seeks the submatrix of fixed size of a given binary matrix that contains the most nonzero entries. This problem is a natural genera…