# Compact Lifted Relaxations for Low-Rank Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 5 Mar 2026.

## Builds on (most cited first, 6 of 6)

- [Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach](https://mlsanity.com/paper/2109.12701/) (2021)
- [Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints](https://mlsanity.com/paper/2009.10395/) (2020)
- [Certifiably Optimal Low Rank Factor Analysis](https://mlsanity.com/paper/1604.06837/) (2016)
- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [On the tightness of SDP relaxations of QCQPs](https://mlsanity.com/paper/1911.09195/) (2019)
- [On the Partial Convexification for Low-Rank Spectral Optimization: Rank Bounds and Algorithms](https://mlsanity.com/paper/2305.07638/) (2023)

## Abstract (arXiv)

We develop tractable convex relaxations for rank-constrained quadratic optimization problems over n × m matrices, a setting for which tractable relaxations are typically only available when the objective or constraints admit spectral structure. We derive lifted semidefinite relaxations that do not require such spectral terms. Although a direct lifting introduces a large semidefinite constraint in dimension n2 + nm + 1, we prove that many blocks of the moment matrix are redundant and derive an equivalent compact relaxation that only involves two semidefinite constraints of dimension nm + 1 and n+m, respectively. We also derive a new class of valid inequalities for low-rank problems, which we call projection cuts, that exploit the fact that rank constraints are inherited by linear images of a low-rank matrix, to strengthen our low-rank relaxations substantially. For matrix completion and reduced-rank regression problems, among others, we exploit additional structure to obtain even more compact formulations involving semidefinite matrices of dimension at most the sum of the two dimensions of the low-rank decision matrix (i.e., of size at most n+m). Overall, we obtain scalable semidefinite bounds for a broad class of low-rank quadratic problems.