Seminar Aric: Sparse Matrix Factorization with Fixed Support
Date:
Abstract: The problem of approximating a dense matrix by a product of sparse factors is a fundamental problem of many computer science tasks. It can be decomposed into two subproblems: finding the position of the nonzero coefficients in the sparse factors (or equivalently finding the support of the factors) and determining their values. While the first problem is usually seen as more challenging due to its combinatorial nature, this talk will focus on the second, referred to as Fixed Support sparse Matrix Factorization (FSMF). We present several interesting properties of (FSMF), notably from two points of view: 1) In terms of complexity: (FSMF) is NP-hard which shows that even if one knows the support factor, sparse matrix factorization remains challenging; 2) In terms of optimization: Despite the NP-hardness, there exists a family of instances of (FSMF) can be polynomially tractable and their underline geometry allows optimization techniques to converge to the optimal solutions. This is joint work with Elisa Riccietti and Rémi Gribonval.