# A new perspective on low-rank optimization

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 83 references that are in the map.
- First posted on arXiv 12 May 2021.

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

- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization](https://mlsanity.com/paper/2004.06152/) (2020)
- [Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions](https://mlsanity.com/paper/1709.10029/) (2017)
- [Low-Rank Matrix Completion: A Contemporary Survey](https://mlsanity.com/paper/1907.11705/) (2019)
- [Sparse Regression: Scalable algorithms and empirical performance](https://mlsanity.com/paper/1902.06547/) (2019)
- [A unified approach to mixed-integer optimization problems with logical constraints](https://mlsanity.com/paper/1907.02109/) (2019)
- [Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection](https://mlsanity.com/paper/1510.06083/) (2015)
- [Rank-one Convexification for Sparse Regression](https://mlsanity.com/paper/1901.10334/) (2019)
- [Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints](https://mlsanity.com/paper/2009.10395/) (2020)
- [Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality](https://mlsanity.com/paper/2005.05195/) (2020)
- [Certifiably Optimal Low Rank Factor Analysis](https://mlsanity.com/paper/1604.06837/) (2016)
- [A New Convex Relaxation for Tensor Completion](https://mlsanity.com/paper/1307.4653/) (2013)
- [Ideal formulations for constrained convex optimization problems with indicator variables](https://mlsanity.com/paper/2007.00107/) (2020)
- [Semidefinite approximations of the matrix logarithm](https://mlsanity.com/paper/1705.00812/) (2017)
- [Approximation Algorithms for D-optimal Design](https://mlsanity.com/paper/1802.08372/) (2018)
- [On the tightness of SDP relaxations of QCQPs](https://mlsanity.com/paper/1911.09195/) (2019)
- [Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone](https://mlsanity.com/paper/1408.4685/) (2014)
- [Lieb's concavity theorem, matrix geometric means, and semidefinite optimization](https://mlsanity.com/paper/1512.03401/) (2015)
- [Domain-Driven Solver (DDS) Version 2.0: a MATLAB-based Software Package for Convex Optimization Problems in Domain-Driven Form](https://mlsanity.com/paper/1908.03075/) (2019)

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

- [Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach](https://mlsanity.com/paper/2109.12701/) (2021)
- [Probe-Free Low-Rank Activation Intervention](https://mlsanity.com/paper/2502.04043/) (2025)
- [On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained Optimization Problems](https://mlsanity.com/paper/2210.16191/) (2022)
- [On the Partial Convexification for Low-Rank Spectral Optimization: Rank Bounds and Algorithms](https://mlsanity.com/paper/2305.07638/) (2023)
- [Constrained Optimization of Rank-One Functions with Indicator Variables](https://mlsanity.com/paper/2303.18158/) (2023)
- [Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion](https://mlsanity.com/paper/2305.12292/) (2023)
- [FedMPDD: Communication-Efficient Federated Learning with Privacy Preservation Attributes via Projected Directional Derivative](https://mlsanity.com/paper/2512.20814/) (2025)
- [Predictive Low Rank Matrix Learning under Partial Observations: Mixed-Projection ADMM](https://mlsanity.com/paper/2407.13731/) (2024)
- [Variable Selection Methods for Multivariate, Functional, and Complex Biomedical Data in the AI Age](https://mlsanity.com/paper/2501.06868/) (2025)
- [Compact Lifted Relaxations for Low-Rank Optimization](https://mlsanity.com/paper/2603.20228/) (2026)

## Abstract (arXiv)

A key question in many low-rank problems throughout optimization, machine learning, and statistics is to characterize the convex hulls of simple low-rank sets and judiciously apply these convex hulls to obtain strong yet computationally tractable convex relaxations. We invoke the matrix perspective function - the matrix analog of the perspective function - and characterize explicitly the convex hull of epigraphs of simple matrix convex functions under low-rank constraints. Further, we combine the matrix perspective function with orthogonal projection matrices-the matrix analog of binary variables which capture the row-space of a matrix-to develop a matrix perspective reformulation technique that reliably obtains strong relaxations for a variety of low-rank problems, including reduced rank regression, non-negative matrix factorization, and factor analysis. Moreover, we establish that these relaxations can be modeled via semidefinite constraints and thus optimized over tractably. The proposed approach parallels and generalizes the perspective reformulation technique in mixed-integer optimization and leads to new relaxations for a broad class of problems.