Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search

1. Introduction.

• Truncated least-squares is robust to noise and outliers, while its semidefinite relaxation offers a typically polynomial-time alternative to a non-convex, hard-to-solve formulation [60].The paper assesses tightness by whether an SDR solution yields a global minimizer of the corresponding QCQP.Source: §1 · pp. 1–2
• The paper asks whether a specific semidefinite relaxation for robust rotation search is tight and provides tightness characterizations accounting for noise, outliers, and both.It notes that fewer works [39] provide theoretical insights into SDR robustness to noise, while only a few relaxations [60] are empirically robust to outliers.Source: §1 · p. 1
• The goal is to recover the rotation relating inlier 3D point pairs and identify which pairs are outliers, given bounded noise.The inlier pairs are related by an unknown rotation R*_0 up to bounded noise.Source: §1 · p. 2
• In noiseless, outlier-free data, the SDR is always tight, and the paper gives a shorter proof than prior work [59, Section E.3].The result is Theorem 3.1.Source: §1 · p. 2
• For noiseless data with outliers, tightness holds for sufficiently small truncation parameters with random outliers regardless of their number, but not for parameters set too large.Clustered outlier pairs defined by a rotation different from the true rotation can also make the SDR not tight.Source: §1 · p. 2
• For noisy data without outliers, the SDR is tight for sufficiently small noise and sufficiently large truncation parameters; the noisy, outlier-contaminated case receives a tightness characterization as well.The paper describes the noisy-with-outliers case as the most challenging and discusses it sparingly.Source: §1 · p. 2

2. (TLS-R) and Its Relaxation: Review and New Insights.

• The section derives the SDR from TLS-R through equivalent TLS-Q and QCQP formulations, using lifting, and obtains the dual program by Lagrangian calculation.Table 1 provides descriptions of the different programs.Source: Table 1 · p. 3

2.1. Derivation.

• For each point pair, squared rotation residual can be expressed as a quadratic form in the unit quaternion representing the rotation.The derivation also gives an eigenvalue characterization of the associated matrix, which the authors note they had not found in the literature except in their prior work.Source: §2.1 · pp. 3–5
• The SDR is obtained by lifting the QCQP, and its dual program is derived through standard Lagrangian calculation.The derivation is simpler than the development in and dispenses with its quaternion product operation.Source: §2 · p. 3, §2.1 · p. 6

2.2. The Tightness and Optimality Conditions.

• Given the assumed inlier-preserving and outlier-rejecting solution of TLS-Q, the SDR is tight if and only if a dual matrix of the specified form satisfies the stated optimality conditions.The paper establishes strong duality between the SDR and its dual program.Source: §2.2 · p. 7
• The main proof strategy is to find dual certificates satisfying those conditions, or show that no such certificates exist.The certificate entries and scalar multiplier are the quantities used to establish tightness or its failure.Source: §2.2 · p. 8

3.1. The Noiseless + Outlier-Free Case.

• Without noise or outliers, SDR is tight, and the authors give a shorter proof than.The rank-one matrix formed from a global minimizer of the original problem globally minimizes SDR.Source: §3.1 · pp. 8–9

3.2. The Noiseless + Outliers Case.

• For noiseless outliers, SDR is tight when 0 < c_j^2 < λ_min(Q_j) for every outlier, but W* is not a global minimizer if c_j^2 > (w*_0)^T Q_j w*_0 for any outlier.For randomly drawn outliers from a continuous distribution, λ_min(Q_j) > 0 with probability 1, so SDR is tight when c_j^2 is sufficiently small.Source: §3.2 · pp. 9–10
• Under the theorem’s clustered-outlier assumptions, W* is not a global SDR minimizer; experiments nevertheless find SDR robust to 40%-50% uniformly random outliers sampled from S2.The analysis does not account for the final projection step and does not bound how far SDR global minimizers can be from W*.Source: §3.2 · p. 11

3.3. The Noisy + Outlier-Free Case.

