Convex relaxations of structured matrix factorizations

Abstract

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.

References in corpus (4)

• Generalized power method for sparse principal component analysis
• Approximation and learning by greedy algorithms
• Factoring nonnegative matrices with linear programs
• Convex Sparse Matrix Factorizations

Cited by in corpus (9)

• Breaking the Curse of Dimensionality with Convex Neural Networks
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Forward - Backward Greedy Algorithms for Atomic Norm Regularization
• Tight convex relaxations for sparse matrix factorization
• Faster Rates for Convex-Concave Games
• Binary component decomposition Part II: The asymmetric case
• Model Function Based Conditional Gradient Method with Armijo-like Line Search
• An Analysis of Dropout for Matrix Factorization
• Pursuits in Structured Non-Convex Matrix Factorizations