Convex relaxations of structured matrix factorizations
This work addresses matrix factorization with structural constraints, which is important for applications in data analysis and machine learning, but it appears incremental as it builds on existing gauge function and relaxation methods.
The paper tackles the problem of factorizing a rectangular matrix into structured rank-one factors with constraints like positivity or sparsity, showing that optimal decomposition relates to gauge functions and providing semi-definite relaxations and algorithms with approximation guarantees. It includes simulations on binary decompositions and contributions like variational quadratic norm representations and a new iterative basis pursuit algorithm.
We consider the factorization of a rectangular matrix $X $ into a positive linear combination of rank-one factors of the form $u v^\top$, where $u$ and $v$ belongs to certain sets $\mathcal{U}$ and $\mathcal{V}$, that may encode specific structures regarding the factors, such as positivity or sparsity. In this paper, we show that computing the optimal decomposition is equivalent to computing a certain gauge function of $X$ and we provide a detailed analysis of these gauge functions and their polars. Since these gauge functions are typically hard to compute, we present semi-definite relaxations and several algorithms that may recover approximate decompositions with approximation guarantees. We illustrate our results with simulations on finding decompositions with elements in $\{0,1\}$. As side contributions, we present a detailed analysis of variational quadratic representations of norms as well as a new iterative basis pursuit algorithm that can deal with inexact first-order oracles.