Exact Camera Location Recovery by Least Unsquared Deviations∗
Gilad Lerman1, Yunpeng Shi1, and Teng Zhang2
1

arXiv:1709.09683v2 [] 3 Oct 2017

2

School of Mathematics, University of Minnesota
Department of Mathematics, University of Central Florida
{lerman, shixx517}@umn.edu, Teng.Zhang@ucf.edu

Abstract
We establish exact recovery for the Least Unsquared Deviations (LUD) algorithm of Özyesil
and Singer. More precisely, we show that for sufficiently many cameras with given corrupted
pairwise directions, where both camera locations and pairwise directions are generated by a special
probabilistic model, the LUD algorithm exactly recovers the camera locations with high probability.
A similar exact recovery guarantee was established for the ShapeFit algorithm by Hand, Lee and
Voroninski, but with typically less corruption.

1

Introduction

The Structure from Motion (SfM) problem asks to recover the 3D structure of an object from its 2D images.
These images are taken by many cameras at different orientations and locations. In order to recover
the underlying structure, both the orientations and locations of the cameras need to be estimated [19].
The common procedure is to first estimate the relative orientations between pairs of cameras from the
corresponding essential matrices and then use them to obtain the pairwise directions between cameras
[12]. The global orientations up to an arbitrary rotation can be concluded via synchronization from
the pairwise orientations [1, 6, 10, 13, 15, 18]. The locations can be derived from the pairwise directions
[1, 2, 8, 9, 10, 11, 16, 17, 18, 22, 23].
This paper mathematically addresses the latter subproblem of estimating global camera locations
when given corrupted pairwise directions with missing values. In doing so, it follows the corruption
model and the mathematical problem of Hand, Lee and Voroninski (HLV) [11], which are described next.
The HLV model: Assume n camera locations {t∗i }ni=1 ⊆R3 i.i.d. sampled from N(0,I). Let G(n,p)
be the Erdös-Rényi graph of n vertices V ={t∗i }ni=1 with probability of connection p. That is, denoting
[n] = {1,2,...,n}, an edge with index ij ∈ [n] × [n] is independently drawn between t∗i and t∗j with
probability p. Let E denote the set of indices of drawn edges and WLOG assume that if ij ∈E, then
i<j, so ji is not repeated. Note that the set of indices of missing edges is [n]×[n]\E. Assume further
that G(V,E) is parallel rigid. Namely, all locations {t∗i }ni=1 can be uniquely recovered from the true
pairwise directions {γij∗ }ij∈E , where
t∗i −t∗j
γij∗ = ∗ ∗
(1)
kti −tj k
and k·k denotes the Euclidean norm. This assumption is necessary for the well-posedness of the recovery
problem. For each edge with index ij ∈ E, a possibly corrupted pairwise direction vector γij ∈ S 2 is
assigned. More precisely, E is partitioned into sets of “good” and “bad” indices, Eg and Eb respectively,
and the direction vectors are obtained in each set as follows: If ij ∈ Eg , then γij = γij∗ ; otherwise,
{γij }ij∈Eb are arbitrarily assigned in S 2. The level of corruption of the HLV model is quantified by
b = n1 (maximal degree of Eb). Note that |Eb|< 21 bn2, where |Eb| denotes the number of elements in
Eb. The parameters of the HLV model are n, p and b.
∗

This work was supported by NSF award DMS-14-18386.

1

The HLV problem and its solutions: Given data sampled from the HLV model and assuming
a bound on the corruption parameter b, the exact recovery problem is to reconstruct, up to ambiguous
translation and scale, {t∗i }ni=1 from {γij }ij∈E . Hand, Lee and Voroninski addressed this problem while
assuming b =O(p5/log3n) and using their ShapeFit algorithm [11]. Here we address this problem with
the weaker assumption b =O(p7/3/log9/2n), while using the LUD algorithm [17].

1.1

Previous Works

In the past two decades, a variety of algorithms have been proposed for estimating global camera
locations from corrupted pairwise directions [19]. The earliest methods use least squares optimization
[1, 2, 9] and often result in collapsed solutions. That is, they tend to wrongly estimate many camera
locations near the origin. Constrained Least Squares (CLS) [22, 23] utilizes a least squares formulation
with an additional constraint to avoid collapsed solutions. Another least squares solver with anti-collapse
constraint is semidefinite relaxation (SDR) [18]. Its constraint is non-convex and makes it hard to solve
even after convex relaxation. Other solvers include the L∞ method [16] and the Lie-Algebraic averaging
method [10]. However, all the above methods are sensitive to outliers.
Recently, Özyesil and Singer proposed the Least Unsquared Deviation (LUD) algorithm [17] and
numerically demonstrated its robustness to outliers and noise. Given the pairwise directions {γij }ij∈E ,
the LUD algorithm estimates the camera locations {t∗i }ni=1 by {t̂i}ni=1 ⊂R3, which solve the following
constrained optimization problem with theX
additional parameters {α̂ij }ij∈E ⊂R:
X
n
({t̂i}i=1,{α̂ij }ij∈E )= argmin
kti −tj −αij γij k s.t. αij ≥1 and
ti =0.
(2)
{ti }n ⊂R3
i=1
ij∈E
{αij }ij∈E ⊂R

i

This formulation is very similar to that of CLS, but uses least absolute deviations instead of least
squares in order to gain robustness to outliers. Numerical results in [17] demonstrate that LUD can
exactly recover the original locations even when some pairwise directions are maliciously corrupted.
Following Özyesil and Singer, Hand, Lee and Voroninski [11] proposed the ShapeFit algorithm as
a theoretically guaranteed solver. Given the pairwise directions {γij }ij∈E , the ShapeFit algorithm
estimates the locations {t∗i }ni=1 by solving the following convex optimization problem:
n
X
X
X
min
kPγ⊥ (ti −tj )k s.t.
hti −tj ,γij i=1 and
ti =0,
n
{ti }i=1 ⊂R3

ij

ij∈E

ij∈E

i=1

where Pγ⊥ denotes the orthogonal projection onto the orthogonal complement of γij . Empirically, for low
ij
levels of noise and corruption, ShapeFit is more accurate than LUD. However, for high levels of corruption
and noise, LUD is more accurate and stable. Figure 1 demonstrates the empirical behavior of ShapeFit
and LUD for synthetic data. We remark that in this case of synthetic data, stability can be measured
as the magnitude of the rate of change of accuracy with respect to corruption or noise. Figures 1 and
2 of Goldstein et al. [8] demonstrate similar behavior, but emphasize exact recovery at lower corruption
levels, where ShapeFit often outperforms LUD. Practical results are demonstrated in [8, 21] and seem
to indicate similar behavior. Most notably, LUD is more stable, where stability for real data sets is
demonstrated by consistent performance of different simulations for the same data set as well as consistent
performance among different data sets. We remark that [8] presents an accelerated version of ShapeFit
and [21] presents a novel heuristic for estimating the fundamental matrices, which directly relies on LUD.
The mathematical problem discussed in this paper is an example of a convex recovery problem. Other
such problems include, for example, recovering sparse signals, low-dimensional signals and underlying
subspaces. There seem to be two different kinds of theoretical guarantees for convex recovery problems.
Guarantees of the first kind construct dual certificates [3, 4, 5]. Guarantees of the second kind show that
the underlying object is the minimizer of the convex objective function, and it is sufficient to show this
in a small local neighborhood [7, 14, 20, 24, 25]. The latter guarantees often require geometric methods.
It is evident from page 10 of [11] that the guarantees of ShapeFit are of the second kind. Nevertheless,
the graph-theoretic approach of [11] is completely innovative and enlightening. In particular, it clarifies
the effect of vertex perturbation on edge deformation.

2

Figure 1: Empirical performance of LUD and ShapeFit under corruption and noise for synthetic data. Left: Data is
generated by the HLV model with n=50 and p=0.5. The corruption level is measured by |Eb |/|E| instead of b and takes
values in [0,1]. Right: The ground truth is generated by the HLV model with n=50, p=0.5 and Eb =∅. For each ij ∈E,
∗
∗
γij =(γij
+σvij )/kγij
+σvij k, where vij is uniformly distributed on S 2 and 0≤σ ≤1 is the noise level. In both figures the
P
∗
∗ 2 Pn
∗ 2
performance is measured by the normalized root mean squared error (NRMSE): NRMSE2 = n
i=1 kκ t̂i −ti k /
i=1 kti k ,
P
∗
∗ 2
where κ =argminκ∈R ij∈E kκt̂i −ti k .

1.2

This Work

