Manifold-based Algorithms for the Hadamard Decomposition

Given a matrix X, and two ranks r1 and r2, the Hadamard decomposition (HD) looks for two low-rank matrices, X1 of rank r1 and X2 of rank r2, both of the same size as X, such that X≈ X1circ X2, where circ is the Hadamard (element-wise) product. In most cases, HD is more expressive than standard low-rank approximations such as the truncated singular value decomposition (TSVD), as it can represent higher-rank matrices with the same number of parameters; this is because the rank of X1 circ X2 is generically equal to r1 r2. In this paper, we first present some theoretical insights for HD, in particular a useful reformulation X≈ WH^top where W and H have r1 r2 columns and belong to certain manifolds. These allow us to develop three new algorithms for computing HD. The first one uses the representation X≈ X1circ X2 and relies on the Manopt toolbox. The other two rely on the reformulation X≈ WH^top: one is a block projected gradient method, and the other is a manifold-based gradient descent algorithm that does not require projection onto the feasible set. The last two algorithms are particularly effective for handling large sparse data. We also propose new initializations that allow us to improve the accuracy of the HD. We compare our algorithms and initialization strategies with the TSVD and with the state of the art. Numerical results show that the new methods are efficient and competitive on both synthetic and real data.