# On the Partial Convexification for Low-Rank Spectral Optimization: Rank Bounds and Algorithms

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 38 references that are in the map.
- First posted on arXiv 12 May 2023.

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

- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [Color image recovery using low-rank quaternion matrix completion algorithm](https://mlsanity.com/paper/1909.06567/) (2019)
- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [Exact and Approximation Algorithms for Sparse PCA](https://mlsanity.com/paper/2008.12438/) (2020)
- [Exact Semidefinite Formulations for a Class of (Random and Non-Random) Nonconvex Quadratic Programs](https://mlsanity.com/paper/1802.02688/) (2018)
- [Beyond Symmetry: Best Submatrix Selection for the Sparse Truncated SVD](https://mlsanity.com/paper/2105.03179/) (2021)
- [Variational analysis of spectral functions simplified](https://mlsanity.com/paper/1506.05170/) (2015)
- [On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained Optimization Problems](https://mlsanity.com/paper/2210.16191/) (2022)
- [Optimized Transmission for Parameter Estimation in Wireless Sensor Networks](https://mlsanity.com/paper/1908.00600/) (2019)
- [Approximation Bounds for Sparse Programs](https://mlsanity.com/paper/2102.06742/) (2021)
- [Exactness in SDP relaxations of QCQPs: Theory and applications](https://mlsanity.com/paper/2107.06885/) (2021)
- [Strengthened SDP Relaxation for an Extended Trust Region Subproblem with an Application to Optimal Power Flow](https://mlsanity.com/paper/2009.12704/) (2020)

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

- [Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances](https://mlsanity.com/paper/2405.15441/) (2024)
- [Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion](https://mlsanity.com/paper/2305.12292/) (2023)
- [Compact Lifted Relaxations for Low-Rank Optimization](https://mlsanity.com/paper/2603.20228/) (2026)

## Abstract (arXiv)

A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective subject to multiple two-sided linear matrix inequalities intersected with a low-rank and spectral constrained domain set. Although solving LSOP is, in general, NP-hard, its partial convexification (i.e., replacing the domain set by its convex hull) termed "LSOP-R," is often tractable and yields a high-quality solution. This motivates us to study the strength of LSOP-R. Specifically, we derive rank bounds for any extreme point of the feasible set of LSOP-R and prove their tightness for the domain sets with different matrix spaces. The proposed rank bounds recover two well-known results in the literature from a fresh angle and also allow us to derive sufficient conditions under which the relaxation LSOP-R is equivalent to the original LSOP. To effectively solve LSOP-R, we develop a column generation algorithm with a vector-based convex pricing oracle, coupled with a rank-reduction algorithm, which ensures the output solution satisfies the theoretical rank bound. Finally, we numerically verify the strength of the LSOP-R and the efficacy of the proposed algorithms.