Hi, I have a complex-valued vector X in C^n. Given another complex-valued vector Y in C^n, I want to find a permutation of Y, say, Y*, that minimizes ||X - Y*||, the distance between X and Y*.
Note that this problem can be trivially solved for "Real" vectors, since real numbers possess the ordering property. Complex numbers, however, do not possess this property. Hence the challenge. The obvious solution is to enumerate all the permutations of Y and pick out the one that yields the smallest distance. This, however, is only feasible for small n. I would like to be able to solve this for n as large as 100 - 1000, in which cases the permutation approach is infeasible. I am looking for algorithms, possibly iterative, that can provide a "good" approximate solutions that are not necessarily optimal for high-dimensional vectors. I can do random sampling, but this can be very inefficient in high-dimensional problems. I am looking for efficient algorithms because this step has to be performed in each iteration of an "outer" algorithm. Are there any clever adaptive algorithms out there? Here is an example illustrating the problem: require(e1071) n <- 8 x <- runif(n) + 1i * runif(n) y <- runif(n) + 1i * runif(n) dist <- function(x, y) sqrt(sum(Mod(x - y)^2)) perms <- permutations(n) dim(perms) # [1] 40320 8 tmp <- apply(perms, 1, function(ord) dist(x, y[ord])) z <- y[perms[which.min(tmp), ]] # exact solution dist(x, z) # an aproximate random-sampling approach nsamp <- 10000 perms <- t(replicate(nsamp, sample(1:n, size=n, replace=FALSE))) tmp <- apply(perms, 1, function(ord) dist(x, y[ord])) z.app <- y[perms[which.min(tmp), ]] # approximate solution dist(x, z.app) Thanks for any help. Best, Ravi. ____________________________________________________________________ Ravi Varadhan, Ph.D. Assistant Professor, Division of Geriatric Medicine and Gerontology School of Medicine Johns Hopkins University Ph. (410) 502-2619 email: rvarad...@jhmi.edu ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
