PaperlayerView exact revision on arXiv

Source-linked AI summary

A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints

Nicolas Boumal

arXiv:1506.00575v2math.OCcs.CVstat.CO

TL;DR

Rank-constrained semidefinite problems arise in estimation and combinatorial optimization, but solving their rank-restricted forms directly is difficult. The paper develops a Riemannian staircase that uses second-order critical points to find KKT points of the semidefinite problem. Its theory gives conditions for this link, and numerical experiments confirm the method's usefulness.

  • Problem

    Rank-constrained semidefinite formulations arise in estimation and combinatorial optimization, while interior-point methods for the relaxed SDP do not scale well.

    Source: §1 · pp. 2–3

  • Method

    The Riemannian staircase solves rank-restricted problems on a smooth manifold and increases the rank parameter until second-order critical points yield KKT points.

    Source: §1.1 · p. 4

  • Results

    Rank-deficient second-order critical points reveal KKT points, and numerical experiments confirm the usefulness of the resulting approach.

    Source: §7 · p. 28

  • Takeaways & Limitations

    Under stated conditions, second-order critical points on a low-dimensional portion of the spectrahedron's boundary can suffice to obtain KKT points.

    Source: §7 · p. 28

    The complexity of computing sufficiently accurate second-order critical points remains an open question; approximate critical points are shown to yield approximate KKT points only for linear f.

    Source: §7 · p. 28

Abstract

from arXiv · show

We propose a new algorithm to solve optimization problems of the form $\min f(X)$ for a smooth function $f$ under the constraints that $X$ is positive semidefinite and the diagonal blocks of $X$ are small identity matrices. Such problems often arise as the result of relaxing a rank constraint (lifting). In particular, many estimation tasks involving phases, rotations, orthonormal bases or permutations fit in this framework, and so do certain relaxations of combinatorial problems such as Max-Cut. The proposed algorithm exploits the facts that (1) such formulations admit low-rank solutions, and (2) their rank-restricted versions are smooth optimization problems on a Riemannian manifold. Combining insights from both the Riemannian and the convex geometries of the problem, we characterize when second-order critical points of the smooth problem reveal KKT points of the semidefinite problem. We compare against state of the art, mature software and find that, on certain interesting problem instances, what we call the staircase method is orders of magnitude faster, is more accurate and scales better. Code is available.

1 Introduction

The paper studies block-identity semidefinite relaxations of rank-constrained problems and develops a Riemannian staircase method that links low-rank second-order critical points to KKT points. Its applications include synchronization and combinatorial optimization, while its contribution builds on but addresses limitations of earlier low-rank SDP methods.

1 Introduction

  • The rank-constrained formulation is equivalent to optimizing over positive semidefinite matrices with identity diagonal blocks and a rank bound; dropping that bound yields an SDP relaxation.The relaxation provides a lower bound, and a solution of rank at most p also solves the rank-constrained problem.Source: §1 · pp. 2–3

1.1 Contribution

  • The Riemannian Staircase increases the rank parameter step by step, using second-order critical points to identify KKT points or warm-start a higher-rank problem.Rank-deficient second-order critical points yield KKT points; allowing p to grow to n guarantees termination.Source: §1.1 · pp. 4–5

1.3 Related work

  • The method extends prior Riemannian and low-rank SDP approaches by handling nonlinear costs without requiring local optimizers of the rank-restricted problems.It also avoids the quotient approach's geometry breakdown at rank-deficient points; the paper notes that MaxBet and MaxDiff fall outside its scope.Source: §1 · p. 4, §1.1 · p. 5, §1.3 · p. 7

1.2 Applications

  • The framework covers synchronization tasks, including rotation estimation, as well as Max-Cut and other problems modeled through pairwise relations.Rotation synchronization appears in applications such as structure from motion, pose-graph estimation, and SLAM.Source: §1.2 · pp. 5–6

1.4 Notation

  • The notation treats matrices as block matrices with d × d blocks and uses block indices for their row and column positions.For Z ∈ R^(n×p), Z_i denotes its ith d × p slice.Source: §1.4 · pp. 7–8

2 Geometry

The rank-restricted search space has smooth Riemannian geometry, while the full feasible set is compact and convex. Their complementary structures connect low-rank solutions to properties of the semidefinite problem.

