Many hard geometry and graph problems become easy if you lift them into a bigger space. You replace a vector $x$ with the matrix $xx^T$, drop the requirement that this matrix have rank one, and solve the resulting convex problem, a semidefinite relaxation. Practitioners rarely solve that convex problem directly. They write the matrix as $YY^T$ with a thin factor $Y$, the Burer–Monteiro factorization, and run a local optimizer on $Y$. This is fast, but the problem is non-convex again, and The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound builds Max-Cut instances whose factorized landscape has strict, isolated spurious minima up to rank $n/2$. At those minima the gradient is zero and the curvature is positive, so small random kicks do not help.
This note proposes to change the landscape rather than the optimizer, using a trick from physics. A pendulum whose pivot is shaken fast enough can balance upside down (Kapitza's pendulum). The fast oscillation adds an effective potential: a time-averaged energy that is high wherever the shaking force is strong. Nonlinear wave physics uses the same idea. Dynamical stabilization of solitons in cubic-quintic nonlinear Schrödinger model rapidly oscillates a nonlinearity coefficient and obtains an effective term proportional to the modulation variance, which stops a pulse from collapsing. We apply this to the factor $Y$. If the cost matrix is oscillated rapidly in a chosen pattern, the averaged dynamics follow a modified objective whose extra term can be computed in closed form. The research question is whether that pattern can be chosen, from the problem's own optimality certificate, so that the extra term lifts spurious minima while leaving the global solution in place.
Core Claim
Consider damped second-order (heavy-ball) dynamics on the factorization manifold. Here $F$ is the factorized objective, $\gamma$ a damping constant, and $G$ a "shaking" function oscillated with amplitude $A$ and frequency $\omega$:
$$\ddot Y + \gamma \dot Y = -\operatorname{grad} F(Y) + A\cos(\omega t)\,\operatorname{grad} G(Y).$$
Here "grad" is the gradient projected onto the constraint manifold. For Max-Cut, that manifold requires each row of $Y$ to have unit norm. To leading order in $1/\omega$, classical Kapitza averaging says the slow motion descends
$$F_{\mathrm{eff}}(Y) = F(Y) + \frac{A^2}{4\omega^2}\,\big\|\operatorname{grad} G(Y)\big\|^2 .$$
Second-order dynamics are not optional. For first-order gradient flow shaken along a single vector field, the averaged drift cancels exactly, so heavy-ball dynamics are the natural carrier. They also match the accelerated ODEs studied in Direct Runge-Kutta Discretization Achieves Acceleration.
A short calculation gives the first prediction, and it is a cautionary one. Take $G(Y)=\operatorname{Tr}(WYY^T)$ with $W$ a random symmetric matrix whose off-diagonal entries are independent with variance $\sigma^2$. On the unit-row manifold the expected extra term is
$$\mathbb{E}\,\|\operatorname{grad} G\|^2 \approx 4\sigma^2\big(n^2 - \|YY^T\|_F^2\big).$$
This is smallest when $YY^T$ has rank one. Naive isotropic shaking therefore pushes the factor toward aligned, low-rank configurations. Those are the kind of degenerate axial configurations the counterexamples exploit. The same effect might be useful at the very end of a run, as a rounding step.
The proposal's real claim is that the shaking pattern must be steered. Each candidate solution comes with a dual certificate: a matrix built from the cost and the current constraint multipliers. It is positive semidefinite exactly when the solution is globally optimal, which is the tool Rotation Averaging and Strong Duality uses to certify rotation averaging. At a spurious minimum this certificate has negative eigenvectors. We will shake along matrices built from those eigenvectors, and from their images under the problem's symmetries. The aim is a penalty term that is large at the trap and vanishes at any certified solution, so the global optimum is never disturbed. The concrete outcome is a fixed-rank solver that escapes spurious Burer–Monteiro minima without increasing the rank. It comes with an analytic account of which shaking patterns help and which ones make things worse.
Relation to Prior Work
Two lines of work motivate the gap. The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound shows that the traps are real and robust to local perturbation, and it supplies our adversarial test instances. It offers no escape mechanism. Rotation Averaging and Strong Duality and Hybrid Rotation Averaging: A Fast and Robust Rotation Averaging Approach show that first-order coordinate methods on low-rank relaxations are the practical workhorse. Their own reported failure modes involve initialization, outliers and a heuristic global-to-local handoff, and this is where trap-escape matters. We keep their problem formulations and certificates and change only the dynamics.
The method comes from physics and numerics. The soliton-stabilization paper supplies the averaging idea and the "effect proportional to variance" scaling. We move it from a one-dimensional wave equation to a constrained matrix manifold, and we choose the modulation from an optimality certificate rather than fixing it in advance. High-Order and Energy-Stable Implicit-Explicit Relaxation Runge-Kutta Schemes for Gradient Flows shows how to integrate non-convex energy flows while keeping a discrete energy monotone. We borrow its relaxation step so the integrator does not inject artificial energy over many fast cycles.
The RK paper also constrains the design. It reports that Euler discretization of accelerated dynamics oscillates and diverges, while multi-stage methods track the continuous path. It also requires smooth objectives, which our polynomial Burer–Monteiro objectives satisfy. This leads to a specific prediction. The averaged correction is of size $A^2/\omega^2$. A first-order integrator's error on the fast term should exceed that correction at practical step sizes, so only higher-order integration should realize the effective landscape.
Landscape-smoothing methods are the main conceptual competitors. A Theoretical Analysis of Optimization by Gaussian Continuation blurs the objective by a heat equation and notes that its guarantees break when paths of minima bifurcate. Consensus-based swarms (Consensus-Based Optimization Methods Converge Globally, Fast and Robust Consensus-Based Optimization via Optimal Feedback Control) escape traps with particle ensembles, but they have been shown only on low-dimensional vector spaces and simple manifolds. Our modification is deterministic, targeted, and uses a single trajectory. It adds a term only where the certificate says something is wrong.
Research Program
The first stage is analytic. We will derive the averaged extra term on the unit-row manifold for Max-Cut and on products of rotation groups for rotation averaging. This includes the projection terms and the correction from finite damping, and it gives the isotropic-shaking result above in full. We will then characterize the steered term at the axial spurious minima constructed in the Burer–Monteiro failure paper. The target is the smallest amplitude-to-frequency ratio $A/\omega$ at which the trap's positive curvature is cancelled. A second target is a proof that the term vanishes at every factor whose certificate is positive semidefinite, which follows if the shaking directions lie in the certificate's negative eigenspace.
The second stage is algorithmic. The shaking directions are refreshed whenever the certificate check fails, using a few Lanczos iterations for the lowest eigenvectors. Two realizations are built on top of this. One adds the extra term explicitly as a penalty and descends it with Riemannian heavy-ball steps. The other integrates the oscillating dynamics with fourth-order Runge–Kutta, augmented with the energy-relaxation step from the IMEX RRK paper. Treating these as two equal candidates is deliberate. If the explicit penalty works as well, the contribution is a certificate-steered regularizer derived from averaging theory, and that is an acceptable outcome.
The third stage is empirical and is described below.
Baselines
The naive reference point is plain Burer–Monteiro at fixed rank. It uses Riemannian heavy-ball descent from a random start, stopping when the gradient is small, and success is judged by the certificate.
The strongest practical competitor on real data is the block coordinate descent solver of Rotation Averaging and Strong Duality, which reports completing the Buddha dataset (322 cameras) in 16.7 seconds versus over 1700 seconds for a standard SDP solver. Alongside it we run Hybrid Rotation Averaging: A Fast and Robust Rotation Averaging Approach, which reports the rotation averaging step on Trafalgar Square (7,085 images) in 4.2 seconds. On 1DSfM, the comparison point is IRAv4 from Incremental Rotation Averaging Revisited and More: A New Rotation Averaging Benchmark, which reports an average rank of 2.21 for rotation estimation against 13 methods. All methods receive the same view graphs and the same outlier filtering. Our method replaces only the inner low-rank solver of the hybrid pipeline. Cost is counted in gradient evaluations and wall-clock time, and every method gets the same tuning budget on a held-out split.
On the adversarial Max-Cut instances, no reported result was found on Lacuna for any method's escape rate. Ground truth there comes from an interior-point solve at small $n$. The strongest competitor is the Riemannian staircase: raise the rank when a certificate fails and step along the negative eigenvector. It uses the same certificate information that we do.
Three ablations isolate the key ingredient. The first is isotropic shaking, which the theory predicts will hurt. The second is Gaussian noise injection with per-step perturbation energy matched to the shaking. The third is the explicit-penalty realization compared with the oscillating one, each integrated with Euler and with fourth-order Runge–Kutta at equal gradient budgets.
Beating the baselines means the following. On adversarial instances, we need a higher fraction of runs reaching a certified optimum at fixed rank than restarts or noise achieve with the same gradient budget, and lower peak memory than the staircase at equal success. On synthetic rotation cycle graphs, where the duality paper reports local solvers failing in 30–70% of cases while the dual SDP always succeeds, we need to approach the dual SDP's success rate at the cost of a first-order method. On real benchmarks, we need equal or better rotation error with no more than a small constant-factor slowdown relative to the cited timings.
Why not just…?
Why not just use random restarts or noise injection? The Burer–Monteiro failure paper shows that the traps have strictly positive curvature, so perturbations below the barrier height relax back. Restarts help only if the global basin is large, which adversarial instances are built to prevent. The matched-energy noise ablation tests this directly. If noise matches the steered shaking at equal budget, the averaging mechanism adds nothing, and we will report that outcome.
Why not just raise the rank (the Riemannian staircase)? This is a real threat. It uses the same certificate and is guaranteed to finish once the rank reaches $n$. Spurious minima persisting to rank $n/2$ mean it may need to climb a long way, with memory growing proportionally. Our advantage, if any, lies at fixed and memory-bounded rank. The memory-versus-success curves on adversarial and large rotation instances will show whether that regime matters. If the staircase solves them within a rank increase of one or two, our method's case shrinks to a niche, and the note will say so.
Why not just add the effective penalty directly and forget the oscillation? For the shaking patterns we use, the extra term is cheap to write down, so this may be the better algorithm. The proposal therefore treats the explicit penalty as a co-equal realization rather than a straw man. The oscillating version is kept only if it beats the penalty, for instance through the finite-amplitude excursions that averaging discards. The integrator-order ablation still tests the theory: it checks that the averaged landscape is what the shaken dynamics actually see.
Why not just blur the objective (Gaussian continuation) or use a particle swarm? Continuation's own analysis fails at bifurcations of minimum paths (A Theoretical Analysis of Optimization by Gaussian Continuation). Blurring is also not tied to a certificate, so it can move the global optimum. Swarm methods have been demonstrated only up to roughly 80 dimensions (Fast and Robust Consensus-Based Optimization via Optimal Feedback Control), far below the thousands of rotations in Trafalgar Square. We include continuation on the Max-Cut instances as a secondary baseline at matched budget.
Decisive Checks
Three results would settle the idea. First, the predicted harm from isotropic shaking must appear: runs should drift toward rank-one configurations and certified success should fall below plain Burer–Monteiro. If the sign is wrong, the averaging analysis is wrong. Second, on the adversarial instances, certificate-steered shaking at fixed rank must escape traps that matched-energy noise does not, and the escape threshold must follow the predicted $A/\omega$ scaling across a sweep of $\omega$. Third, the oscillating realization must reproduce the explicit penalty's trajectory under fourth-order Runge–Kutta and fail to do so under Euler at the same gradient budget. Only then does high-order integration earn a place in the method rather than being decoration.
If all three hold and the real-data comparison is at least neutral, the work delivers a landscape-shaping tool for low-rank relaxations grounded in physical stabilization theory. If only the second holds through the explicit penalty, it still delivers a principled, certificate-steered regularizer that does not require increasing the rank.
References
- The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound
- Dynamical stabilization of solitons in cubic-quintic nonlinear Schrödinger model
- Direct Runge-Kutta Discretization Achieves Acceleration
- Rotation Averaging and Strong Duality
- Hybrid Rotation Averaging: A Fast and Robust Rotation Averaging Approach
- High-Order and Energy-Stable Implicit-Explicit Relaxation Runge-Kutta Schemes for Gradient Flows
- A Theoretical Analysis of Optimization by Gaussian Continuation
- Consensus-Based Optimization Methods Converge Globally
- Fast and robust consensus-based optimization via optimal feedback control
- Incremental Rotation Averaging Revisited and More: A New Rotation Averaging Benchmark