Hi Klaus,
This problem can be cast as a linear sum assignment problem (LSAP), and solved
using the `solve_LSAP' function in the "clue" package. I show how to solve a
slightly more general problem of finding a permulation of matrix A (n x n) that
minimizes the Frobenius distance to a given matrix B (n x n). In your case, B
= I. I ran this for n up to 100. It seems to be quite fast.
Here is how you do this:
dist <- function(A, B) {
# Frobenius norm of A - B
n <- nrow(A)
sum(abs(B - A))
}
pMatrix.min <- function(A, B) {
# finds the permutation P of A such that ||PA - B|| is minimum
# in Frobenius norm
# Uses the linear-sum assignment problem (LSAP) solver
# in the "clue" package
# Returns P%*%A and the permutation vector `pvec' such that
# A[pvec, ] is the permutation of A closest to B
n <- nrow(A)
D <- matrix(NA, n, n)
for (i in 1:n) {
for (j in 1:n) {
D[j, i] <- sum(abs(B[j, ] - A[i, ]))
} }
vec <- c(solve_LSAP(D))
list(A=A[vec,], pvec=vec)
}
#set.seed(123)
# Find P such that ||PA - I|| is minimum
n <- 100
A <- matrix(rnorm(n*n), n, n)
dist(A, diag(n))
B <- pMatrix.min(A, diag(n))$A # B = P%*%A
dist(B, diag(n))
# Find P such that ||PA - C|| is minimum
C <- matrix(rnorm(n*n), n, n)
B <- pMatrix.min(A, C)$A
dist(A, C)
dist(B, C)
Let me know how this works for you.
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
----- Original Message -----
From: klau...@gmx.de
Date: Friday, January 15, 2010 9:53 am
Subject: [R] optimization problem
To: r-help@r-project.org
> Dear R-experts,
>
> this is not a direct R-problem but I hope you can help me anyway.
>
> I would like to minimize || PG-I || over P, where P is a p x p
> permutation matrix (obtained by permuting the rows and/or columns of
> the identity matrix), G is a given p x p matrix with full rank and I
> the identity matrix. ||.|| is the frobenius norm.
>
> Does anyone know an algorithm to solve such a problem? And if yes, is
> it implemented in R?
>
> Currently I minimize it by going through all possible permutations -
> but this is not feasible for higher dimensional problems as I would
> like to consider too.
>
> Any help is appreciated!
>
> Thanks in advance,
>
> Klaus
>
> --
> Jetzt kostenlos herunterladen: Internet Explorer 8 und Mozilla
> Firefox 3.5 -
> sicherer, schneller und einfacher!
>
> ______________________________________________
> R-help@r-project.org mailing list
>
> PLEASE do read the posting guide
> and provide commented, minimal, self-contained, reproducible code.
______________________________________________
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.