This paper proves exact recovery of LUD under the HLV model up to ambiguous scale and translation.
More precisely, it establishes the following theorem.
Theorem 1. There exist absolute constants n0, C0 and C1 such that for n>n0 and for {t∗i }ni=1 ⊆R3,
E ⊆ [n]×[n] and {γij }ij∈E ⊆ R3 generated by the HLV model with parameters n, p and b satisfying
C0n−1/3log1/3n≤p≤1 and b ≤C1p7/3/log9/2n, LUD recovers {t∗i }ni=1 up to translation and scale with
probability 1−1/n4.
To the best of our knowledge this theorem is the first exact recovery result for LUD under a corrupted
model. Theorem 2 of Hand, Lee and Voroninski [11] provides exact recovery for ShapeFit under the
same model. Both theorems restrict the minimal value of p and the maximal degree of corruption b.
In Theorem 2 of [11], p=Ω(n−1/5log3/5n), whereas in Theorem 1, p=Ω(n−1/3log1/3n). Therefore, our
setting allows exact recovery for sparser graphs. For example, if p≈n−α, our theorem allows 0<α<1/3,
whereas [11] allows 0<α<1/5. More importantly, Theorem 1 tolerates more corruption. Indeed, the
higher the upper bound on b, the higher the corruption that the algorithm can tolerate. Theorem 2 of
[11] requires a bound of order O(p5/log3n) and Theorem 1 requires a bound of order O(p7/3/log9/2n).
Therefore in sparse settings where p  1, e.g., p ≈ n−α, Theorem 1 guarantees recovery with more
corruption than Theorem 2 of [11]. Nevertheless, our analysis borrows various ideas from the work
of Hand, Lee and Voroninski [11]. In fact, we find it interesting to show that their innovative and
nontrivial ideas are not limited to a specific objective function, but can be extended to another one.
The main ideas of the proof of Theorem 1 are discussed in Section 2, while additional technical details
are left to other sections. The novelties of this work are emphasized in Section 2.5.

2

Proof of Theorem 1

The outline of the proof is as follows. Section 2.1 reformulates the LUD problem. Section 2.2 uses
the new formulation to define the “good-long-dominance condition” and states that under this condition
LUD exactly recovers {t∗i }ni=1. Section 2.3 defines the “good-shape condition” and claims that it implies
the good-long-dominance condition. Section 2.4 shows that under the HLV model the good-shape
condition is satisfied with high probability and thus concludes the proof of the theorem. At last,
Section 2.5 discusses the novelties in our proof. Details of proofs of the main results of this section
are left to Sections 3-5 and the Appendix.
3

t̂i −t̂j

0

γij

t̂i −t̂j

0

α̂ij γij

Figure 2: Demonstration of the choice of α̂ij when κ>1
(Pγij (t̂i −t̂j )=κγij ). By definition, α̂ij =kPγij (t̂i −t̂j )k.

γij = α̂ij γij

Figure 3: Demonstration of the choice of α̂ij when κ≤1
(Pγij (t̂i −t̂j )=κγij ). Since κ≤1 and α̂ij ≥1, α̂ij =1.

Throughout the rest of the paper we assume that |Eb|>0. This assumption is sufficient for concluding
the proof. Indeed, Proposition 1 of [17] implies that when Eb = ∅, LUD recovers the true solution
{t∗i }ni=1 up to translation and scale.

2.1

Reformulation of the Problem

