  The problem of approximating a dense matrix by a product of sparse factors is
a fundamental problem for many signal processing and machine learning tasks. It
can be decomposed into two subproblems: finding the position of the non-zero
coefficients in the sparse factors, and determining their values. While the
first step is usually seen as the most challenging one due to its combinatorial
nature, this paper focuses on the second step, referred to as sparse matrix
approximation with fixed support. First, we show its NP-hardness, while also
presenting a nontrivial family of supports making the problem practically
tractable with a dedicated algorithm. Then, we investigate the landscape of its
natural optimization formulation, proving the absence of spurious local valleys
and spurious local minima, whose presence could prevent local optimization
methods to achieve global optimality. The advantages of the proposed algorithm
over state-of-the-art first-order optimization methods are discussed.