2.1 Smooth geometry of the rank-restricted search space

  • St(d, p)m is a smooth Riemannian search space; its tangent directions support optimization, and retractions return iterates to the manifold.The set is connected when p > d; the described slice-wise SVD retraction costs O(np^2) flops.Source: §2 · p. 8, §2.1 · pp. 8, 10
  • The rank-restricted factorization represents bounded-rank matrices in C by Y Y^T, with redundancy allowing a smooth parameterization even where the bounded-rank set is nonsmooth.In Figure 1, the rank-2 boundary is smooth except at rank-1 points, while the factorization uses a redundant product-of-circles parameterization.Source: Figure 1 · p. 9

2.2 Convex geometry of the full search space

  • The feasible set C consists of positive semidefinite matrices with identity diagonal blocks, and each off-diagonal block lies in the convex hull of O(d).All off-diagonal blocks are orthogonal exactly when rank(X) = d.Source: §2.2 · pp. 10–11
  • For d = 1, not every feasible matrix meeting the rank bound is extreme; rank-2 matrices can lie between distinct rank-1 feasible matrices.The text states that almost all feasible rank-p matrices have face dimension Δ, not that all such matrices are extreme.Source: §2.2 · p. 12
  • Every rank-d feasible matrix is an exposed extreme point, while feasible matrices within the rank bound need not be extreme.For linear costs, an extreme-point optimizer means the rank-restricted and full problems have the same optimal value once p ≥ p*.Source: §2.2 · p. 12

3 From second-order critical points Y to KKT points X

This section gives conditions under which second-order critical points of the rank-restricted problem yield KKT points of the semidefinite problem. It also examines exceptional non-KKT or nonoptimal critical points and mechanisms involving rank changes.

3 From second-order critical points Y to KKT points X

  • The explicit certificate S is positive semidefinite if and only if X is KKT, and it is the unique dual certificate for X.Its formula follows from the first-order optimality conditions of the smooth rank-restricted problem.Source: §3 · pp. 13–14
  • For convex f, S ⪰ 0 characterizes global optimality; if X is extreme and strict complementarity holds, X is the unique global optimizer.The rank condition rank(X) = d is sufficient for extremeness.Source: §3 · pp. 14–15
  • Rank-deficient second-order critical points yield KKT points, and square second-order critical points do too; for square full-rank points, first-order criticality suffices.Thus, when p = n, every second-order critical point reveals a KKT point.Source: §3 · p. 16
  • At a rank-deficient non-KKT critical point, a null-space tangent direction is descending; at a full-rank non-KKT point, increasing p creates such a direction.The rank-increased point preserves the objective and criticality before the descent step.Source: §3 · p. 17
  • Second-order criticality transfers to optimization on X's face; for linear costs and p > ⌊p*⌋, the face is either globally optimal or full-rank and suboptimal.For strongly concave costs, second-order critical points are extreme and have rank at most ⌊p*⌋, so p > ⌊p*⌋ implies KKT; for convex costs, face-critical points are optimal on the face.Source: §3 · pp. 17–18
  • For concave f, a non-KKT second-order critical point must be full-rank, with dim FX ≥ Δ + p.If Y is rank-deficient, then S is positive semidefinite.Source: §3 · p. 18
  • For linear f and p > p*, any nonoptimal second-order critical point has rank(X) = p, dim F_X ≥ Δ + p, and f is constant over F_X.The paper leaves open the probability that a randomly sampled linear objective is constant on such a face, while noting there are few such faces.Source: §3 · p. 19
  • For rank-p X, dim F_X is at most p(p + 1)/2 − p(d + 1)/2; this bound is attained for some X when p is a multiple of d.Source: §3 · pp. 19–20
  • The combined results give a sufficient rank condition for every second-order critical point to map to a KKT point; for linear f, such points are global optimizers.The threshold is stated as d+3n in the supplied excerpt.Source: §3 · p. 21
  • For concave f, p > (d+1)/2 ensures the condition (n − p)(d + 1) < 2p, under which the results imply S ⪰ 0 and hence the KKT conclusion.Source: §3 · p. 21
  • For Max-Cut, where d = 1 and f is linear, p = ⌊n/2⌋ + 1 certainly makes every second-order critical point solve the SDP; empirically, smaller p = ⌊p*⌋ + 1 is sufficient.For a bad critical point at the smaller rank, the paper gives an escape route for concave f that does not increase rank.Source: §3 · p. 21
  • A nonzero vector in ker H yields a boundary point X′ in F_X with rank(X′) ≤ p − 1, providing an in-face rank-reduction step.Computing the needed vector via a minimal eigenvector of H costs O(d^2 n^3) flops under the stated assumptions.Source: §3 · p. 21

