Filetype PDF | Posted on 25 Jan 2023 | 3 years ago
Authentication
digital resources
273x Filetype PDF File size 0.40 MB Source: users.cecs.anu.edu.au
Efficient Reduction of L-infinity Geometry Problems
HongdongLi
Research School of Information Sciences and Engineering
Australian National University and NICTA
hongdong.li@anu.edu.au
Abstract (binary search) procedure. But, convexoptimization is any-
wayanexpensivecomputation. Modern convexoptimizers
This paper presents a new method for computing optimal L are mostly based on the Interior-Point-Algorithm, which
∞
solutions for vision geometry problems, particularly for those is known to be polynomial algorithm, meaning that the
problems of fixed-dimension and of large-scale. Our strategy for required computation grows polynomially in the size of the
solving a large L problemistoreduceittoafinitesetofsmallest problem (i.e. number of constraints and variables). A high
∞
possible subproblems. By using the fact that many of the problems polynomial degree often prevents it from handling too big
in question are pseudoconvex, we prove that such a reduction is problems,or its speed is unbearably slow.
possible. To actually solve these small subproblems efficiently, we
propose a direct approach which makes no use of any convex op- To accelerate the L∞ computation, researchers have ex-
timizer (e.g. SOCP or LP), but is based on a simple local Newton ploredvariousways. However,mostofthemhavebeencon-
method. We give both theoretic justification and experimental val- centrated either on how to speedup the convex solver itself,
idation to the new method. Potentially, our new method can be or on how to reduce the total number of convex program
madeextremely fast. iterations (e.g.,[5][2]).
As a consequence, despite having all those improve-
ments, their methods still have to solve a full-size convex
1. Introduction program using a full-scale convex optimizer at every itera-
The L optimization is a rather new and promising di- tions. Since convexoptimizerhasstillpolynomialcomplex-
∞ ity, also may come with a high memory (storage) require-
rection of research in multi-view geometry [4, 5, 6]. In just
afewyears’timeithasattractedmuchattentionfromthevi- ment, it may not be capable of handling very large-scale
sion geometrycommunity(seee.g.[12,17,9,14,2,7,15]). problems.
AcriticalvirtueoftheL schemeisthatthesolutionob- The goal of this paper is to develop a new method to
∞ speed up the L computation, particularly for those large-
tained is not only geometrically meaningful, but also glob- ∞
ally optimal and hence unique. The unique solution can al- scale applications. We will present a new approach that ef-
waysbereliablyfound,regardlessofthesizeoftheproblem fectively solves an L∞ problemwithout solvinganyconvex
and the configurations of the cameras. This forms a sharp program. Ourmethodisnotonlytheoreticallyprovable,but
contrast to the conventional L method, which is known to also practically efficient. Potentially, it can be easily made
2 extremely fast.
be problematic due to local minima or slow convergency.
This virtue entails the L∞ scheme particularly suitable 2. Related work
for large-scale applications. In these applications, there are
often e.g. thousands of views to be triangulated, or thou- In an early work on L∞ vision computation [5], Kahl
sands of points to be fit to a model. Paper [19] gives some formulated the problem as quasi-convex program, and pro-
instancesoflargeproblems,oneofwhich,the‘NotreDame’ posed an Improved Bisection method based on the idea of
data set, involves solving for 595 cameras and 277,887 3D updating the upper-bound adaptively, thus effectively re-
points. duces the total number of SOCP iterations. This way, con-
However,to process large-scaledata using L∞ there is a siderable time reduction was observed.
computationalcomplexity issue. The standard approach for Arecentpaper[2],alsoaimingatreducingthetotalnum-
solving an L∞ problem is to convert it into a sequence of ber of iterations, has gained remarkable success. Based
convexprograms(e.g. SOCP, second-order cone program), on fractional programming, it introduced five algorithms
and iteratively solves many such SOCPs via a bisection (e.g. Dinkelbach algorithm, Gugat algorithm, etc.) to vi-
1
sion community. The common idea is: instead of doing Our method follows from the reduction (or decompo-
a naive binary search (bisection) which has linear conver- sition) strategy, which performs by reducing a big original
gence, it uses Newton method to cut-downthe total number probleminto a set of small-size subproblems. We call these
of SOCPs significantly. small subproblems as atom or primitive problems. Each of
Olsson et al. [12] realized that many L∞ functions in the atomproblemsissosmallthatapplyingafull-scalecon-
vision are in fact pseudoconvex (which is slightly stronger vex solver is often unnecessary. Rather, more direct and
than quasi-convex). They proposed two fast algorithms. more efficient methods (e.g. analytic) may exist and may
The first one is based on local search using LOQO, but sufficeforsolvingthem. Thisway,weavoidtheuseofcon-
for large applications it suffers from numerical convergence vexoptimizer.
problem. The second one is via SOCP approximation, and To be able to apply the above strategy, it is crucial to
lately was shown to be a special case of Dinkelbach algo- show that the L∞ problems are indeed “reducible”. To
rithm. Our work is significantly motivated by the concept this end, we will establish our main reduction theorem
of pseudoconvexity. in section-5. The theorem is substantially grounded on
Thenewmethod,to bepresentedin this paper, is rooted the pseudoconvexity theory–which will be reviewed in
fromthemathematicaltheoryofLP-typeproblems. Inour section-4.
previous work we introduced the elegant LP-type frame- To actually perform the reduction (i.e. form the origi-
work to multi-view L∞ computation [7]. We have proven nally big problem to a set of small primitive problems), we
that many fixed-dimensionalL∞ geometryproblemsare in present two reduction algorithms in section-7. These al-
fact instances of the so-called LP-type problem [10]. How- gorithmsareefficient, inthe sense thatthey will find the op-
ever, that paper’s focus was on outliers-removal, and no ef- timal solution in linear expected time. Therefore, our new
ficient algorithm was given there. methodis also efficient.
After the completion of the work, a very interesting con- Ourefficiencyargumentalso dependsonthe assumption
nection was brought to our attention, which is that our that, one can solve those primitive problems extremely ef-
method bears a remarkable similarity to the SMO method ficiently. This is often the case, in fact, as the primitive
for fast Support Vector Machine training in the machine problems are usually very tiny and very regular. Section-6
learning field [13]. We note that, while these two meth- is devoted to primitive solvers.
ods advocate the same idea of reducing to the smallest pos- Indeed, as an example, later we will show a 1000-point
sible subproblems, the SMO was designed for the convex L∞planarhomographyproblemcanbereducedto 4-point
(quadratic programming) case, and the actual reduction al- homographyand 5-point homographyproblems etc. Obvi-
gorithms are also different. ously, to estimate an L∞ homography from 4 points one
does not need any sophisticated SOCP; a simple SVD suf-
3. A Preview of the Paper fices.
So far, almost all published works on L∞ vision com- 4. The L Minimization and Pseudoconvexity
∞
putation are based on convex optimization. As mentioned
earlier, being a polynomial-complexity algorithm, the con- To ease exposition, this section will summarize some
vex optimization is expensive, preventing it from handling known results of L∞ in vision computation. Emphasis is
very big problems. given to pseudoconvexityand its implications.
For this reason, most existing wisdom for accelerating The key idea of the L∞ scheme is to replace the L2 er-
large-scale L computation is either through using faster ror norm with the L∞-norm (i.e. minimax norm). Previous
∞
convex solvers, or through reducing the total number of worksshowthatthisleadstoquasi-convexminimization(or
convexprograms. quasi-convex program). We call a function quasi-convex if
all of its sublevel sets are convex. Quasi-convex minimiza-
tion in multi-view geometry often takes the following form
However, since convex-optimization appears to be the ([5]):
bottleneck here, can we avoid it at all? Motivated by this
question, we take a very different angle to attack the prob- kA x+b k
min max f (x) = i i (1)
i T
lem of large-scale L∞ computation. We ask ourselves a x i (c x+di)
i
novel question: is it possible to effectively solve an L T
∞ s:t: c x+di >0;i=1;:::;N; (2)
i
problemwithout solving any convex program ?
Our answer to this question is “yes.” In this paper, we wherethefi(x) are quasi-convex,x ∈ Rn is the unknowns
propose a new method precisely does this: enjoying all the to be solved for. The dimension of the problem is n, which
benefitsofL∞withoutusingany(slowandexpensive)con- is often fixed and intrinsic to particular application. For ex-
vexoptimizer. ample, n = 3 for multi-view triangulation, n = 6 for 2D
affinity, n = 8 for planar homography, n = 7 for funda- This theorem says that, unlike the quasi-convex case, for
mental matrix and n = 11 for camera calibration, etc. The pseudoconvexcase the KKT conditionsare not only neces-
size (scale) of the problemis definedby N. By ‘large-scale’ sary but also sufficient. This actually suggests a local de-
problemswemeanN ≫ningeneral. scent approach for pseudoconvex optimization. Following
Thestandardapproachtosolvesuchaquasi-convexpro- from this, paper [12] made an important attempt in using
gram is to convert it to iteratively solving the following LOQOtosolve L∞ problems. For small problems LOQO
SOCPsviabisection: worked fine, but for large problems it often failed to con-
verge.
min γ (3)
x
T
s:t: C (x) = kA x+b k−γ(c x+d )≤0;i=1;:::;N;
i i i i i Minimax case. Recall that our purpose is to minimize
max f (x); where each f (x) is pseudoconvex. Although
where C (x) represents the i-th second-order cone (shell i i i
i the concept of pseudoconvexitydoes not extend to the min-
only). Note that we have multiplied the chirality condition imaxcase, we howeverhavea significant result as follows:
to both side.
∗ ∗
Theorem4.4(minimaxKKT) x solves γ =
4.1. Useful results of pseudoconvexity min max f (x); i = 1;:::;N; where f (x) is pseudocon-
x i i i
vex, if and only if there exist scalars λ such that
Paper [12] has proven that the above functions f (x) are i
i
in fact pseudoconvex in the feasible region. Pseudoconvex N N
is a slightly stronger condition than quasi-convex. A pseu- Xλ▽f(x∗)=0; Xλ =1; (6)
i i i
doconvexfunction is always quasi-convex but the converse i=1 i=1
is not necessarily true. where λ ≥ 0if f (x∗) = γ∗;λ = 0 if f (x∗) < γ∗:
i i i i
Definition 4.1 A function f is called pseudoconvex if it is ∗
This theorem says that: at the optimum point x of γ, in
¯ ¯ ¯
differentiable and ▽f(x)(x−x) ≥ 0implies f(x) ≥ f(x), each direction (denoted by θ) there must be an ‘i’ such that
where ▽ denotes gradient operator [8]. ∗
▽fi(x )· θ ≥0. Geometrically, this means that in each di-
rection there is at least one residual non-decreasing. Proofs
Pseudoconvexity is very useful in minimization. Infor- of all the above results can be found in [8, 12].
mally speaking, a local stationary point of a pseudoconvex
functionis also its global minimum. To find the global min- 5. Main Reduction Theorem
imumitissufficienttofindalocalstationarypoint,andthis
can be done sufficiently by solving a KKT system of the We have seen that pseudoconvexity is useful in deriv-
problem,as assured by the following two results. ing optimization procedures. In this section, we will further
showthatit actually offers more.
Lemma4.2 Given a pseudoconvex function f, then we Recall that our intended strategy for solving a big prob-
¯ ¯
have▽f(x) = 0 if and only if f(x) ≥ f(x) for all x. lemofsize N(c.f. Eq.3)is to reduce it to a single or a set of
This lemma says that any local stationary point of a pseu- small primitive problems, each of which is of size k ≪N.
doconvexfunction is also its global minimum. Byusingpseudoconvexity,we will show this is indeed pos-
sible, thanks to the Main Reduction Theorem to be given
Theorem4.3(KKTsufficientcondition[8]) Consider a below.
general inequality-constrainedminimization problem: Before presenting the theorem, we first point to a useful
empirical observation, which offers insight to the theorem.
minf(x); s:t: gi(x) ≤ 0;i = 1;:::;N (4) Many authors have observed that, the L∞ optimum is
x actually only supported by a small subset of the entire
x inaconvex set: constraints set. This empirical ‘fact’ was applied to L
∞
¯ computations (e.g. [18, 15, 7]). But neither of them has
Let x be a feasible solution. Suppose its KKT system holds
true at x¯, i.e., there exist scalars λ ≥ 0 such that offeredsufficientjustification, nor answered a key question:
i
“how big size that subset should be, and how to quickly
▽f(x¯)+Xλi▽gi(x¯) = 0: (5) findit?”.
i
Suppose further that f(x) and gi(x) are pseudoconvex, 5.1. The Main Theorem
then the point x¯ which solves the KKT system is precisely
the global optimum. Wenowstatethemainreductiontheorem.
Theorem5.1(mainreductiontheorem) Suppose by using our reduction algorithms (to be given
Consider L problem min max f (x), where x ∈ in the next section) we have reduced a big N-view problem
∞ x i i
Rn; i = 1;:::;N, N > (n + 1), each fi(x) is pseudocon- into a small set of k-view (k ≤ 4) primitive problems. Be-
vex. Denote f (x) = max f (x); where I is a subset of cause the primitive problems are so small that one is able
I i∈I i
N = {1;:::;N}: Also denote f∗ as the minimum of f (x): to solve them directly, efficiently, or even in closed-form.
I I
Then there must exist a proper subset B which is of size Nowletusshowthis.
∗ ∗ ∗ ∗
|B| ≤ n + 1 such that f = f and x = x are their
B N B N 2-viewcase. It is easy to imagine(viageometricintuition)
(equal) optimizers. that, solving 2-view L triangulation is equivalent to find-
∞
We call a subset of N a basis set (or basis in short), if ingtwonon-inclusiveconesthataretangentin3-space. The
optimum attains, i.e., the γ values is minimal, when the
this subset yields the same minimal function value and two cones are tangent with the two gradients at the point
if remove any member from it will decrease the function of tangency pointing to opposite directions. This point-of-
value. The maximal size (cardinality) of any basis is called tangency gives the optimal solution. Summarizing this up
the combinatorial dimension. Hence the combinatorial mathematically and we get:
dimensionin the theorem is (n + 1). ( T
C (x) = kA x+b k−γ (c x+d )=0; i =1;2
i i i i i
Aproof of the theorem is given in the Appendix of the λ▽C1(x)+(1−λ)▽C2(x)=0; λ>0;ascalar:
paper. It is adduced in a form most suitable for the purpose. This is almost a system of equations. Having very small
Arelated and neat result, though in a different context, can size, the system can be easily solved by any Newtonmethod
be found in [11]. (e.g. Levenberg-Marquardt). In solving the system, the last
positivity conditioncanberelaxedfirst andreinforcedafter-
This theorem predicts that the solution of the big prob- ward. Alineartriangulationmethodmaybeusedtoprovide
lem is dominated by a small basis set of at most (n + 1) aninitial point. To ensurethat the linear solution is also fea-
constraints. This is very appealing, because solving that sible in terms of chirality, a validation before using it seems
small sub-problem yields identically the same result to the necessary.
original problem. Now the remaining task is to quickly find ThereadermayworrythatthelocalNewtonmethodmay
abasis. not converge globally. The fact is, being pseudoconvex the
If the purposeweremerelytofindabasis,thenonecould problem has only one local minimum, which is also the
easily do it a posteriori, meaning that extracting a basis set global optimum. In addition, because the problem size is so
after having found a solution of the original problem. But tiny and the nonlinearity is so mild that the Newton solver
this is meaningless however, for our current purpose of re- is adequate in practice. Our tests hardly encountered any
duction. We must have an a priori approach that can iden- difficulties, even when the noise level was high.
tify a basis quickly before spending too much time on solv-
ing the original big problem. But how ? 3-view case. The 3-view case is a bit tricky. Now the 3
Our answer to this will be given in section-7, in which cones cannot be tangent in any configuration, otherwise it
wewillpresenttworeductionalgorithms,bothofwhichcan will reduce to the 2-view case, contradict to the fact that
the 3 cones form a basis set. Hence, they must intersect at
findabasisinlinearexpectedtime. In the nextsection (i.e., a common point. Moreover, at that point the three gradi-
section-6), instead, we will explain how to construct primi- ents must cover all feasible directions, otherwise the point
tive solvers. would move therefore not non-optimal, contradict to the
preassumption. Mathematically we have:
6. Solving Primitive Problems
8 T
>C(x)=kAx+bk−γ(c x+d)=0; i=1;:::;3
i i i i i
Inthis section, we will elaborateonhowtoactuallycom- < Xλi▽Ci(x)=0; Xλi=1; λi >0:
pute the primitive problems fast and efficiently, without us- >
ing convex optimizer. We choose to describe our primitive : i i
solvers earlier (before describing the actual reduction algo- 4-view case. The 4-view case, on the other hand, is par-
rithms in the next section), is to assure the reader earlier of ticularly simple. Note that we have totally 4 unknowns to
the possibility of solving L∞ without SOCP. solve, 3 in x and 1 in γ. Now we have precisely 4 cones in
Let us use N-view triangulation as an example to il- the basis set. Hence the solution can be found as a proper
lustrate the possibility to construct ad hoc primitive solvers root of the square system of equalities.
without SOCP. The combinatorial dimension here is 4. T
C (x) = kA x+b k−γ (c x+d )= 0; i = 1;:::;4
Hence only 4 distinct primitive problems exist: 1-view, 2- i i i i i
view, 3-view and 4-view (the 1-view case is trivial). Note There may be multiple roots. However, this is no serious,
that they are all under the L∞ norm. thanks to the use of local solver, and to the fact that we
no reviews yet
Please Login to review.
