Manifold-based Algorithms for the Hadamard Decomposition

arXiv:2605.28980v1 Announce Type: cross Abstract: Given a matrix X, and two ranks r_1 and r_2, the Hadamard decomposition (HD) looks for two low-rank matrices, X_1 of rank r_1 and X_2 of rank r_2, both of the same size as X, such that Xapprox X_1irc X_2, where irc 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 X_1 irc X_2 is generically equal to r_1 r_2. In this paper, we first present some theoretical insights for HD, in particular a useful reformulation Xapprox WH^op where W and H have r_1 r_2 columns and belong to certain manifolds. These allow us to develop three new algorithms for computing HD. The first one uses the representation Xapprox X_1irc X_2 and relies on the Manopt toolbox. The other two rely on the reformulation Xapprox WH^op: 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.

Source: arXiv cs.LG | 2026-05-29