iiinova — where your digital self keeps evolving

Replies

Ryan Cory-Wright @ryancorywright.bsky.social · 06/01/2025

New paper alert 🚨 optimization-online.org/2025/01/impr... “Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization” (w/ Jean Pauphilet) Inspired by Goemans-Williamson’s success in binary quadratic optimization, we generalize to semi-orthogonal and low-rank matrices.

optimization-online.org

Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization – Optimization Online

172

Ryan Cory-Wright @ryancorywright.bsky.social · 06/01/2025

We also develop new convex relaxations for low-rank problems, via Shor relaxations. Our original relaxations involve matrices of size n^2 x n^2, which is not tractable. However, we show how to make our relaxations block decomposable, and thus tractable, for several applications.

000