Compact Lifted Relaxations for Low-Rank Optimization

• URL: http://arxiv.org/abs/2603.20228v1
• Date: Thu, 05 Mar 2026 17:05:18 GMT
• Title: Compact Lifted Relaxations for Low-Rank Optimization
• Abstract summary: We develop tractable convex relaxations for rank-constrained quadratic optimization problems over $n times m$ matrices.<n>We derive lifted semidefinite relaxations that do not require such spectral terms.<n>Overall, we obtain scalable semidefinite bounds for a broad class of low-rank quadratic problems.
• Score: 2.0052993723676895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop tractable convex relaxations for rank-constrained quadratic optimization problems over $n \times m$ matrices, a setting for which tractable relaxations are typically only available when the objective or constraints admit spectral (permutation-invariant) structure. We derive lifted semidefinite relaxations that do not require such spectral terms. Although a direct lifting introduces a large semidefinite constraint in dimension $n^2 + nm + 1$, we prove that many blocks of moment matrix are redundant and derive an equivalent compact relaxation that only involves two semidefinite constraints of dimension $nm + 1$ and $n+m$ respectively. For matrix completion, basis pursuit, and reduced-rank regression problems, we exploit additional structure to obtain even more compact formulations involving semidefinite matrices of dimension at most $2\max(n,m)$. Overall, we obtain scalable semidefinite bounds for a broad class of low-rank quadratic problems.

Related papers

• Semidefinite Relaxations for Collision-Free Motion Planning [53.160637667144876]
  We focus on a point robot moving from start to goal through inmathbbRn constraints in terms of $C4 trajectories.<n>We demonstrate its effectiveness as a planner for minimum-snap continuous planning with $C4 trajectories.
  arXiv  Detail & Related papers  (2026-06-12T03:18:03Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• A Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedron [18.035791732015802]
  We consider the problem of minimizing a smooth and convex function over the $n$-dimensional spectrahedron.<n>Standard first-order methods often require high-rank matrix computations which are prohibitive when the dimension $n$ is large.<n>We present the first Frank-Wolfe-based algorithm that only applies efficient rank-one matrix computations.
  arXiv  Detail & Related papers  (2025-03-03T11:46:46Z)
• Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization [2.0052993723676895]
  We construct an analogous relax-then-round strategy for low-rank optimization problems.<n>For a given $n times m$ semi-orthogonal matrix, we derive a purely multiplicative approximation ratio for our algorithm.<n>We extend our approach to generic low-rank optimization problems by developing new semidefinite relaxations.
  arXiv  Detail & Related papers  (2025-01-06T11:31:41Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  We propose a natural algorithm that involves imputing the missing values of the matrix $XTX$. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing.
  arXiv  Detail & Related papers  (2023-06-06T22:35:16Z)
• Disjunctive Branch-And-Bound for Certifiably Optimal Low-Rank Matrix Completion [6.537257913467247]
  We present a novel and often near-exact class of convex relaxations by decomposing a low-rank matrix as a sum of two minors.<n>In numerical experiments, our new convex relaxations decrease the optimality or near optimality in for $max m, n q$ and $r leq$.
  arXiv  Detail & Related papers  (2023-05-20T22:04:34Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
  We investigate the problem of recovering a partially observed high-rank clustering matrix whose columns obey a nonlinear structure such as a union of subspaces. We show that the alternating limit converges to a unique point using the Kurdyka-Lojasi property.
  arXiv  Detail & Related papers  (2021-09-13T16:13:13Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Compressed sensing of low-rank plus sparse matrices [3.8073142980733]
  This manuscript develops similar guarantees showing that $mtimes n$ that can be expressed as the sum of a rank-rparse matrix and a $s-sparse matrix can be recovered by computationally tractable methods. Results are shown for synthetic problems, dynamic-foreground/static separation, multispectral imaging, and Robust PCA.
  arXiv  Detail & Related papers  (2020-07-18T15:36:11Z)
• Competitive Mirror Descent [67.31015611281225]
  Constrained competitive optimization involves multiple agents trying to minimize conflicting objectives, subject to constraints. We propose competitive mirror descent (CMD): a general method for solving such problems based on first order information. As a special case we obtain a novel competitive multiplicative weights algorithm for problems on the positive cone.
  arXiv  Detail & Related papers  (2020-06-17T22:11:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.