• For noisy inliers without outliers, SDR is tight under the theorem’s truncation condition when ζ ≥ ℓ/(ℓ−1), and the estimated rotation’s quaternion error grows proportionally with noise.The theorem concerns the global minimizer of TLS-Q; ζ is the ratio of the second-smallest to minimum eigenvalue of the summed data matrix.Source: §3.3 · p. 13
• The proof verifies Proposition 2.5’s conditions, establishing (SDR) tightness in the noisy, outlier-free case.Source: §3.3 · p. 14
• The condition’s ∥Qi ŵ∥² term accounts for noise breaking a noiseless eigenvalue inequality, while |di| is two orders smaller and tends to zero as noise vanishes.The authors regard the |di| term as an analysis artifact; they propose an ideal condition but could not prove it because it requires a matrix-inverse inequality.Source: §3.3 · pp. 14–15
• In Figure 1a, ζ is approximately 250 at 10% noise, approximately 25,000 at 1% noise, and infinite in the noiseless case, empirically validating ζ ≥ 100/99.Figure 1 numerically illustrates condition (3.7) using 500 trials with ℓ = 100.Source: §3.3 · p. 14, Figure 1 · p. 15
• The error bound becomes zero as noise vanishes, and its stability depends on the second-smallest eigenvalue; the associated ratio is small and well-behaved for random Gaussian data.Source: §3.3 · p. 15

3.4. The Noisy + Outliers Case.

• With ζin ≥ k*/(k*−1), 0 < c²j < λmin(Qj) for each outlier, and condition (3.7) for inliers, (SDR) is tight and an analogous error bound holds.Under these assumptions, (TLS-Q) rejects outliers and admits inliers.Source: §3.4 · pp. 15–16

• The probability argument also invokes a result for random points and takes the sample size ℓ sufficiently large.Source: §4 · p. 16
• The combined event holds with probability at least 1 − exp(−t^2/2) − 2 exp(−3t^2/8) after applying a union bound to Lemmas 4.3–4.5.Source: §4 · pp. 16–17
• The auxiliary lemmas assume random 3D points with i.i.d. N(0, 1) entries.Source: §4 · p. 17

5. Discussion and Future Work.

• The investigation covers four cases of SDR tightness for truncated least-squares in robust rotation search, with improvements over prior work or new theoretical results in each case.The authors suggest the investigation could inform analysis of SDRs for other geometric-vision tasks.Source: §5 · p. 18
• The analyzed relaxation is the first, lowest-order relaxation in the Lasserre hierarchy, also known as the Shor relaxation.A tighter relaxation has quadratically more constraints, but its analysis is left for future work because it is significantly harder.Source: §5 · p. 19
• The authors identify analysis of the tighter relaxation as a future challenge because it requires more dual certificates or more abstract optimality conditions.Source: §5 · p. 19

Appendix A. Proof of Lemma 3.8.

• The proof establishes bS_i ⪰ 0 by showing bT_i ⪰ 0, using the assumption ζ ≥ ℓ/(ℓ−1).It also identifies the relevant eigenvalue as the second smallest eigenvalue of the indicated matrix.Source: Appendix A · pp. 19–20
• A coordinate change makes the left-hand side a quadratic polynomial in a_i, which the proof minimizes with respect to a_i4 at the stated value.Source: Appendix A · p. 20
• Under assumption (3.7), the proof concludes that the derived quadratic inequality holds.Source: Appendix A · pp. 20–21

Appendix B. Supplementary Material: Detailed Comparison to Yang & Carlone [59].

• The appendix states that (QCQP-YC) and the paper’s (QCQP) are equivalent, with both minimum values equal to the minimum of (TLS-Q).It describes (SDR-YC) as Yang and Carlone’s naive relaxation.Source: Appendix B · p. 21
• If (TLS-Q) rejects all outliers and keeps all inliers, (SDR) is tight if and only if (SDR-YC) is tight, assuming c2_i ≠ λmax(Q_i) for every i.Source: Appendix B · pp. 21–22
• The proof shows that the tightness implication follows by establishing the stationary and dual-feasibility conditions for (SDR).Source: Appendix B · pp. 22–23