4 The Riemannian staircase algorithm

The Riemannian Staircase searches increasingly larger Stiefel-product manifolds for second-order critical points, using rank deficiency to identify KKT points of the semidefinite problem. Under stated conditions it certifies termination by rank n, while practical behavior and function-specific bounds can keep the search rank lower.

4 The Riemannian staircase algorithm

  • The staircase optimizes at rank p, returns when the second-order critical point is rank deficient, and otherwise increases p using an escape direction and line search.The worst case reaches p=n, where any second-order critical point yields a KKT point.Source: §4 · pp. 21–22
  • For strongly concave f, rank ⌊p*⌋+1 suffices; for sufficiently smooth f, taking pk=n guarantees Algorithm 1 returns Y such that YY⊤ is a KKT point.For concave f, rank ⌊p*⌋+1 is expected to suffice, but is not established as a guarantee.Source: §4 · p. 22
  • For concave f, a full-rank non-KKT endpoint can be moved to the boundary of its feasible face without increasing rank, with strict cost decreases, but termination is unproved.The authors expect termination because the problem admits KKT points of rank at most ⌊p*⌋.Source: §4 · p. 22
  • The implementation uses Riemannian trust-region descent, which converges toward critical points; stable fixed points are local optimizers, though non-second-order-critical convergence remains possible.If a returned point is not second-order critical, the method can escape it, but the worst-case number of repetitions is unclear.Source: §4 · p. 22
  • Because the gradient stopping rule returns only an approximate critical point, numerical rank deficiency is assessed by a condition-number threshold.The example threshold is 10^10; a higher-rank solution can also be projected to rank q and reoptimized, which may avoid poor local traps.Source: §4 · p. 23

5 Special case: linear cost function

For linear costs, the paper develops an SDP value bound and evaluates the staircase on noisy orthogonal synchronization instances. It reports that the method alone satisfies constraints to machine precision and returns a solution numerically closest to rank d, with cost scaling like computing d dominant eigenvectors.

5 Special case: linear cost function

  • For linear f, f(X) + n · λmin(S(X)) ≤ f* ≤ f(X) for every X in C, giving lower and upper bounds on the SDP optimum.The proof uses an admissible dual matrix and strong duality under Slater’s condition.Source: §5 · p. 23
  • The staircase alone satisfies constraints to machine precision and returns the solution numerically closest to rank d, with computational cost growing like EIG and outperforming interior-point methods and SDPLR.Figure 2 compares methods solving (P) on Section 5 problems; the staircase runs RTR once at p=d+1 for the rank-d solution.Source: Figure 2 · p. 24, §5 · p. 24
  • Every generated orthogonal-synchronization instance admits a rank-d solution, revealing the true maximum-likelihood estimator.The experiment estimates orthogonal matrices from noisy relative-transformation measurements.Source: §5 · pp. 23–24

6 Special case: Pseudo-Huber loss cost function

The section studies smoothed robust costs for orthogonal and permutation synchronization, where smoothing makes the objective amenable to the proposed method but can affect solution rank. In the permutation experiment, staircase empirically recovers the true permutations with up to 80% outliers, although global optimality is not established.

6 Special case: Pseudo-Huber loss cost function

  • The proposed tools do not directly apply to nonsmooth LUD, motivating the use of a smoothed related cost that is strongly concave in X.The pseudo-Huber loss approaches absolute error as ε tends to zero.Source: §6 · pp. 25–26
  • Smoothing the LUD cost typically yields higher-rank solutions at significant computational premium, and under slight measurement inconsistency all KKT points have rank greater than d.The theorem assumes a twice continuously differentiable increasing loss and measurements that are not a rank-d matrix in C.Source: §6 · p. 25
  • The quadratic synchronization cost differs from its linear counterpart only by a constant on rank-d feasible matrices, yet even the smallest noise is not expected to preserve rank-d solutions for the convex quadratic cost.The text points to concavity and nonsmoothness as properties that promote rank-d solutions.Source: §6 · p. 25
  • As ε decreases with warm-starting, the quality of the found rank-d KKT point increases; empirically, the method typically reaches such a point even for ε>0.For strong concavity, second-order critical points at p>p* reveal KKT points.Source: §6 · p. 26
  • The permutation setting models relative permutation measurements, with a uniformly random subset replaced by random permutations; exact recovery means recovering the true permutations.The example applies the robust orthogonal-synchronization formulation without changing the algorithms.Source: §6 · p. 26
  • With m=100 permutations of size d=6, pseudo-Huber staircase empirically achieves perfect recovery with up to 80% outliers, but the concave objective prevents claiming a global optimum.The figure compares mean squared error against the outlier fraction; ADM solves a convex problem and comes with guarantees.Source: §6 · p. 26, Figure 3 · p. 27

