# Convex relaxations of structured matrix factorizations

arXiv: https://arxiv.org/abs/1309.3117 · HTML: https://mlsanity.com/paper/1309.3117/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2013.

## Built on by (most cited first, 3 of 3)

- [Nonconvex Linear System Identification with Minimal State Representation](https://mlsanity.com/paper/2504.18791/) (2025)
- [Wave-Informed Matrix Factorization with Global Optimality Guarantees](https://mlsanity.com/paper/2107.09144/) (2021)
- [Wave Physics-informed Matrix Factorizations](https://mlsanity.com/paper/2312.13584/) (2023)

## Abstract (arXiv)

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 U and 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.