A new perspective on low-rank optimization

Bertsimas, D, Cory-Wright, R and Pauphilet, J (2023) A new perspective on low-rank optimization. Mathematical Programming, 202. pp. 47-92. ISSN 0025-5610 OPEN ACCESS


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 relaxations. We invoke the matrix perspective function the matrix analog of the perspective function to 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 semidenite 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.

More Details

Item Type: Article
Subject Areas: Management Science and Operations
Date Deposited: 17 Apr 2023 13:09
Date of first compliant deposit: 12 Apr 2023
Subjects: Matrix analysis
Last Modified: 17 Oct 2023 14:50
URI: https://lbsresearch.london.edu/id/eprint/2744

Export and Share


Published Version - Text
  • Available under License


View details on Dimensions' website

Downloads from LBS Research Online

View details

Actions (login required)

Edit Item Edit Item