Nearest Multiple of a Vector
----------------------------
Are there fast algorithms for computing the multiple of
a vector $b$ nearest to a vector $a$ in the 1-norm
and the max norm,
$\min_\lambda ||a-\lambda b||_1$,
$\min_\lambda ||a-\lambda b||_\inf$,
and the related problem
$\min_\lambda max_i (a_i-\lambda b_i)$ ?
More precisely, I would like to know the corresponding
active sets after $O(n)$ operations, if possible with a
constant independent of the length of the data.
------------------------------------------------
Improvements to the contents of this page are welcome.
Please write me to neum@cma.univie.ac.at
Arnold Neumaier
------------------------------------------------
1. Peter Spellucci (spellucci@mathematik.tu-darmstadt.de) wrote
(but I couldn't translate this into an O(n) algorithm; if you, reader,
can, please write me!):
your functions to be minimized are convex piecewise linear in one
variable \lambda. It suffices therefore the check the "kinks"
(points of nondifferentiability) and this is O(n).
-------------------------------------------------
2. David Stewart (dstewart@math.uiowa.edu) wrote:
I can give an O(n\log n) method for the first problem:
for i = 1, 2, ..., n
if b_i < 0 then
a_i <- -a_i; b_i <- -b_i;
end if
end for
(Ignore any i where b_i = 0.)
Sort the indices so that
a_1/b_1\le a_2/b_2\le a_3/b_3\le ....\le a_n/b_n
(This is the O(n\log n) part.)
[find sign change of derivative]
sum1 <- \sum_{i=1}^n b_i
sum2 <- 0
for i = 1, 2, ..., n
sum1 <- sum1 - b_i
sum2 <- sum2 + b_i
if sum1 < sum2 then
optimum lambda <- a_i/b_i & exit loop
end if
end for
----------------------------------------------
3. Daniel Zwick (zwick@double-star.com) wrote:
Those are certainly interesting problems.
The minmax problem can be converted to 2-variable linear programs of
the form
Minimize y
Subject to y >= +/-(a_i + b_i x) ( i = 1 to n)
and solved by, say, the simplex method. However this would not be O(n). The others can also be converted to 2-varible linear programs.
On the other hand, they are equivalent to Halfspace Intersection,
which is equivalent to Convex Hull, and this can be solved in
O(n log h) time, where in this case h would be the number of vertices
visited in solving the problem. There is a O(n) algorithm for this
problem, by N. Megiddo, but I don't know anyone who has actually
programmed it. He proved that a linear program in two variables
(actually, fixed dimension) and n constraints can be solved in
optimal O(n) time. There is a nice discussion of this with an
indication of how it might be programmed in the book
"Computational Geometry" by Preparata and Shamos (around p.292).
The book of Preparata and Shamos doesn't contain the latest references
on these type of problems. There are papers that reduce the constant
(subexponential bounds in the dimension d), and some papers on
randomized algorithms for the same lp problem. Unfortunately I don't
have all of these references, but I would start by searching for
papers by G=E4rtner, Welzl, Sharir, and Clarkson (and combinations
thereof). Dyer has (at least) two papers on Megiddo's technique, the one
mentioned in Preparata and Shamos, SIAM J Comp 13 (1984), p. 33 and
another one in SIAM J Comp 15 (1986), p. 725. It's still Megiddo's
O(n) algorithm but with minor improvements.
-------------------------------------------------
I followed this up. The O(n) method is based on an O(n) method for
finding the median, but checking on median algorithms, I noticed that
apparently no one is using O(n) median algorithms since the factor
hidden in the Landau symbol seems to be so large that simpler
O(n log n) median methods are faster in practice, even for large n.
This suggests that for practical purposes, one should be content in
the above problems with O(n log n) algorithms.
But it also suggests that there is further scope for research.
Along the way I found some interesting WWW pages and references
that might be useful:
http://graphics.lcs.mit.edu/~seth/geomlib/geomlib.html
[lp, Mike Hohmeyer's C implementation of Raimund Seidel's O(d! n) time
linear programming algorithm]
http://www.geom.umn.edu/software/cglist/lp.html
Low-dimensional linear programming codes
[_expected_ O(n)]
http://cm.bell-labs.com/cm/cs/who/clarkson/lp2.html
K. L.Clarkson. Las Vegas algorithms for linear and integer programming
when the dimension is small. Journal of the ACM, 42(2):488--499, 1995.
[with source code that is _expected_ O(n)]
http://www.maths.mu.oz.au/~worms/digest/lp.html
[Recently, Gil Kalai and (independently) Matousek, Sharir, and Welzl
have developed a randomized "subexponential" pivot rule for the
simplex method.]
http://www.cs.sunysb.edu/~algorith/implement/linprog/implement.shtml
http://www.inf.ethz.ch/personal/gaertner/
Bernd Gärtner
http://www.inf.fu-berlin.de/inst/theo/mitarbeiter/welzl.html
Emo Welzl
D. Eppstein,
Dynamic three-dimensional linear programming,
ORSA J. Comput. 4 (1992), 360--368.
R. Seidel,
Small-dimensional linear programming and convex hulls made easy,
Discrete Comput. Geom. 6 (1991), 423--434.