  Sparse matrix factorization is the problem of approximating a matrix
$\mathbf{Z}$ by a product of $J$ sparse factors $\mathbf{X}^{(J)}
\mathbf{X}^{(J-1)} \ldots \mathbf{X}^{(1)}$. This paper focuses on
identifiability issues that appear in this problem, in view of better
understanding under which sparsity constraints the problem is well-posed. We
give conditions under which the problem of factorizing a matrix into \emph{two}
sparse factors admits a unique solution, up to unavoidable permutation and
scaling equivalences. Our general framework considers an arbitrary family of
prescribed sparsity patterns, allowing us to capture more structured notions of
sparsity than simply the count of nonzero entries. These conditions are shown
to be related to essential uniqueness of exact matrix decomposition into a sum
of rank-one matrices, with structured sparsity constraints. In particular, in
the case of fixed-support sparse matrix factorization, we give a general
sufficient condition for identifiability based on rank-one matrix
completability, and we derive from it a completion algorithm that can verify if
this sufficient condition is satisfied, and recover the entries in the two
sparse factors if this is the case. A companion paper further exploits these
conditions to derive identifiability properties and theoretically sound
factorization methods for multi-layer sparse matrix factorization with support
constraints associated to some well-known fast transforms such as the Hadamard
or the Discrete Fourier Transforms.