7 Conclusions and perspectives

The paper presents a Riemannian method for KKT-point computation on spectrahedra arising in orthonormal-matrix relaxations, connecting bounded-rank geometry with second-order criticality. It closes with open questions about manifold complexity, nonconvex KKT points, and the rank needed for global optimization.

7 Conclusions and perspectives

  • The method exploits smooth geometry of bounded-rank spectrahedra to reduce optimization to Riemannian problems, and experiments confirm the usefulness of the resulting low-dimensional search.Under certain conditions, only second-order critical points on a low-dimensional portion of the spectrahedron boundary need to be computed.Source: §7 · p. 28
  • Whether second-order critical points on a Riemannian manifold can be computed efficiently to a given accuracy remains an open complexity question.The paper also asks whether approximately second-order-critical, rank-deficient iterates yield approximately KKT points; for linear f it cites a positive answer.Source: §7 · p. 28
  • For nonconvex f, KKT points include local optimizers but also uninteresting points, leaving open whether second-order KKT conditions can exclude more spurious points.The paper identifies this as a possible route to improved guarantees.Source: §7 · p. 28
  • For a unique rank-r solution under linear f, whether searching at p=r+1 suffices remains open, though the paper reports this empirically under its Section 5 noise model.The authors suggest investigating the expected attraction-basin size of global optimizers.Source: §7 · p. 28
  • For random linear costs and p>p*, the probability that second-order critical points are not global optimizers remains an open question.Source: §7 · p. 28

A Tightness for synchronization on a cycle

For synchronization on a cycle, the SDP relaxation has a unique rank-d solution when the product of orthogonal measurements has no eigenvalue −1. The proof constructs that solution explicitly and certifies its optimality with a dual certificate.

A Tightness for synchronization on a cycle

  • The proof's explicit primal and dual formulas may extend to connected graphs whose cycles have disjoint edges; Zhang and Singer [83] cover only 3-cycles but allow non-orthogonal data blocks.Sharp et al. and Peters et al. give an explicit solution formula under the same condition, restricting attention to rotations.Source: A Tightness for synchronization on a… · p. 34
  • When −1 is not an eigenvalue of the measurement product P, the cycle SDP has a unique rank-d solution that reveals the global optimum.The theorem applies to orthogonal measurements on a cycle of length m ≥ 3.Source: A Tightness for synchronization on a… · p. 34
  • The candidate solution incorporates an equal share of cycle inconsistency at each step using the principal matrix root P^(1/m).The construction defines a recurrence for the aligned measurements and is admissible with rank d.Source: A Tightness for synchronization on a… · p. 34
  • The certificate is verified by showing S(X) is positive semidefinite with rank (m − 1)d, using a spectral decomposition and eigenvalue interlacing.After block permutation, the proof uses positive eigenvalues of a tridiagonal Toeplitz matrix and identifies a kernel vector.Source: A Tightness for synchronization on a… · p. 35
  • The condition on P is necessary in general: for d = 1 and m = 3 with P = −1, none of the four admissible rank-1 matrices is optimal.For rotation measurements, the condition holds almost surely under a uniform random distribution.Source: A Tightness for synchronization on a… · pp. 34–35

B Generic face dimension

For d = 1, a uniformly random point has a face whose dimension is almost surely minimal, as specified by the theorem's bound. The proof reduces this dimension to the span of independent random constraint matrices; extending the result to d ≥ 1 remains unproved.

B Generic face dimension

  • For d = 1, a uniformly random Y yields dim F_(YY⊤) = max(0, Δ) almost surely, the minimal dimension given by the stated bound.The proof studies the span of the constraint matrices y_i y_i⊤; for Gaussian samples, nontrivial linear combinations have no point mass at zero.Source: B Generic face dimension · p. 36
  • Independent random vectors that almost surely avoid every proper subspace span a space of dimension min(n, k) almost surely.The proof applies this lemma to the constraint matrices in the symmetric-matrix space.Source: B Generic face dimension · p. 36
  • The authors expect the minimal-face-dimension result to hold for d ≥ 1, but state that they lack a proof.The theorem itself is stated for d = 1.Source: B Generic face dimension · p. 36

Related papers

Loading 1506.00575v2…