Integer Program Combination Optimization - Lattices II

1 Outline � � � Slide 1 Gram-Schmidt (GS) Orthogonalization. Reduced bases for lattices. Simultaneous Diophantine approximation. 2 GS orthogonalization Input: linearly independent vectors b1 Output: linearly independent vectors b~1 n b 2Q ~ that are orthogonal and span ::: b Slide 2 n n the same linear space. Algorithm: 1. (Initialization) b~1 = b1 2. (Main iteration) For = 2 n n ::: : i ::: , set: n ~ = (b ) b2 for j = 1 ~ jj jjb j i 0 i j ::: j b~ = b i i X1 i; ; j =1 i j b~ j i ;1 : 2.1 Intuition To initialize b~1 = b1 . Decompose b2 = v + u, such that v = b1 for some  2 R and u is orthogonal to b1 , i.e., u b1 = 0. Multiplying b2 = v + u by b1 , (b2 ) b1 = jjb1 jj2 : (b2 ) b1  = Slide 3 0 0 0 jjb1 jj2 ~b2 = u = b2 ; v = b2 ; b1 Geometrically b~2 corresponds to projecting b2 to the subspace that is orthogonal to b1 . 2.2 Properties (~b ) b~ = 0 for all i = 6 j:
P x 2 R j x = =1  b p 2 R = x 2 R k = 1 : : : n. Q det(L(b1 : : : b )) = =1 jj~b jj. ~ jj  jjb jj for j = 1 : : : n. jjb i 0 k n i n i n k i n j j j Slide 4 j j 1 jx = P k ~ =1 i b p 2 R k i i
for 2.3 Example Slide 5 b1 = (4 1) and b2 = (1 1) . The GS orthogonalization: b~1 = b1 and 0 0 b~2 = b2 ; 2 1 b~1 = (1 1) 0 ; 5 ~1 1 17 b = 17 (;3 12) 0 Note that b~1 , ~b2 do not form a basis of L. The GS orthogonalization depends on the order in which the vectors are processed. Consider b1 = (1 1) and b2 = (4 1) . The GS orthogonalization b~1 = b1 2 2 1 = 5=2 and ~ b = (1=2)(3 ;3) 0 0 0 2.4 Nearest vector Given x 2 R: bxe = Slide 6  if 0  x ; bxc  21 if 12 < x ; bxc  1: bxc dxe b1:5e = 1, b3:7e = 4 and b5:2e = 5. Let b1 : : : b be a basis of the lattice L with GS ~b1 : : : b~ . For every z 2 L n f0g, 1 jjzjj  minfjj~b jj : : : jj~b jjg: n n n 1 If ~b P b~ is a basis of L, then the nearest vector in L to the vector x = ~ =1  b , p 2 R is given by: X ~ b =  b where  = b e: j n ::: j n n j n j � j 2.5 Proof 0 =6 z = P =1 =1 i i i i 2 Z, j j = 1 : : : n. Let k be the largest index such that  = 6 0, i.e., j j  1,   P P 1  b~ ~ z =  b + =1 =1 n b with  j k P = k = k k i k j i; i i i j j  ~b + P =11  + P = +1   ~b + P =11  ~b k k;  k j j k Slide 7 i i i j i j b~ j j k; j j where  =  + = +1   . Since (~b ) ~b = 0, j j i 0 k i i j i j j jjzjj2 =zz= 0 X1 2  jj~ b jj2 + 2 jj~b jj2  2 jjb~ jj2  jj~b jj2: k; j j =1 k k j k 2 k k 1 ~ jj jjzjj  jj~b jj  minfjjb k P ::: jj~b jjg. n ~ with  2 Z , be an arbitrary vector of the lattice L. P Let x = =1  ~b , p 2 R . Then, b= =1 j b n j Slide 8 j j j n n j i jjb ; xjj2 = X n j =1 ( j j ; j )2 jj~b jj2  X n j =1 ( j j ; j )2 jj~b jj2 = jjb � ; xjj2: For all b 2 L, jjb ; xjj  jjb ; xjj: Importance of orthogonality. � 3 Reduced Bases 3.1 Denition = L(b1 : : : b ) with b1 : : : b 2 Q and with GS: ~b1 fb1 : : : b g is called reduced if the following conditions hold: (a) j j  12 , for all i j with 1  j < i  n, (b) jj~b +1 +  +1 b~ jj2  43 jj~b jj2, for all i = 1 : : : n ; 1: Let L n n n n ::: b~ . The basis n Slide 9 i j i i i i i 3.2 Intuition Conditions (a) and (b) jointly imply that a reduced basis consists of nearly orthogonal vectors. 1 b~ = b1 , condition (a) for i = 2 implies that (b2 ) b1  1 : 2 1 = 2 jjb1 jj2 0 From GS b2 = ~b2 + 2 1 b~1 and thus (b) for i = 1 jjb2 jj2  43 jjb1 jj2 : Let  be the angle between the two vectors b1 and b2 . Then 2 1 1 2 1 cos = (2b ) b 1 = (b 1) b2 jjb2 jj  21 p2 = p1 : jjb jj jjb jj jjb jj jjb jj 3 3 p This implies that   cos 1 (1= 3) = 54:7 , For the purpose of achieving a bigger angle between the two vectors, that is, bringing the vectors closer to orthogonality, we would like to have as high a constant c as possible. For c = 1, conditions (a) and (b) imply that an angle  would be at least cos 1 (1=2) = 60 . 0 0 o ; ; o 3 Slide 10 3.3 Properties For a reduced basis b1 : : : b of a lattice L and its GS ~b1 (a) jjb~ jj2  2 jj~b jj2 for all 1  i < j  n. (b) jjb1 jj  2( 1) 4 det(L)1 . (c) jjb1 jj  2( 1) 2 minfjjbjj : b 2 L n f0gg. (d) jjb1 jj    jjb jj  2( ( 1)) 4 det(L). n j n; = n; = n =n n n; n 3.4 Proof ::: Slide 11 b~ : i i;j For all i = 1 ::: n = Slide 12 ; 1: 3 ~i 2 ~i+1 ~i 2 4 jjb jj  jjb + i+1 i b jj = jj~bi+1 jj2 + 2i+1 i jj~bi jj2 i i+1  jj~b jj2 + 41 jj~b jj2 : This gives jj~ b +1 2 1 ~i 2 jj  jjb jj i leading to 2 j i jj~b jj2  2i;j jj~b jj2 for all i = 1 ;j det(L)2 ;1 for all 1  j  n: ;j From Proposition 6.2(c), we have n for all 1  i < j  n: Applying part (a) for i = 1 we obtain ~ jj2  21 jjb~1 jj2 = 21 jjb1 jj2 jjb j ::: !  n  (n(n;1))=2 Y 21;j jjb1 jj2n = 21 jjb1 jj2n = jj~b jj2  j =1 j =1 Y n j proving part (b). From Proposition 6.3, we have that for every b 2 L n f0g, jjbjj2  minfjj~b jj2 : j = 1 : : : ng  21 jjb1 jj2 j ;n proving part (c). From GS, Proposition 6.2 and the denition of a reduced basis we obtain P P b jj2 + =11 2 jj~b jj2  jj~b jj2 + 14 =11 jj~b jj2 jjb jj2 = jj~ P 1 ~ 2  jj~b jj2 + 14 =1 2 jjb jj  ; = jjb~ jj2 1 + 41 (2 + : : : + 2 1 )  ; = jj~b jj2 1 + 14 (2 ; 2)  jj~b jj2 2 1 : i i j i; j i j i; i j j i i; i;j i j i i; i i 4 i i; Using Proposition 6.2(c) we obtain Y n =1 jjbi jj2  2(n(n;1))=2 i Y n =1 i jj~b jj2 = 2( ( 1)) 2 det(L)2 n n; = i proving part (d). From Minkowvski, L there exist a vector u 2 L such that jjujj  det(L)1 . In contrast, jjb1 jj  jjb1 jj2  2( 1) 4 det(L)1 is weaker. The key dierence is that we can nd the vector b1 in polynomial time. 1 n; 1 = =n =n 3.5 Algorithm 6.2 Slide 13 Input: A basis b1 b 2 Z of a lattice L. Output: A basis of L satisfying condition (a) Algorithm: 1. For = 2 n ::: i ::: n n For j = i ; 1 : : : 1 (a) If j j > 1=2, then set b = b ; b eb . (b) Compute the GS of b1 : : : b and the corresponding multii i j i i j j n pliers  . 2. Return b1 i j ::: b . n 3.6 Correctness The basis returned by Algorithm 6.2 satises condition (a). Algorithm 6.2 requires O(n4 ) arithmetic operations. Algorithm 6.2 has the invariance property that after each iteration the GS of the initial basis of L remains unchanged, i.e., ~b = q~ for all i = 1 : : : n: i i 3.7 Basis Reduction Input: A basis b1 b 2 Z of a lattice L. Output: A basis of L satisfying conditions (a) and (b). Algorithm: 1. Compute the Gram-Schmidt orthogonalization b~1 1 n ::: b ::: n i ::: Slide 15 n b . 2. Apply Algorithm 6.2. 3. +1For = 1 ::: ~b of the vectors n n If jj~b +  +1 b~ jj2 < 3=4 jj~b jj2 , then interchange b and b +1 and return to Step 1. 4. Return b1 : : : b . i i i Slide 14 i i i n 5 i 3.8 Polynomiality Let b1 : : : b 2 Z be a basis of the lattice L. The basis reduction algorithm returns a reduced basis of L by performing O(n6 log 2 bmax ) arithmetic operations, where bmax is the largest integer (in absolute value) among the entries in b1 : : : b . n n Slide 16 n 4 Simultaneous diophantine approximation For given numbers 1 : : : 2 Q, 0 < < 1 and a given integer number N > 1, nd p1 : : : p 2 Z and q 2 Z+ with 0 < q  N satisfying: Slide 17 n n i ; pi < q q for i 2 f1 g ::: n : () If N  , then there exist p1 : : : p 2 Z and q 2 Z+ with 0 satisfying (*). Proof We dene a lattice L = L(b0 : : : b )  Q +1 where ;n n n b0 = ( 1 ::: n N n ) b = ;e 0  < q i i i =1 ::: n = +1 . Since det(L) = = +1 and dim(L) = n + 1, from Convex body theorem we obtain that there exists an a 2 L, a = 6 0 with jjajj  (det(L))1 ( +1) = : Hence, there exist q p1 : : : p 2 Z such that n n = n 1 n a = qb0 + X n =1 pi b i i with ja j  , or equivalently i jai j = jq i ; pi j  i =1 ::: n = q  i.e., q  : To complete the proof we need to check that q > 0. Note that we assume without loss of generality that q  0, since we can always take ;a instead of a. If q = 0, then jp j  for all i. Since p 2 Z and 0 < < 1, we have p = 0. This leads to a = 0, which is a contradiction since a = 6 0. ;n an i i i 4.1 Using Basis Reduction Theorem If N  2 ( +1) 4 , we can nd in polynomial time p1 : : : p 2 Z and q 2 Z+ with 0 < q  N satisfying Eq. (*). = 2 ( +1) 4 +1 in the basis for the lattice L dened earlier. Applying Basis Reduction we nd in polynomial time a reduced basis of L. The rst vector c 2 L in the reduced basis satises (recall that we use n + 1 instead of n, since dim(L) = n + 1) n n ;n n = = ;n n n jjcjj1  jjcjj2  2n=4 det(L)1=(n+1) 6 = 2 4 1 ( +1) = n= = n : Slide 18 Hence, we can nd p1 ::: pn 2Z and q 2 Z+ such that c = qb0 + X n =1 pi b i i with jc j  , or equivalently i jci j = jq cn =q  i.e., q  2 ( +1) 4 n n = i ; pi j  ;n : 7 i =1 ::: n