Convex relaxations of structured matrix factorizations
  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.
