どの格子点に近い?

  • 先日、正単体を組み合わせた格子座標系上のある点からもっとも近い格子点ってどうやったらわかる?ということが話題になった
  • 多次元立方格子の場合には、各軸の値を四捨五入してやっておしまい
  • はて、正単体組合せでは…となった
  • どうも、近い格子点を探す方法で良いものはなかなかないなー、と思っていたら、それは「最短ベクトル問題」と呼ばれるNP困難な問題だと言う(こちらこちら)
  • 性質のよい格子の場合にはみつかるけど、ということで、超立方格子はもちろん、性質がものすごくよいものらしい
  • 直交している座標系っていうのは、軸の組合せに関する情報が全部0になるので、組合せ発散しないことがその(ある意味での)理由の様だった
  • 正単体なら、対称性も完璧だし、「性質が良い」のでは…と思うので、ちょっと考えてみる
  • \sum_{i=1}^k x_i=Kなる実亜空間上の点から最短距離にある\sum_{i=1}^k x_i=Kなる亜空間上の格子点を求めたい
  • 性質が完璧な超立方格子を利用することとする
  • 正単体格子は、超立方格子の部分集合である。原点からのハミング距離が一定である点の集合である
  • 従って、実亜空間上の任意の点について、ひとまず、k次元超立方格子点の最短距離のものを探す(これは上述のように簡単)
  • このようにして探した立方格子点が亜空間上にあれば、探索は終了
  • 不幸にして亜空間上にないときは、その仮の点(仮格子点)から、立方格子を何歩か歩けばたどり着けるだろう
  • 何歩あるくかは、仮格子点が\sum_{i=1}^k x_i = K'となっていてK \ne K'であるから、K-K'歩だけ歩けばよさそう。ここでK-K'の符号は歩くべき格子の向きについての情報を持っているので、『符号付き歩数』として取り扱いたい
  • ある符号付き歩数を歩くときに、あっちへプラス3歩、こっちへマイナス2歩で結果としてK-K'的には1歩分となる、という計算もあるが(この歩き方は、(おそらく)最短距離格子点の探索という条件から不適切である(ことが示せると思う)
  • また、ある方向に2歩してもよいか、というと、それも「そんなことができるなら、その方向に1歩の点の方が近いからだめ」というようなやり方で、不可であることが示せる(と思われる)
  • 従って、ある特定の軸について0か1歩で、総歩数がK-K'の絶対値になるような歩き方でたどり着く点が求める最近格子点になるのではないだろうか
  • すると、問題は、どの軸についてどちらに、というのが問題になる
  • これを解決するのに、総当たりでやることにすると、次元が高いときに、組合せ発散をしそうだ
  • 今、亜空間上の点の座標と、仮格子点の座標はわかっているから、その2点を結ぶベクトルもわかる。そのベクトルと遠くないような一歩を選ぶのが、他の一歩を選ぶよりもよいだろう。そんな選び方でK-K'歩歩いてたどり着くことにする
  • この結果をRで確かめると、最適ではないことが分かった。やはり、ある方向に1歩行くのと、あっちとこっちと合わせて3歩でK-K'的に1歩なのとでは、どちらがよいかはそれほど単純ではないことが実例からわかった
  • Rでやってみる
  • このようにして求めた格子点の周りをランダムに探索して、よりよい点が現れるかどうか、調べてみると、そこそこの回数を酔歩しても、そんな点は現れないようだ…だが、次元を上げると、もっと近い点も表れるようだ…

library(MCMCpack)
# dimension
k <- 10
# Which hyperplane points are located
v <- 100
# number of points te evaluate
n <- 10
# randomly generate points
R <- rdirichlet(n,rep(1,k))*v

#R.fl <- floor(R)
#R.cl <- R.fl + 1
# The closest lattice points in Cartesian coordinates
R.rd <- round(R)

# When values below are equal to v, then the lattice points are in the hyperplane.
# No further search is necessary
# When values below are not equal to v, then move steps in lattice.

hist(apply(R.rd,1,sum))

# How many steps?
# steps with direction
n.steps <- apply(R.rd,1,sum) -v

# Choose lattice directions closer to the vector R.rd->R
R.rd2R <- R- R.rd

# I have not proved, we should step only once for any individual direction.
# In case multiple steps are necesssary, choose directions in the order of closeness.

# direction
drc <- -sign(n.steps)
sign.R <- sign(R.rd2R)
tobeselected.R <- sign.R * drc

Ans <- R.rd

for(i in 1:n){
	tmp.select <- which(tobeselected.R[i,] > 0)
	tmp <- R.rd2R[i,tmp.select]
	tmp.val <- abs(R.rd2R[i,tmp.select])
	ord <- order(tmp.val)
	if(abs(n.steps[i])>0){
		tmp.d <- tmp.select[ord[1:abs(n.steps[i])]]
		tmp.v <- rep(0,k)
		tmp.v[tmp.d] <- 1*drc[i]
		Ans[i,] <- R.rd[i,] + tmp.v
	}
}
Ans

apply(Ans,1,sum)
# 周囲の点により近い点があるかどうか探してみる
n.iter <- 10000
dist.x <- matrix(0,n,n.iter)
for(i in 1:n){
	tmp.dist <- sqrt(sum((Ans[i,]-R[i,])^2))
	for(j in 1:n.iter){
		g <- sample(1:5,1)
		tmpp <- Ans[i,]
		for(j2 in 1:g){
			g2 <- sample(1:k,2)
			
			tmpp2 <- tmpp
			tmpp2[g2[1]] <- tmpp[g2[1]]+1
			tmpp2[g2[2]] <- tmpp[g2[2]]-1
			tmpp <- tmpp2
		}
		tmp.dist2 <- sqrt(sum((tmpp-R[i,])^2))
		dist.x[i,j] <- tmp.dist2-tmp.dist
	}
}

for(i in 1:n){
	plot(sort(dist.x[i,]))
}
hist(dist.x)
min(dist.x)
  • あるk次元座標のfloorを取ると、それを基準とした辺の長さ1のk次元立方体の中にその点はある
  • このk次元立方格子の頂点の数は2^n
  • この2^n個は座標の和の値によってn+1群に分かれる。そのうちの一つが調べている点と同じ亜空間上の点となる
  • したがって、[ted:\begin{pmatrix}k \\i \end{pmatrix}]個の点が対象となる
  • この数はたかだか\begin{pmatrix} k \\ (k/2)\end{pmatrix}個である
  • で、結局、これよりは減らせなさそう…
  • この方針は、アプローチを色々変えられるけれども、きれいに並んだ点に関するボロノイ図の作成、と同じことのようです。