In order to reformulate the LUD optimization problem, we use the following observation: If {t̂i}ni=1
and {γij }ij∈E are known, then
( for each ij ∈E
kPγij (t̂i −t̂j )k, if Pγij (t̂i −t̂j )=κγij for κ>1;
α̂ij =
1,
if Pγij (t̂i −t̂j )=κγij for κ≤1,
where Pγij denotes the orthogonal projection onto γij . Indeed, following (2) and the demonstration
in Figure 2, if Pγij (t̂i −t̂j )=κγij with κ>1, then
X
α̂ij ≡ argmin
kt̂i −t̂j −αij γij k=kPγij (t̂i −t̂j )k.
{αij }ij∈E :
ij∈E
αij ≥1, ∀ij∈E

Otherwise, as demonstrated in Figure 3, α̂ij =1. Plugging the above values of {α̂ij }ij∈E into (2), we
obtain the equivalent LUD formulation:
n
X
X
n
{t̂i}i=1 = argmin
fij (ti,tj ) subject to
ti =0,
(3)
3
{ti }n
i=1 ⊂R ij∈E

where
fij (ti,tj )=

i=1

(
kPγ⊥ (ti −tj )k, if Pγij (ti −tj )=κγij for κ>1;

ij
(4)
kti −tj −γij k, if Pγij (ti −tj )=κγij for κ≤1.
Our analysis requires formulating an oracle problem that determines the particular shift and scale found
by LUD. That is, we assume we know the ground truth solution {t∗i }ni=1 and we ask for the scale c∗ and
shift ts such that {c∗t∗i +ts}ni=1 minimizes the LUD problem. This oracle problem is formulated as follows:
n
X
X
∗
(c ,ts)= argmin
fij (ti,tj ) subject to
ti =0 and ti =ct∗i +t.
(5)

c∈R,t∈R3 ij∈E
Appendix A that c∗ is

i=1

We later show in
unique with overwhelming P
probability under our assumption
that Eb =
6 ∅. The uniqueness of ts follows from the LUD constraint iti =0. We will prove Theorem
1 by showing that t̂i =c∗t∗i +ts for all i∈[n].

2.2

Exact Recovery under the Good-Long-Dominance Condition

We establish the recovery of the ground truth locations {t∗i }ni=1 by LUD up to translation and scale
under a geometric condition, which we refer to as the good-long-dominance condition. The set of good
and long edges, Egl, and its complement are defined by
c
Egl ={ij ∈Eg | kt∗i −t∗j k>1/c∗} and Egl
=E\Egl.
(6)

4

We say that Egl and G(V,E)
satisfy the P
good-long-dominance condition if for any perturbation vectors
P
n
∗
{i}ni=1 ∈R3 such that ni=1i =0
and
i=1 hi ,ti i=0, X
X
kPγ∗⊥ (i −j )k≥
ki −j k.
(7)
ij

c
ij∈Egl

ij∈Egl

In order to clarify this condition, we assume that the variables {ti}ni=1 are perturbed by {i}n1=1
respectively from the ground truth {c∗t∗i +ts}ni=1. As explained later in (16), the change in the objective
function of (3), when restricted to the sum over Egl, is the LHS of (7). Furthermore, as explained
c , is bounded above by
later in (17), the change in the objective function of (3), when restricted to Egl
the RHS of (7). The condition thus shows that the change in the objective function due to the good
and long edges dominates the change due to all other edges.
At last, we formulate the following theorem, which is proved in Section 3.
Theorem 2. If V ={t∗i }ni=1, E ⊆[n]×[n] and {γij }ij∈E are generated by the HLV model and Egl and
G(V,E) satisfy the good-long-dominance condition, then LUD exactly recovers the ground truth solution
up to translation and scale. That is, the solution of (3) has the form t̂i = c∗t∗i +ts for i ∈ [n], where
c∗ and ts solve (5).

2.3

Exact Recovery under the Good-Shape Condition

We show that the good-long-dominance condition is satisfied when the graph E has certain properties.
We first review the definitions of the following two properties suggested in [11]: a p-typical graph and
c-well distributed vertices.
Definition 2.1. A graph G(V,E) is p-typical if it satisfies the following propositions:
1. G is connected.
2. Each vertex of G has degree between 12 np and 2np.
3. Each pair of vertices has codegree between 12 np2 and 2np2, where the codegree of a pair of vertices
ij is defined as |{k ∈[n]:ik,jk ∈E}|.
Definition 2.2. Let G=G(V,E) be a graph with vertices V ={ti}ni=1 ⊆R3. For x, y ∈R3, c>0 and
A⊆V , we say that A is c-well-distributed with respect to (x,y) if the following holds for any h∈R3:
1 X
kPSpan{t−x,t−y}⊥ (h)k≥ckP(x−y)⊥ (h)k.
|A|
t∈A

We say that V is c-well-distributed along G if for all distinct 1≤i,j ≤n, the set Sij ={tk ∈V :ik,jk ∈
E(G)} is c-well-distributed with respect to (ti,tj ).
Let Kn denote the complete graph with n given vertices and E(Kn) denote the set of edges of Kn.
When saying that V is c-well-distributed along Kn, we assume that V has n vertices and Kn is the
complete graph with these vertices.
Using the above notation and definitions, we formulate a geometric condition on Egl and G(V,E)
that guarantees exact recovery by LUD.
Definition 2.3 (Good-Shape Condition). Let p, β, 0, c1 ∈(0,1], c0 ≥1 and let V ={t∗i }ni=1, E ⊆[n]×[n]
and {γij }ij∈E be generated by the HLV model with Egl and Eglc defined above. We say that Egl and
G(V,E) satisfy the good-shape condition with the parameters p, β, 0, c1, c0, if the following hold:
1. G is p-typical.
∗ i≥β 2
2. For any distinct ij ∈E(Kn), there exists at least n−1n indices k =
6 i,j such that 1−hγij∗ ,γik
∗
∗
2
and 1−hγij ,γjk i≥β .
3. For any distinct ij ∈E(Kn), kt∗i −t∗j k≤c0µ, where
X
1
µ=
kt∗i −t∗j k.
(8)
|E(Kn)|
ij∈E(Kn )

4. The maximal degree of Eglc is bounded by 0n.
5. V is c1-well distributed along G and along Kn.
6. For any distinct i, j ,k ∈[n], t∗i , t∗j and t∗k ∈V are not collinear.
5

At last, we claim that under the HLV model the good-shape condition with certain restriction on
its parameters implies exact recovery. The proof verifies that the good-long-dominance condition holds
and then applies Theorem 2.
Theorem 3. If V = {t∗i }ni=1, E ⊆ [n]×[n] and {γij }ij∈E are generated by the HLV model, Egl and
G(V,E) satisfy the good-shape 
condition with respect
p, β,0, 1, c1,, c0 and if
 to the parameters

2
2
1
1
βc1p βc p c1p
and 1 ≤min
,
,
(9)
0 <min 22 3 , 191 ,
144c0 96
2 c0 2 c0 16
then the solution {t̂i}ni=1 of (3) has the form t̂i =c∗t∗i +ts for i∈[n], where c∗ and ts solve (5).

2.4

Conclusion of Theorem 1

We verify that under the HLV model the good-shape condition holds with parameters satisfying (9)
and with high probability. Combining this observation with Theorem 3 results in Theorem 1.
We assume the conditions of Theorem 1 and set the following parameters
p
p
p
c
β = 18
, 1 =
and c0 =64 logn,
, c1 = √
2 logn
192c0
logn
where c is a constant used in lemma 18 of [11] and is also the same as the constant q, which is clarified
in the proof of Lemma 17 of [11]. The second inequality of (9) is clearly satisfied with these parameters.
We note that establishing the first inequality of (9) requires establishing the inequality 0 ≤c0p2/log3n,
where c0 linearly depends on c. That is, it requires establishing 0 =O(p2/log3n). p
We note that Lemma 12 of [11] and the assumption of Theorem 1 that p = Ω( 3 logn/n)1 imply
property 1 of Definition 2.3 with probability
larger than 1 − O(n−5). Lemma 18 of [11] and the
p
assumption of Theorem 1 that p = Ω( 3 logn/n) imply properties 2, 3 and 5 of Definition 2.3 with
probability 1−O(n−5) and with the above choice of parameters. Furthermore, property 6 of Definition
2.3 holds almost surely since the vertices are generated by i.i.d. Gaussian distributions.
Property 4 of Definition 2.3 is about 0, whereas [11] considered instead b. The following theorem
bounds with high probability 0 by a function of b. Combining this theorem with the assumption of
Theorem 1 that b =O(p7/3/log9/2n) implies that property 4 of Definition 2.3 holds with probability
1−O(n−5) and with 0 =O(p2/log3n). We recall from the discussion above that this requirement on
0 is consistent with satisfying the first inequality of (9).
Theorem
4. If V = {t∗i }ni=1, E ⊆ [n] × [n] and {γij }ij∈E are generated by the HLV model with
p
3
7/3 /log9/2 n), then
p=Ω( logn/n) and b =O(p

n
o
3/4

0 =O max p2/log4n,(p1/4log3/8n)·b

w.p. 1−O(n−5).

(10)

We have shown that all properties of the good-shape condition hold with probability 1−O(n−5),
which can be written as 1−n−4 for sufficiently large n. This concludes the proof of Theorem 1.
We remark that the bound on b in Theorem 1 is chosen so that (10) and the first inequality of
(9) hold. Note that the lower bound on p in Theorem 1 is the one required by Theorem 4. With this
bound and the assumption on b, we include the non-trivial case where nb →∞ as n→∞.

2.5

Novelties of This Paper

This work uses ideas and techniques of [11], but considers LUD instead of ShapeFit and guarantees
a stronger rate of corruption. Here we highlight the main technical differences between the two works
and emphasize the novel arguments for handling these differences in the current work.
Reformulation: The objective function of ShapeFit depends only on {ti}ni=1, while the objective
function of LUD has the additional variables {αij }ij∈E , which introduce more degrees of freedom. To
handle this issue, we reformulated the LUD problem in (3) as a new convex optimization problem with
objective function depending only on {ti}ni=1. We also needed to introduce the oracle problem (5) that
provided the scale and shift of LUD with respect to the ground truth.
1

Recall that for a, b∈R, the notation a=Ω(b) is equivalent with b=O(a).

6

Adaptation to the new formulation: The reformulated objective function for LUD is different
than that of ShapeFit only in the case where Pγij (t̂i −t̂j )=κγij and κ≤1. We note that for ij ∈Egl,
Pγij (t̂i − t̂j ) = κγij for κ > 1. Therefore, for ij ∈ Egl the objective functions of ShapeFit and LUD
c
coincide. Our analysis thus tries to follow that of [11], while replacing Eg and Eb in [11] with Egl and Egl
respectively. Some modifications in the analysis of [11] are needed, in particular, the two mentioned below.
More faithful constraint on perturbation: Both works introduce constraints on the perturbed
solutions
{c∗t∗i +i}ni=1. Even though c∗ is not defined in [11], it can be defined as the constant satisfying
P
∗ ∗
∗ ∗
∗ n
0 n
ij∈E hc ti −c tj ,γij i=1, where the ground truth {ti }i=1 is denoted by {ti }i=1 in [11]. Hand, Lee
and Voroninski [11] require that
X
hi −j ,γij i=0
(11)
ij∈E
∗ ∗
so that any perturbed solution {t̃i}ni=1, where
X t̃i =c ti +i for all i∈[n], satisfy
ht̃i −t̃j ,γij i=1.
ij∈E

The perturbation constraint of our work appears in the formulation
Pnof the ∗good-long-dominance
P
n
condition. That is, the perturbation vectors {i}i=1 need to satisfy i=1hi ,ti i = 0 and ni=1 i = 0.
This requirement implies that
X
hi −j ,t∗ij i=0.
(12)
ij∈E(Kn )

We note that the perturbation constraint in (12) replaces γij and E in (11) with t∗ij =t∗i −t∗j and E(Kn)
respectively. Any perturbed
solution {t̃i}ni=1
X
Xthus needs to satisfy X
∗
ht̃i −t̃j ,tij i=
hc∗t∗i −c∗t∗j ,t∗ij i=c∗
kt∗ij k2.
(13)
ij∈E(Kn )

ij∈E(Kn )

ij∈E(Kn )

We believe that our perturbation constraint is more faithful to the underlying structure of the problem.
First of all, it uses the correct directions t∗ij instead of the corrupted ones γij . More importantly, it
uses t∗ij for any pair of locations, even if they are not connected by an edge. The latter property results
in improved estimates in comparison to [11]. For example, our lower bound in (37) is tighter than the
one in [11, page 13], which is multiplied by 2p2 and suffers when p1.
Effective way of controlling 0:A deterministic upper bound on b was obtained in pages 24 and
c,
26 of [11], where b is denoted in [11] by 0. A direct analogous bound on the maximal degree of Egl
0, depends on the unknown scale c∗ and is thus not appealing. The proof of Theorem 4 shows that
with high probability 1/c∗ concentrates around a function of b, n and p and consequently 0 can also
be controlled with high probability by a function of b, n and p, as stated in Theorem 4. The proof
of this theorem is delicate and does not follow ideas of [11].

3

Proof of Theorem 2

∗ is uniquely defined with overwhelming probability and we assume WLOG that t =0,
We recall that cP
s
or equivalently ni=1t∗i =0. Indeed, the statement of Theorem 2, in particular, the good-long-dominance
condition, is independent of any shift of the locations {t∗i }ni=1.
Since the objective function in (3) is convex, in order to prove that {c∗t∗i }ni=1 solves (3), it is sufficient
n
3
to prove that for any sufficiently
i }i=1 ∈R ,
X small perturbations {X
fij (c∗t∗i +i,c∗t∗j +j )≥
fij (c∗t∗i ,c∗t∗j ).
(14)
ij∈E

ij∈E

⊥
∗
For any i∈[n],
some κ∈R, where κ is indepenPni can⊥be∗ decomposed as i =i +i , where ni =κti for
n
∗ n
dent of i, and i=1hi ,ti i=0. To clarify this, we stack {i}i=1, {i }ni=1, {⊥
i }i=1 , {ti }i=1 as rows of
⊥
∗
∗
⊥
⊥
matrices Σ, Σ , Σ and T respectively so that Σ P
=κT , Σ=Σ
+Σ and hΣ ,Σ i=tr(Σ T Σ⊥)=0.
P
n
n
Furthermore, the assumption ts =0 implies that i=1⊥
i =
i=1 i =0. Therefore, the perturbations
n
{⊥
i }i=1 satisfy the required assumptions on the perturbations used in the good-long-dominance condition.
Letting c0 =c∗ +κ, the relation i =κt∗i +⊥
i implies that
c∗t∗i +i =c0t∗i +⊥
for all i∈[n].
(15)
i
n
0
∗
Since {i}i=1 have sufficiently small norms, we may assume that c is sufficiently close to c .

7

Next, we obtain useful estimates in two complimentary cases.
Case A: ij ∈Egl. In this case, γij = (t∗i −t∗j )/kt∗i −t∗j k =γij∗ and kPγij (c∗(t∗i −t∗j ))k > 1. Combining
the latter inequality, the fact that the perturbations are arbitrarily small and the proximity of c0 to
⊥
c∗ result in kPγij (c0(t∗i −t∗j )+⊥
i −j )k>1. Applying (15), then the latter inequality and (4), and at
last the assumption ij ∈Egl concludes that
0 ∗
⊥
0 ∗
∗
⊥
⊥
⊥
⊥
fij (c∗t∗i +i ,c∗t∗j +j ) = fij (c0t∗i +⊥
⊥ (c (ti −tj )+i −j )k = kPγ ⊥ (i −j )k.
i ,c tj +j ) = kPγij
ij
This equation and the observation fij (c0t∗i ,c0t∗j )=0 imply the inequality:
X
 X
⊥
fij (c∗t∗i +i,c∗t∗j +j )−fij (c0t∗i ,c0t∗j ) =
kPγ⊥ (⊥
(16)
i −j )k.
ij

ij∈Egl
c
ij ∈Egl. Following

ij∈Egl

Case B:
the demonstration in Figures 2 and 3, we note that fij (ti,tj ) is the
distance between the following two convex sets: {αγij :α≥1} and the singleton {ti −tj }. Application
of (15) and then the triangle inequality for a distance between convex sets of R3 results in
0 ∗
⊥
0 ∗ 0 ∗
⊥
⊥
|fij (c∗t∗i +i ,c∗t∗j +j )−fij (c0t∗i ,c0t∗j )| = |fij (c0t∗i +⊥
i ,c tj +j )−fij (c ti ,c tj )| ≤ ki −j k. (17)
At last, we combine the above estimates with the good-long-dominance condition to verify (14). We
n
first apply (16), then the good-long-dominance condition of (7) with {⊥
i }i=1 that satisfy its necessary
requirements,
and at last (17), and consequently conclude
that
X
 X

∗ ∗
∗ ∗
0 ∗ 0 ∗
fij (c ti +i,c tj +j )−fij (c ti ,c tj ) ≥
fij (c0t∗i ,c0t∗j )−fij (c∗t∗i +i,c∗t∗j +j ) .
c
ij∈Egl

ij∈Egl

By rearranging terms, this equation
becomes
X
X
∗ ∗
fij (c ti +i,c∗t∗j +j )≥
fij (c0t∗i ,c0t∗j ).
ij∈E

ij∈E

By the definition of c∗ in (5) and the assumption ts =0, this equation implies (14) and thus concludes
the proof.

4

Proof of Theorem 3

We show that under the assumptions of Theorem 3, the good-shape condition implies the good-longdominance condition and consequently Theorem 3 follows from Theorem 2. Section 4.1 reviews notation
and auxiliary lemmas, which were borrowed from [11]. Section 4.2 presents the details of the proof.
While the outline of the proof in this section resembles the outline of the proof of Theorem 4
of [11], there are some nontrivial modifications. A main difference between the proofs appears in the
perturbation constraints stated earlier in (11) and (12).

4.1

Preliminaries

We first review some notation that we mainly borrowed from [11]. We denote t∗ij =: t∗i − t∗j and
for {i}ni=1 ⊆ R3, we define ηij = kPγ∗⊥ (i − j )k and δij kt∗ij k = hi − j , γij∗ i. The function η :
ij
E(Kn)×E(Kn)→R of [11] is defined as
X
η(ij,kl)=
ηmn.
(18)
m,n∈{i,j,k,l}
m<n

That is, if ij and kl do not have common elements, then η(ij,kl)=ηij +ηkl +ηik +ηil +ηjk +ηjl . If they
have one common element, e.g., i = k, then η(ij,kl) = ηij +ηil +ηjl . We modify the definition of Eg0
in [11] and define E 0(Kn) as follows:
1
E 0(Kn)={ij ∈E(Kn):kt∗ij k≥ µ},
(19)
2
where µ was defined in equation (8). Let B(ij) denote
of all kl ∈E(Kn) for which there exist
p the set
∗ ,γ ∗ i<β.
distinct a,b,c∈{i,j,k,l} satisfying {a,b}6= {i,j} and 1−hγab
bc
The following lemmas are from [11]. We remark that Lemma 2 was formulated in [11] for E 0 =Eg
as a matter of convenience, however, its formulation below still hold.

8

Lemma 1 (Lemma 3 of [11] with α=1). Let V4∗ ={t∗i }4i=1 ⊂R3 be a set of 4 distinct vertices, K4 be
the complete graph with the set of vertices V4∗ and let {i}4i=1 ⊂R3 be perturbation vectors. Then
q
β0
∗ i.
η(12,34)≥ kt∗12k|δ12 −δ34|, where β0 = min
1−hγij∗ ,γik
(20)
{i,j,k}∈[4]
4
{j,k}6={1,2}

Lemma 2 (Lemmas 5 and 6 of [11]). Let G(V,E) be p-typical and c1-well-distributed graph with n
vertices for 0<p, c1 ≤1 and let E 0 be a subset of E, where the maximal degree of its complement, E 0c,
is bounded by 0n. If 0 ≤c1p2/8, then
X
X
c1p2 X
c1p X
ηij ≥ 0
ηij .
(21)
ηij and
ηij ≥
8
16
0
0c
0
ij∈E

ij∈E

ij∈E

ij∈E(Kn )

Since Kn is 1-typical, the next corollary follows from the first inequality of Lemma 2.
Corollary 1. Let Kn be c1-well-distributed and let E 0 be a subset of E(Kn), where the maximal degree
0
of its complement, E 0c, is bounded by 0n.
then
XIf  ≤cc11/8,X
ηij ≥ 0
ηij .
(22)
8
0
0c
ij∈E

ij∈E

Lemma 4 (Lemma 14 of [11]). For any ij ∈E(Kn),
|B(ij)|≤61n2,
where 1 is the constant specified in property 2 of Definition 2.3.

4.2

(23)

Details of Proof

In order to verify the good-long-dominance
X condition
X of (7), it is sufficient to prove that
ηij ≥2
|δij |kt∗ij k.

(24)

c
ij∈Egl

ij∈Egl

P
Indeed, since 0 ≤c1p2/16 we can apply the first inequality of Lemma 2 and obtain that ij∈Egl ηij >
P
2 ij∈Ec ηij . The combination of the latter inequality with (24) and the following triangle inequality:
gl

ki −j k≤|δij |kt∗ij k+ηij yields (7).
Following [11],
P we prove (24)Pby considering three complementary cases, which depend on the
parameter δ̄ = ij∈Ec |δij |kt∗ij k/ ij∈Ec kt∗ij k.
gl

gl

c =∅. Since either E c =∅ or δ =0 for all ij ∈E c , the RHS of (24) is 0.
Case 1: δ̄ =0 or Egl
ij
gl
gl
P
c =
Case 2: δ̄ =
6 0, Egl
6 ∅ and ij∈E0(Kn) |δij | < δ̄|E0(Kn)|/8. First, we obtain a lower bound
on |E 0(Kn)|/|E(Kn)|. The definition of E 0(Kn) and then the definition of µ in (8) result in
X
1
1 X
kt∗ij k< µ|E(Kn)|=
kt∗ij k.
2
2
0
ij∈E(Kn )\E (Kn )

ij∈E(Kn )

Consequently,
X

kt∗ij k≥

ij∈E 0 (Kn )

1
2

X

1
kt∗ij k= µ|E(Kn)|.
2

(25)

ij∈E(Kn )

Using assumption 3 of the good-shape condition (Definition 2.3) and then (25), we obtain that
X
1
c0µ|E 0(Kn)|≥
kt∗ij k≥ µ|E(Kn)|
2
0
ij∈E (Kn )

and consequently
1
|E(Kn)|.
(26)
2c0
1
c
We change the definition of Lb in [11] to L={ij ∈Egl :|δij |≥ 2 δ̄} and derive the following inequality,
which is analogous to (14) of [11]:
X
X
X
1 X
|δij |kt∗ij k=
|δij |kt∗ij k−
|δij |kt∗ij k≥
|δij |kt∗ij k.
(27)
2
c
c
c
|E 0(Kn)|≥

ij∈L

ij∈Egl

ij∈Egl \L

9

ij∈Egl

We modify the definition of Fg in [11] to F 0(Kn)={ij ∈E 0(Kn):|δij |< 41 δ̄} and following [11], while
using the last assumption of this case (case 2), we obtain that
X
X
1
1
|δij |≥ δ̄|E 0(Kn)\F 0(Kn)|.
|δij |≥
δ̄|E 0(Kn)|>
8
4
0
0
0
We thus conclude that
for n≥3,

ij∈E (Kn )\F (Kn )
ij∈E (Kn )
1
0
0
|F (Kn)|> 2 |E (Kn)|. Combining this

inequality with (26) we conclude that

n(n−1)
n2
1
|E(Kn)|=
≥
.
(28)
4c0
8c0
12c0
By Lemma 4, |B(ij)| ≤ 61n2 for all ij ∈ E(Kn). Combining this with (28), we obtain that for
1
1 ≤ 144c
,
0
n2
n2
−61n2 ≥
.
(29)
|F 0(Kn)\B(ij)|≥
12c0
24c0
The rest of the proof uses the above inequalities to obtain a lower bound on the LHS of (24) and
a similar upper bound on the RHS of (24). To get the lower bound, we first note that the second
inequality of Lemma 2 implies that X
c1p X
ηij .
(30)
ηij ≥
16
|F 0(Kn)|>

ij∈Egl

ij∈E(Kn )

We thus need to find a lower bound for the RHS of (30).
By applying assumption 4 of the good-shape condition (Definition 2.3) and following the combinatorial
c and
argument establishing case 1 in the proof of Theorem 4 in [11], but replacing Eb and Eg with Egl
E(Kn) respectively, we X
obtainX
that
X
X
η(ij,kl)≤
3n2ηij +
180n2ηij .
c kl∈E(Kn )
ij∈Egl

c
ij∈Egl

kl6=ij

We recall that

0 ≤c1p2/8≤c1/8X
and

thus Corollary
that
X 1 implies
c1 X
ηij ≥
ηij ≥
ηij .
80
c
c

ij∈E(Kn )

The above two equations yield
X

ij∈E(Kn )

ij∈E(Kn )\Egl

X

η(ij,kl)≤

c kl∈E(Kn )
ij∈Egl

ij∈Egl

420 2 X
n
ηij .
c1

(31)

ij∈E(Kn )

kl6=ij

The combination of (30) and (31) results in the following lower bound on the LHS of (24)
X X
X
c1p X
c21p
ηij ≥
ηij ≥
η(ij,kl).
8
2
16
3·2 0n
c kl∈E(K )
ij∈Egl

ij∈Egl

ij∈E(Kn )

(32)

n

kl6=ij

In order to upper bound the RHS of (24) we first apply Lemma 1, which implies that for ij ∈ L
and kl ∈F 0(Kn)
β
η(ij,kl)≥ |δkl −δij |kt∗ij k.
4
For ij ∈L, |δij |> 12 δ̄ and for kl ∈F 0(Kn), |δkl |< 14 δ̄. Consequently, |δkl |<|δij |/2 and
β
β
η(ij,kl)≥ |δkl |−|δij | kt∗ij k≥ |δij |kt∗ij k.
(33)
4 0
8
c
Applying first the inclusions L⊆Egl and F (Kn)⊆E(Kn), then (33), next (29) and at last (27), we
obtain thatX X
X X
η(ij,kl)≥
η(ij,kl)
c kl∈E(Kn )
ij∈Egl
kl6=ij

≥

X

ij∈L kl∈F 0 (Kn )
kl6=ij

β n2 X
β n2 X
β
|δij |kt∗ij k≥ ·
|δij |kt∗ij k.
|F 0(Kn)\B(ij)|· |δij |kt∗ij k≥ ·
8
8 24c0
16 24c0
c

ij∈L

ij∈L

ij∈Egl

This equation implies the following upper bound for the RHS of (24):
X
3·28c0 X X
η(ij,kl).
2
|δij |kt∗ij k≤
βn2
c
c kl∈E(K )
ij∈Egl

ij∈Egl

10

n

kl6=ij

(34)

Note that (9) implies that the RHS of (34) is less than the LHS of (32). This observation concludes
(24) and consequently the proof ofPthe current case.
c =
Case 3: δ̄ =
6 0, Egl
6 ∅ and ij∈E0(Kn) |δij | ≥ δ̄|E0(Kn)|/8. Similarly to case 2, in order to
prove (24), we obtain a lower bound for the LHS of (24) and a similar upper bound for the RHS of (24).
Following [11], we define E+ = {ij ∈ E(Kn) : δij ≥ 0} and E− = {ij ∈ E(Kn) : δij < 0}. Using this
notation, we rewrite the perturbation
(12) as
X constraint ofX
∗ 2
δij ktij k +
δij kt∗ij k2 =0
ij∈E+

ij∈E−

and conclude that
X

|δij |kt∗ij k2 =

ij∈E+

X

|δij |kt∗ij k2 =

ij∈E−

1
2

X

|δij |kt∗ij k2.

(35)

ij∈E(Kn )

P
P
Next, we upper bound the RHS of (24) by a constant times the term ij∈E− kl∈E+ η(ij,kl). We
first lower bound the latter term by following [11] and applying Lemma 1 as follows
X
X X
X
X
β
β
|δij |kt∗ij k.
η(ij,kl)≥
|δij |kt∗ij k≥ (|E+|−|B(ij)|)
4
4
ij∈E− kl∈E+

ij∈E− kl∈E+ \B(ij)

ij∈E−

The successive application of property 3 of the good-shape
E 0(Kn)⊆E(Kn),
Pcondition, (35), 1the inclusion
0
0
the definition of E (Kn) together with the assumption ij∈E0(Kn)|δij |≥ 8 δ̄|E (Kn)| and (26) results in
X
X
1 X
1
|δij |kt∗ij k≥
|δij |kt∗ij k2 =
|δij |kt∗ij k2
c0µ
2c0µ
ij∈E−

≥

1
2c0µ

ij∈E−

X

ij∈E(Kn )

|δij |kt∗ij k2 ≥

ij∈E 0 (Kn )

1 1 2 1
µδ̄n2
· µ · δ̄|E 0(Kn)|≥
.
2c0µ 4
8
512c20

(36)

Assuming |E+| ≥ |E(Kn)|/2 and combining (36), the latter assumption, the fact that |E(Kn)| =
n(n−1)/2≥n2/4 for n≥2, and the assumption 1 ≤1/96, gives
 βµδ̄n4
X
βµδ̄n2  1
β
2
≥ 15 2 .
(|E+|−|B(ij)|)
|δij |kt∗ij k≥
|E(K
)|−6
n
n
1
4
2048c20 2
2 c0
ij∈E−

Consequently,
X X

η(ij,kl)≥

ij∈E− kl∈E+

βµδ̄n4
.
215c20

(37)

Assuming on the contrary that |E−|≥|E(Kn)|/2 and following the same arguments, while switching
between E+ and E−, also yield (37).
We conclude with the following upper bound on the RHS of (24) by first applying the definition
of δ̄, then condition 3 of Definition 2.3, then condition 4 of Definition 2.3, and at last (37):
X
X
215c300 X X
c
|δij |kt∗ij k= δ̄
kt∗ij k≤ δ̄c0µ|Egl
|≤ δ̄c0µ0n2 ≤
η(ij,kl).
(38)
βn2
c
c
ij∈Egl

ij∈Egl

ij∈E− kl∈E+

In order to obtain a lower bound on the LHS of (24), we use the following result from [11, page
25], which is obtained by countingX
the X
number of elementsX
in the sum of η’s:
η(ij,kl)≤3n2
ηij .
(39)
ij∈E− kl∈E+

ij∈E(Kn )

We remark that although we modified the definition of E+ and E−, this result still holds. We conclude a
lower bound on the LHS ofX
(24) by applying
the second inequality
of Lemma 2 and then (39) as follows:
c1p X
c1p X X
ηij ≥
ηij ≥
η(ij,kl).
(40)
16
48n2
ij∈Egl

ij∈E(Kn )

The combination of (38), (40) and the assumption

11

ij∈E− kl∈E+
βc1 p
>2 verifies
221 c30 0

(24).

5

Proof of Theorem 4

c ⊆E ∪E , where E ={ij ∈E :kt∗ −t∗ k<1/c∗ } is the set of short edges. Therefore, to
Note that Egl
s
s
b
i
j
conclude the theorem it is enough to estimate the maximal degree of Es. Our estimate uses the following
notation: I denotes the indicator function, the neighborhood N(t∗i ) of t∗i ∈V includes all indices j ∈[n]
such that ij ∈E, and for a, b∈R, a.b if and 
only if b=Ω(a). We 
will prove that for any fixed t∗i ∈V

2
X 
3
3
1
1
np
(41)
I kt∗i −t∗j k< ∗ .max
,p 4 b4 nlog 8 n w.p. 1−O(n−6).
4
c
log n
j∈N(t∗ )
i

Taking a union bound yields

 2
3
1 3
Maximal degree of Es
p
4  4 log 8 n
w.p. 1−O(n−5)
.max
,p
b
n
log4n
and this implies (10) and thus concludes the proof of the theorem.
We derive (41) by using the following function of c∗, which is defined with respect to a Gaussian
random variable x∼N(0,I) with pdf Φ:
Z
n
1 o
g(c∗)=Pr kxk< ∗ =
Φ(t)dt.
(42)
c
We note that for fixed

t∗i ∈V ,
∗

Pr(kt∗i −t∗j k<1/c

)=

B(0, c1∗ )

Z

Z
Φ(t)dt≤

B(t∗i , c1∗ )
kt∗i −t∗i k < 1/c∗)

B(0, c1∗ )

Φ(t)dt=Pr(kt∗j k<1/c∗)=g(c∗).

Furthermore, I(ij ∈ E and
is a Bernoulli random variable B(1,µ) with µ ≤ pg(c∗).
This observation
and Chernoff bound can be used to conclude (41). It is easily done in Section 5.1 when
√
√
g(c∗).1/ n, while only using the first term in the RHS of (41). The other case, where g(c∗)&1/ n,
is more complicated and verified in Section 5.2 and uses the second term in the RHS of (41).

5.1

√
. 1/ n.
Proof for the case where g(c∗).

In order to verify (41), we use the following version of Chernoff bound for Bernoulli random variables:
If X1,X2,···,Xn ∼B(1,µ) i.i.d., then
n
1X

Pr
Xi −µ>δµ <exp(−δnµ/3) for any δ ≥1.
(43)
n
i=1
We apply this inequality to
(44)
Xij =I(ij ∈E and kt∗i −t∗j k<1/c∗), where i∈[n] is fixed and j ∈[n]\{i}.
As we explained above, Xij ∼B(1,µ), where µ≥pg(c∗) and thus with probability 1−exp(−Ω(δnpg(c∗)))
X 
X
1
I kt∗i −t∗j k< ∗ =
Xij .(δ+1)npg(c∗)≈δnpg(c∗).
c
∗
Taking

j∈N(ti )
4
δ =p/(log ng(c∗))

j∈[n]\{i}

results in


2
 np2
X 
−Ω np4
1
log n
.
(45)
I kt∗i −t∗j k< ∗ . 4 w.p. 1−e
c
log
n
∗
j∈N(ti )
p
Note that the assumptions g(c∗).n−1/2 and p& 3 logn/n guarantee that our choice of δ satisfies the
constraint δ ≥1 in (43).
Indeed, δ =p/(log4ng(c∗))=Ω(n1/6/log11/3n)>1 for n sufficiently large. Also,
p
the assumption p& 3 logn/n implies that Ω(np2/(log4n))&n1/3/log3/10n. Therefore, the probability
in (45) is greater than 1−O(n−6) and thus (41) is proved in the current case.

5.2

√
& 1/ n.
Proof for the case where g(c∗)&

We use another version of Chernoff bound for Bernoulli random variables: If X1,X2,···,Xn ∼B(1,µ)
i.i.d., then
n
 1X

Pr
Xi −µ >δµ <2·exp(−δ2µn/3) for all 0≤δ ≤1.
(46)
n
i=1

12

Applying this inequality to {Xij }j∈[n]\{i} of (44) yields that with probability 1−exp(−Ω(npg(c∗)))
X 
X
1
I kt∗i −t∗j k< ∗ =
Xij .npg(c∗).
(47)
c
∗
j∈N(ti )

j∈[n]\{i}

Note that the probability 1−exp(−Ω(npg(c∗))) exponentially approaches 1 as n → ∞. Indeed, the
√
assumptions g(c∗)&1/ n and p&n−1/3log1/3n imply that Ω(npg(c∗))=Ω(n1/6log1/3n).
Our goal is to upper bound the RHS of (47) by the second term in the RHS of (41). In order to
do this we use the following Lemmas, which we prove in Section 5.3.
Lemma 5. Assuming the setting of Theorem 4, there exists an absolute constant M such that
1
≤M w.p. 1−O(n−6).
(48)
c∗
√
Lemma 6. Assume the setting of Theorem√4. If g(c∗)&1/ n, then
g(c∗) b logn
.
w.p. 1−O(n−6).
(49)
c∗
p
Given the setting of Theorem 4, we claim that there exists xM ∈R3 with kxM k=M such that
1
1
(50)
Φ(xM )Vol ∗ ≤g(c∗)≤Φ(0)Vol ∗ w.p. 1−O(n−6).
c
c
The second inequality of (50) is deterministic and follows from the definition of g in (42). The first
inequality follows from Lemma 5. Indeed, with the same probability the minimum of Φ in the closed
ball B(0,1/c∗) is greater than the minimum of Φ in B(0,M) and it occurs on the boundary of this
∗ )3 and applying this observation to (49) results in
ball. Equation (50) implies that g(c∗)≈1/(c
  √logn  3
4
b
w.p. 1−O(n−6).
(51)
g(c∗).
p
−6 ),
Combining (51) with (47) yields that with probability 1−O(n
√


X 
3
1 3
1
b logn  34
I kt∗i −t∗j k< ∗ .npg(c∗).np
=p 4 b4 nlog 8 n.
c
p
∗
j∈N(ti )

This concludes Theorem 4, though it remains to prove Lemmas 5 and 6.

5.3

Proofs of Lemmas 5 and 6

We first establish the following
for the proofs of both lemmas:
Xinequality, which is necessary
p
∗
∗
2
kti −tj k.bn logn w.p. 1−O(n−6).
ij∈E:

(52)

kt∗i −t∗j k< c1∗

We prove (52) by establishing an inequality involving the left and right derivatives of fij (ct∗i ,ct∗j ) in c.
Since fij (ti,tj ) only depends on ti −tj and since weX
assumed that ts =0, c∗ can be defined as follows:
∗
c =argmin
Fij (c),
(53)
c∈R

where

Fij (c)=fij (ct∗i ,ct∗j ).

ij∈E

This expression implies that
X
X
Fij0 (c∗−)≤0 and
Fij0 (c∗+)≥0.
ij∈E

(54)

ij∈E

We estimate Fij0 (c) for ij ∈E in 5 complementary cases.
1. For ij ∈Eg and c>1/kt∗i −t∗j k, Fij (c)=0 and thus Fij0 (c)=0.
2. For ij ∈Eg and c<1/kt∗i −t∗j k, Fij (c)=1−kt∗i −t∗j k·c and thus Fij0 (c)=−kt∗i −t∗j k.
3. For ij ∈ Eb and c > 1/kt∗i − t∗j k, Fij (c) = sin α · kt∗i − t∗j k · c, where 0 < α ≤ π/2 and thus
Fij0 (c)≤kt∗i −t∗j k.
4. For ij ∈Eb and c<1/kt∗i −t∗j k, Fij (c)=kct∗i −ct∗j −γij k and thus by the triangle inequality
k(c+h)t∗i −(c+h)t∗j −γij k−kct∗i −ct∗j −γij k
Fij0 (c) = lim
h→0
h
∗
∗
khti −htj k
≤ lim
=kt∗i −t∗j k.
h→0
h

13

5. For ij ∈E and c=1/kt∗i −t∗j k, the function Fij (c) is not differentiable. However, the left and right
n
o
derivatives exist and the above equations imply that max Fij0 (c−) , Fij0 (c+) ≤kt∗i −t∗j k.
is differentiable at c∗, then (53) and the first order optimality condition results in
PIf Fij (c)
0
∗
the estimates of the first 4 cases above, we obtain that
ij∈E Fij (c )=0. Combining this with
X
X
−
kt∗i −t∗j k+
Fij0 (c∗)=0.
(55)
ij∈Eb
ij∈Eg : kt∗i −t∗j k< c1∗
∗
∗
∗
∗
If Fij (c) is not differentiable
P at c , then c = 1/ktk −tl k for some kl ∈ E.
non-differentiable term in ij∈E Fij (c). The combination of the 5 cases above

Thus, Fkl (c) is the only
and the second inequality

of (54) yield
X

−

ij∈Eg \kl:

kt∗i −t∗j k+

kt∗i −t∗j k< c1∗

X

Fij0 (c∗)+Fkl0 (c∗+)≥0.

(56)

ij∈Eb \kl
that |Fkl0 (c+)| ≤ kt∗k −t∗l k

The above estimates for the 5 cases also imply
and |Fij0 (c)| ≤ kt∗i −t∗j k for
ij ∈Eb \kl. CombiningX
this observation with X
(56) results in the estimateX
∗
∗
Fij0 (c∗)+Fkl0 (c∗+)≤
kt∗i −t∗j k.
(57)
kti −tj k≤
ij∈Eg \kl: kt∗i −t∗j k< c1∗

ij∈Eb ∪kl

ij∈Eb \kl

Since (55) is stronger than (57), we use the weaker result (57) to obtain the following inequality:
X
X
X
kt∗i −t∗j k=
kt∗i −t∗j k+
kt∗i −t∗j k
ij∈E: kt∗i −t∗j k< c1∗

ij∈Eg \kl: kt∗i −t∗j k< c1∗

X

≤

X

kt∗i −t∗j k+

ij∈Eb ∪kl

ij∈Eb ∪kl: kt∗i −t∗j k< c1∗

kt∗i −t∗j k≤2

X

(kt∗i k+kt∗j k).bn2 ·maxkt∗i k. (58)

ij∈Eb ∪kl

ij∈Eb ∪kl

By the second property of Lemma 18 of [11]
pand its proof,
∗
maxkti k. logn w.p. 1−O(n−6).

i∈[n]

(59)

i∈[n]

This observation and (58) results in (52).
Using (52), we prove Lemma 5 and 6 in Sections 5.3.1 and 5.3.2 respectively.
5.3.1

Proof of Lemma 5

We assume on the contrary that 1/c∗ > M and use this assumption to derive an inequality for the
random variables
(60)
Yij =I(ij ∈E and kt∗i −t∗j k<1/c∗)·kt∗i −t∗j k for fixed i∈[n] and j ∈[n]\{i}.
This inequality uses the constant µ0 =inf kxk<5E[I(kx−yk<1/c∗)·kx−yk, where y ∼N(0,I), and is
formulated as follows:
X X
1 2
n2p7/3
n pµ0 .
Yij .
w.p. 1−O(n−6).
(61)
4
2
log
n
i∈[n]: j∈[n]\{i}
kt∗ k<5
i

We note that (61) results in contradiction w.p. 1−O(n−6) and thus concludes the proof. Indeed, it
implies that with this probability µ0 .p4/3/log4n→0 as n→∞. Since µ0 is monotonically increasing
as a function of 1/c∗, 1/c∗ →0 as n→∞, which contradicts our assumption.
The rest of this section proves (61) under the assumption that 1/c∗ > M. We first establish the
second inequality of (61) asX
follows.
note that
XWe firstX
X
X
Yij ≤
Yij =2
Yij .
(62)
i∈[n]:
kt∗ k<5
i

j∈[n]\{i}

i∈[n] j∈[n]\{i}

ij∈E(Kn )

Subsequently applying (62), the definition of Yij , (52) and the assumption of Theorem 4 that
b =O(p7/3/log9/2n), we obtain that
X X
X
p
n2p7/3
Yij ≤2
kt∗i −t∗j k.bn2 logn.
.
(63)
log4n
1
∗
∗
i∈[n]: j∈[n]\{i}
kt∗ k<5
i

ij∈E: kti −tj k< c∗

To prove the first inequality of (61), we introduce the following notation: Fix i ∈ [n] and assume that kt∗i k < 5. Assume further that t∗1,...,t∗n are i.i.d. N(0,I) and let Yij be defined in (60),
14

P
Ȳi = j∈[n]\{i} Yij /(n−1) and µi = E(Ȳi) = p·E[I(kt∗i −t∗j k < 1/c∗)·kt∗i −t∗j k)]. Applying Hoeffding’s
inequality to {Yij }j∈[n]\{i}
!
1
µ2i n
Ȳi ≥ µi w.p. 1−2·exp −
.
(64)
2
2·max{Yij2}
Since µi is monotonically increasing with respect to 1/c∗, the assumption that 1/c∗ >M implies that
µi =Ω(1). Combining this observation with (64) and the definitions of µ!
i and µ0 results in
1
1
n
.
(65)
Ȳi ≥ µi ≥ µ0p w.p. 1−2·exp −
2
2
2·max{Yij2}
∗
Using the definition of Ȳi, we rewrite (65) as follows: For fixed i∈[n] with
! kti k<5
X
n
Yij &npµ0 w.p. 1−2·exp −
.
(66)
2·max{Yij2}
j∈[n]\{i}

A union bound of (66) over all i∈[n] with kt∗i k<5 has the following form:
X
X
X X
I(kt∗i k<5)·npµ0
npµ0 =
Yij &
i∈[n]:
kt∗ k<5
i

j∈[n]\{i}

i∈[n]:
kt∗ k<5
i

i∈[n]

w.p. 1−2

X

!
n
I(kt∗i k<5)·exp −
. (67)
2·max{Yij2}

i∈[n]

In order to conclude the first inequality of (61) from (66), we first note that the application of (46) yields
n
X
I(kt∗i k<5)>n/2 w.p. 1−2·exp(−Ω(n)),
(68)
i=1

and the application of basic inequalities and (59) implies that
p for all ij ∈E
∗
∗
∗
0≤Yij ≤max{kti −tj k}≤2·max{kti k}. logn w.p. 1−O(n−6).
ij∈E

(69)

i∈[n]

Lemma 5 is concluded by applying (68) and (69) in order to simplify (67) as follows:

 n 
X X
1
Yij & n2pµ0 w.p. 1−n·exp −Ω
−2·exp(−Ω(n))−O(n−6).
2
logn
i∈[n]:
kt∗ k<5
i

5.3.2

j∈[n]\{i}

Proof of Lemma 6

To prove the lemma, it suffices to verify w.p. 1−O(n−6) that
X
1
n
kt∗i −t∗j k& ∗ ·npg(c∗)· .
2c
2
1
∗
∗

(70)

ij∈E: kti −tj k< c∗

Indeed, Lemma 6 clearly follows by combining (52) and (70).
We first bound from below the LHS of (70) by a sum of random variables, which we define as follows.
We arbitrarily fix i ∈ [n] such that kt∗i k < 5 and for all j ∈ [n]\{i} let Zij = I(ij ∈ E and 1/(2c∗) <
kt∗i −t∗j k<1/c∗). We note that
X
X
X
1 X
kt∗i −t∗j k≥
kt∗i −t∗j k=
kt∗i −t∗j k
2
1
∗
∗
i∈[n]:
ij∈E: kt∗ k<5
j∈N(t∗ ):
ij∈E: kti −tj k< c∗

i
1 <kt∗ −t∗ k< 1
i
j
2c∗
c∗

=

1 X
2 i∈[n]:

kt∗ k<5
i

X

kt∗ k<5
i

i
1 <kt∗ −t∗ k< 1
i
j
2c∗
c∗

1 1 X
Zij kt∗i −t∗j k≥ · ∗
2 2c i∈[n]:

j∈[n]\{i}

kt∗ k<5
i

X

Zij .

(71)

j∈[n]\{i}

It remains to bound the RHS of (71) by the RHS of (70) with high probability and conclude the proof.
For this purpose, we introduce the following auxiliary function, which usesZthe random variable y ∼N(0,I),
n 1
1 o
h(c∗)= inf Pr
<kx−yk<
= inf
Φ(t)dt.
(72)
2c∗
c∗
kxk<5
kxk<5
B(x, c1∗ )\B(x, 2c1∗ )

15

In a somewhat similar way to establishing (50), we note that there exists x0 ∈R3 with kx0k=5, such that
 1 
1
∗
C1Vol
≤h(c
)≤C
Vol
w.p. 1−O(n−6),
(73)
2
2c∗
c∗
where C1 =inf kx−x0k<M Φ(x), C2 =supkx−x0k<M Φ(x). Thus, equation (50) and (73) imply that
1
(74)
g(c∗)≈h(c∗)≈ ∗3 w.p. 1−O(n−6).
c ∗
We further note that Zij ∼B(1,µ
X i), where µi ≥ph(c ). Combining this observation with (46) yields that
Zij &nph(c∗) w.p. 1−2·exp(−Ω(nph(c∗))).
(75)
j∈[n]\{i}

We conclude the proof of (70) as follows. By first applying a union bound for (75) over all i such
that kt∗i k<5, and then applying both (74) and (68), we obtain that
X X
n
(76)
Zij &nph(c∗)·|{i:kt∗i k<5}|&npg(c∗)·
2
i∈[n]:
kt∗ k<5
i

j∈[n]\{i}

with probability
P1 = 1 − n · exp(−Ω(npg(c∗))) − 2 · exp(−Ω(n)) − O(n−6). The assumptions
p
√
p = Ω( 3 logn/n) and g(c∗) & 1/ n imply that Ω(npg(c∗)) & Ω(n1/6 log1/3 n). Thus, P1 = 1−O(n−6).
Equation (70) and thus the lemma clearly follows from combining (71) and (76).

A

Appendix: On the Uniqueness of LUD

In this section we show that under the HLV model with |Eb|>0, the solution of LUD is unique with overwhelming probability. To rigorously formulate the problem, we introduce the notion of self-consistency
of a set of vectors in S 2 and show that uniqueness of LUD is equivalent with non-self-consistency of the
pairwise directions. We then easily note that the pairwise directions in our setting are non-self-consistent
with overwhelming probability.
The definition of self-consistency and an equivalent property, whose proof is straightforward, are
formulated as follows.
Definition A.1 (Self-consistency). Let E be a set of pairs of indices and let n be the minimal integer such
that E ⊆[n]×[n]. A set of vectors {γij }ij∈E ∈S 2 is self-consistent if there exist t1,...,tn ⊂R3 that are not
all identical such that (ti −tj )=kti −tj kγij for each ij ∈E. Otherwise {γij }ij∈E is non-self-consistent.
Proposition A.2. Assume a set E of pairs of indices and let n be the minimal integer such that
2
E ⊆ [n]×[n]. A set of pairwise directions {γij }P
ij∈E ∈ S is self-consistent if and only if there exist
3
t1,...,tn ⊂R that are not all identical such that ij∈E fij (ti,tj )=0.
The following theorem reveals the equivalence of non-self-consistency and the uniqueness of LUD.
Theorem A.3. If G(V,E) is a parallel rigid graph, then the solution of LUD with respect to G(V,E)
is unique if and only if the pairwise directions {γij }ij∈E are non-self-consistent.
Proof of Theorem A.3. Assume that {γij }ij∈E is self-consistent, so there exists a set of vertices
V ={ti}ni=1 such that γij =(ti −tj )/kti −tj k for each ij ∈E. Note that for t̂i =ti and αˆij =kti −tj k≥1,
t̂i − t̂j − αˆij γij = 0. Therefore, {cti}ni=1 with any c ≥ 1/minE kti −tj k solves (3) and thus the solution
of (3) is not unique.
Assume on the contrary that {γij }ij∈E is non-self-consistent. We will show that any two solutions
0 }
λ
0
({t̂i}ni=1, {α̂ij }ij∈E ) and ({t0i}ni=1, {αij
ij∈E ) of (2) are the same. For 0≤λ≤1, define ti =(1−λ)t̂i +λti
λ =(1−λ)α̂ +λα0 . We note that since (2) is a convex optimization problem, for any 0≤λ≤1,
and αij
ij
ij
λ
n
λ
({ti }i=1, {αij }ij∈E ) is also a solution of (2). Therefore, the objective function evaluated at the
P
λ}
λ
λ
λ
solution ({tλi}ni=1, {αij
ij∈E ), namely F (λ)=
ij∈E kti −tj −αij γij k, is constant on [0,1]. We denote
0 γ and rewrite F (λ) as
êij = t̂i −t̂j − α̂ij γij and e0ij =t0i −t0j −αij
ij
X
Xq
0
F (λ)=
kêij +λ(eij −êij )k=
ke0ij −êij k2λ2 +2λêTij (e0ij −êij )+kêij k2.
ij∈E

ij∈E

16

Since F is constant, this equation implies that êij =e0ij for all ij ∈E. That is,
0
t̂i −t̂j − α̂ij γij =t0i −t0j −αij
γij for ij ∈E.
(77)
0
0
Let ∆ti = t̂i −ti for i∈[n] and ∆αij = α̂ij −αij for ij ∈E. We rewrite (77) as
∆ti −∆tj =∆αij γij for ij ∈E.
(78)
Since kγij k=1, (78) implies that
∆ti −∆tj =k∆ti −∆tj kγij for ij ∈E.
(79)
The non-self-consistency of {γij }ij∈E implies that the elements of the solution {∆ti}ni=1 of (79) are
P
all identical. Consequently, for all i ∈ [n], t̂i −t0i is a constant vector in R3. The constraint i ti = 0
of (3) implies that the constant vector is zero and thus the solution is unique.
We remark that under the HLV model with |Eb|6= 0, the non-self-consistency is a necessary condition
for exact recovery. Indeed, assume that V ={ti}ni=1, G(V,E) and {γij }ij∈E were generated by the HLV
model with |Eb|6= 0 and that {γij }ij∈E is self-consistent. Since {γij }ij∈E is self-consistent, it is a set
of true pairwise directions of a graph G0(V 0,E). Furthermore, since |Eb|6= 0, V 0 =
6 V and V cannot be
obtained from V 0 by scaling and shifting. That is, LUD outputs V 0 and cannot recover V .
Proposition A.5 below guarantees with high probability the non-self-consistency of {γij }ij∈E , while
assuming the setting of Theorem 1. One can note that its probability is significantly larger than the
one of Theorem 1. This proposition thus implies with overwhelming probability the uniqueness of LUD
and consequently the well-posedness of exact recovery by LUD. The proof of this result depends on
Lemma A.4 below, which demonstrates a necessary condition for self-consistency. Before proceeding
with the proof, we introduce the following notation.
Assume that V ={ti}ni=1, G(V,E) and {γij }ij∈E were generated by the HLV model with |Eb| =
6 0,
where {γij }ij∈E is self-consistent. As clarified above, {γij }ij∈E is the set of true pairwise directions of a
graph G0(V 0,E), where V 0 ={t0i}ni=1 =
6 V and V cannot be obtained from V 0 by scaling and shifting. One
0
may view V as perturbed vertices of V , even though the actual perturbation is of {γij }ij∈E . For S ⊂[n],
denote V (S)={ti}i∈S , V 0(S)={t0i}i∈S and E(S)={ij ∈E :i,j ∈S}. For Ẽ ⊆E, let deg(i,Ẽ) denote the
degree of node i in the subgraph G(V,Ẽ). We say that i, j ∈[n] are undeformed and denote it by i∼j,
if i6= j and ∃ κ>0 such that ti −tj =κ(t0i −t0j ). Otherwise, we say that i and j are deformed and denote
ij. Note that by definition ii. For each i∈[n], we define the undeformed set Si ={j ∈[n]:j ∼i}.
Lemma A.4. Assume that V ={ti}ni=1, G(V,E) and {γij }ij∈E were generated by the HLV model. If
{γij }ij∈E is self-consistent and |Eb|6= 0, then there exists j ∈[n] such that |Sj |<n/2.
Proof. Assume on the contrary that for all j ∈[n], |Sj |≥n/2. Since |Eb|6= 0 and G(V,E) is parallel rigid
(as assumed by the HLV model), there exists k,l ∈[n] such that k l, which implies that {k,l}∩(Sk ∪Sl )=
∅ and |Sk ∪Sl | ≤ n−2. Consequently, |Sk ∩Sl | = |Sk |+|Sl |−|Sk ∪Sl | ≥ n/2+n/2−(n−2) = 2. Denote
by a and b two of the elements of Sk ∩Sl and note that by definition of the undeformed sets Sk and Sl ,
a∼k, b∼k, a∼l and b∼l. Due to the HLV model, the probability that {ak,bk,al,bl} lies on a plane
in R3 is zero and thus the graph G(V ({a,b,k,l}),{ak,bk,al,bl}) is parallel rigid in R3 [18, Figure 4(d)].
Therefore, V ({a,b,k,l})=V 0({a,b,k,l}) up to scale and shift and k ∼l, which results in contradiction.
Proposition A.5. In the setting of Theorem 1, if |Eb|6= 0, then {γij }ij∈E is non-self-consistent with
probability 1−exp(−Ω(n2/3log1/3n)).
Proof. Assume on the contrary that {γij }ij∈E is self-consistent. By Lemma A.4, there exists j ∈[n] such
that |Sj |<n/2. Note that deg(j,Eb)=deg(j,E(Sjc)). Therefore, nb =maxi∈[n]deg(i,Eb)≥deg(j,E(Sjc)).
For each i∈Sjc \{j}, I(ij ∈E(Sjc)) is a Bernoulli random variable B(1,p). Thus, by applying (46) with
δ =1/2, µ=p and the number of terms |Sjc|−1=n−|Sj |−1>n/2−1, we obtain that
X
 1 n
1 n
I ij ∈E(Sjc) > ·( −1)p w.p. 1−2e− 12 ( 2 −1)p.
(80)
deg(j,E(Sjc))=
2 2
c
i∈Sj \{j}

Combining the assumption p = Ω(n−1/3 log1/3 n) with (80) implies that nb ≥ deg(j,E(Sjc)) = Ω(np)
with probability 1 − 2 · exp(−Ω(n2/3 log1/3 n). This contradicts the assumption of Theorem 1 that
nb =O(np7/3/log9/2n).

17

References
[1] M. Arie-Nachimson, S. Z. Kovalsky, I. Kemelmacher-Shlizerman, A. Singer, and R. Basri. Global
motion estimation from point matches. In 2012 Second International Conference on 3D Imaging,
Modeling, Processing, Visualization & Transmission, Zurich, Switzerland, October 13-15, 2012,
pages 81–88, 2012.
[2] M. Brand, M. E. Antone, and S. J. Teller. Spectral solution of large-scale extrinsic camera
calibration as a graph embedding problem. In Computer Vision - ECCV 2004, 8th European
Conference on Computer Vision, Prague, Czech Republic, May 11-14, 2004. Proceedings, Part
II, pages 262–273, 2004.
[3] E. J. Candès, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? J. ACM,
58(3):11:1–11:37, 2011.
[4] E. J. Candès and T. Tao. Decoding by linear programming. IEEE Trans. Information Theory,
51(12):4203–4215, 2005.
[5] V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky. Rank-sparsity incoherence
for matrix decomposition. SIAM Journal on Optimization, 21(2):572–596, 2011.
[6] A. Chatterjee and V. M. Govindu. Efficient and robust large-scale rotation averaging. In IEEE
International Conference on Computer Vision, ICCV 2013, Sydney, Australia, December 1-8,
2013, pages 521–528, 2013.
[7] M. Coudron and G. Lerman. On the sample complexity of robust PCA. In Advances in Neural
Information Processing Systems 25: 26th Annual Conference on Neural Information Processing
Systems 2012. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United
States., pages 3230–3238, 2012.
[8] T. Goldstein, P. Hand, C. Lee, V. Voroninski, and S. Soatto. Shapefit and shapekick for robust,
scalable structure from motion. In Computer Vision - ECCV 2016 - 14th European Conference,
Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part VII, pages 289–304, 2016.
[9] V. M. Govindu. Combining two-view constraints for motion estimation. In 2001 IEEE Computer
Society Conference on Computer Vision and Pattern Recognition (CVPR 2001), 8-14 December
2001, Kauai, HI, USA, pages 218–225, 2001.
[10] V. M. Govindu. Lie-algebraic averaging for globally consistent motion estimation. In 2004 IEEE
Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2004), 27
June - 2 July 2004, Washington, DC, USA, pages 684–691, 2004.
[11] P. Hand, C. Lee, and V. Voroninski. Shapefit: Exact location recovery from corrupted pairwise
directions. CoRR, abs/1506.01437, 2015.
[12] A. Harltey and A. Zisserman. Multiple view geometry in computer vision (2. ed.). Cambridge
University Press, 2006.
[13] R. I. Hartley, K. Aftab, and J. Trumpf. L1 rotation averaging using the weiszfeld algorithm. In
The 24th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011, Colorado
Springs, CO, USA, 20-25 June 2011, pages 3041–3048, 2011.
[14] G. Lerman, M. B. McCoy, J. A. Tropp, and T. Zhang. Robust computation of linear models
by convex relaxation. Foundations of Computational Mathematics, 15(2):363–410, 2015.
[15] D. Martinec and T. Pajdla. Robust rotation and translation estimation in multiview reconstruction.
In 2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR
2007), 18-23 June 2007, Minneapolis, Minnesota, USA, 2007.

18

[16] P. Moulon, P. Monasse, and R. Marlet. Global fusion of relative motions for robust, accurate
and scalable structure from motion. In IEEE International Conference on Computer Vision, ICCV
2013, Sydney, Australia, December 1-8, 2013, pages 3248–3255, 2013.
[17] O. Özyesil and A. Singer. Robust camera location estimation by convex programming. In IEEE
Conference on Computer Vision and Pattern Recognition, CVPR 2015, Boston, MA, USA, June
7-12, 2015, pages 2674–2683, 2015.
[18] O. Özyesil, A. Singer, and R. Basri. Stable camera motion estimation using convex programming.
SIAM Journal on Imaging Sciences, 8(2):1220–1262, 2015.
[19] O. Özyesil, V. Voroninski, R. Basri, and A. Singer. A survey of structure from motion. Acta
Numerica, 26:305364, 2017.
[20] P. Ravikumar, M. J. Wainwright, G. Raskutti, and B. Yu. High-dimensional covariance estimation
by minimizing `1-penalized log-determinant divergence. Electron. J. Statist., 5:935–980, 2011.
[21] S. Sengupta, T. Amir, M. Galun, T. Goldstein, D. W. Jacobs, A. Singer, and R. Basri. A new rank
constraint on multi-view fundamental matrices, and its application to camera location recovery.
IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, Hawaii,
USA, June 22-25, 2017, pages 4798–4806, 2017.
[22] R. Tron and R. Vidal. Distributed image-based 3-d localization of camera sensor networks. In
Proceedings of the 48th IEEE Conference on Decision and Control, CDC 2009, December 16-18,
2009, Shanghai, China, pages 901–908, 2009.
[23] R. Tron and R. Vidal. Distributed 3-d localization of camera sensor networks from 2-d image
measurements. IEEE Trans. Automat. Contr., 59(12):3325–3340, 2014.
[24] H. Xu, C. Caramanis, and S. Sanghavi. Robust PCA via outlier pursuit. IEEE Trans. Information
Theory, 58(5):3047–3064, 2012.
[25] T. Zhang and G. Lerman. A novel M-estimator for robust PCA. Journal of Machine Learning
Research, 15(1):749–808, 2014.

19

