Multicasting in Linear Deterministic Relay Network by Matrix Completion

ISIT 2014

Transcript

1. Multicasting in Linear Deterministic Relay Network by Matrix Completion Tasuku Soma Univ. of Tokyo 1 / 20
2. 1 Linear Deterministic Relay Network (LDRN) 2 Unicast Algorithm 3 Mixed Matrix Completion 4 Algorithm 5 Conclusion 2 / 20
3. Linear Deterministic Relay Network (LDRN) A model for wireless communication [Avestimehr–Diggavi–Tse’07] 3 / 20
4. Linear Deterministic Relay Network (LDRN) A model for wireless communication [Avestimehr–Diggavi–Tse’07] • Signals are represented by elements of a finite field F • Signals are sent to several nodes (Broadcast) 3 / 20
5. Linear Deterministic Relay Network (LDRN) A model for wireless communication [Avestimehr–Diggavi–Tse’07] • Signals are represented by elements of a finite field F • Signals are sent to several nodes (Broadcast) 3 / 20
6. Linear Deterministic Relay Network (LDRN) A model for wireless communication [Avestimehr–Diggavi–Tse’07] • Signals are represented by elements of a finite field F • Signals are sent to several nodes (Broadcast) • Superposition is modeled as addition in F. 3 / 20
7. Linear Deterministic Relay Network (LDRN) A model for wireless communication [Avestimehr–Diggavi–Tse’07] • Signals are represented by elements of a finite field F • Signals are sent to several nodes (Broadcast) • Superposition is modeled as addition in F. 3 / 20
8. Multicasting in LDRN • intermediate nodes can perform a linear coding • |F| > # of sinks 4 / 20
9. Multicasting in LDRN • intermediate nodes can perform a linear coding • |F| > # of sinks 4 / 20
10. Previous Work Randomized Algorithm (|F| is large): Theorem (Avestimehr-Diggavi-Tse ’07) Random conding is a solution w.h.p. Deterministic Algorithm (|F| > d): Theorem (Yazdi–Savari ’13) A Deterministic algorithm for multicast in LDRN which runs in O(dq((nr)3 log(nr)+n2r4)) time. d: # sinks, n: max # nodes in each layer, q: # layers, r: capacity of node 5 / 20
11. Our Result Deterministic Algorithm (|F| > d): Theorem A deterministic algorithm for multicast in LDRN which runs in O(dq((nr)3 log(nr)) time. d: # sinks, n: max # nodes in each layer, q: # layers, r: capacity of node • Faster when n = o(r) • Complexity matches: current best complexity of unicast×d 6 / 20
12. Technical Contribution Yazdi-Savari’s algorithm: Step 1 Solve unicasts by Goemans– Iwata–Zenklusen’s algorithm Step 2 Determine linear encoding of nodes one by one. 7 / 20
13. Technical Contribution Yazdi-Savari’s algorithm: Step 1 Solve unicasts by Goemans– Iwata–Zenklusen’s algorithm Step 2 Determine linear encoding of nodes one by one. Our algorithm: Step 1 Solve unicasts by Goemans– Iwata–Zenklusen’s algorithm Step 2 Determine linear encoding of layer at once by matrix completion 7 / 20
14. 1 Linear Deterministic Relay Network (LDRN) 2 Unicast Algorithm 3 Mixed Matrix Completion 4 Algorithm 5 Conclusion 8 / 20
15. Unicast in LDRN One-to-one communication 9 / 20
16. Unicast in LDRN One-to-one communication • Goemans-Iwata-Zenklusen’s algorithm: ... the current fastest algorithm for unicast 9 / 20
17. s–t flow 1 For each node, # of inputs in F = # of outputs in F. 2 Linear maps between layers corresponding to F are nonsingular. 3 At the last layer, F is contained in the outputs of t. 10 / 20
18. s–t flow one for each 1 For each node, # of inputs in F = # of outputs in F. 2 Linear maps between layers corresponding to F are nonsingular. 3 At the last layer, F is contained in the outputs of t. 10 / 20
19. s–t flow [ x y ] → [ x y ] [ x y ] → [ x x+y ] [ x y ] → [ x y ] 1 For each node, # of inputs in F = # of outputs in F. 2 Linear maps between layers corresponding to F are nonsingular. 3 At the last layer, F is contained in the outputs of t. 10 / 20
20. s–t flow 1 For each node, # of inputs in F = # of outputs in F. 2 Linear maps between layers corresponding to F are nonsingular. 3 At the last layer, F is contained in the outputs of t. 10 / 20
21. s–t flow Theorem (Goemans–Iwata–Zenklusen ’12) In LDRN, s–t flow can be found in O(q(nr)3 log(nr)) time. 10 / 20
22. 1 Linear Deterministic Relay Network (LDRN) 2 Unicast Algorithm 3 Mixed Matrix Completion 4 Algorithm 5 Conclusion 11 / 20
23. Mixed Matrix Completion Mixed Matrix: Matrix containing indeterminates s.t. each indeterminate appears only once. Example A = 1 + x1 2 + x2 x3 0 = 1 2 0 0 + x1 x2 x3 0 12 / 20
24. Mixed Matrix Completion Mixed Matrix: Matrix containing indeterminates s.t. each indeterminate appears only once. Example A = 1 + x1 2 + x2 x3 0 = 1 2 0 0 + x1 x2 x3 0 Mixed Matrix Completion: Find values for indeterminates of mixed matrix so that the rank of resulting matrix is maximized Example F = Q A = 1 + x1 2 + x2 x3 0 −→ A = 2 2 1 0 (x1 := 1, x2 := 0, x3 := 1) 12 / 20
25. Simultaneous Mixed Matrix Completion Simultaneous Mixed Matrix Completion F: Field Input Collection A of mixed matrices (over F) Find Value assignment αi ∈ F for each indeterminate xi maximizing the rank of every matrix in A 13 / 20
26. Simultaneous Mixed Matrix Completion Simultaneous Mixed Matrix Completion F: Field Input Collection A of mixed matrices (over F) Find Value assignment αi ∈ F for each indeterminate xi maximizing the rank of every matrix in A Example A = x1 1 0 x2 , 1 + x1 0 1 x3 → 1 1 0 1 , 2 0 1 1 if F = F3 13 / 20
27. Simultaneous Mixed Matrix Completion Simultaneous Mixed Matrix Completion F: Field Input Collection A of mixed matrices (over F) Find Value assignment αi ∈ F for each indeterminate xi maximizing the rank of every matrix in A Example A = x1 1 0 x2 , 1 + x1 0 1 x3 → 1 1 0 1 , 2 0 1 1 if F = F3 → No solution if F = F2 13 / 20
28. Simultaneous Mixed Matrix Completion Simultaneous Mixed Matrix Completion F: Field Input Collection A of mixed matrices (over F) Find Value assignment αi ∈ F for each indeterminate xi maximizing the rank of every matrix in A Example A = x1 1 0 x2 , 1 + x1 0 1 x3 → 1 1 0 1 , 2 0 1 1 if F = F3 → No solution if F = F2 Theorem (Harvey-Karger-Murota ’05) If |F| > |A|, the simultaneous mixed matrix completion always has a solution, which can be found in polytime. 13 / 20
29. 1 Linear Deterministic Relay Network (LDRN) 2 Unicast Algorithm 3 Mixed Matrix Completion 4 Algorithm 5 Conclusion 14 / 20
30. Algorithm Algorithm 1. for each t ∈ T : 2. Find s–t flow Ft Goemans–Iwata–Zenklusen 3. for i = 1, . . . , q : 4. Determine the linear encoding Xi of the i-th layer Matrix Completion 5. return X1 , . . . , Xq 15 / 20
31. Algorithm w: message vector vi: the input vector of the i-th layer Determine Xi so that the linear map At : w → (subvector of vi corresponding to Ft ) is nonsingular for each sink t ∈ T. 16 / 20
32. Algorithm w: message vector vi: the input vector of the i-th layer Determine Xi so that the linear map At : w → (subvector of vi corresponding to Ft ) is nonsingular for each sink t ∈ T. 16 / 20
33. Algorithm vi+1 = MiXivi = MiXiPiw. Thus At = Mi [Ft ]XiPi (Mi [Ft ]: Ft -row submatrix of Mi) 17 / 20
34. Algorithm vi+1 = MiXivi = MiXiPiw. Thus At = Mi [Ft ]XiPi (Mi [Ft ]: Ft -row submatrix of Mi) Determine Xi so that the matrix Mi [Ft ]XiPi is nonsingular for each sink t. 17 / 20
35. Algorithm Mi [Ft ]XiPi is NOT a mixed matrix ... BUT Lemma Mi [Ft ]XiPi is nonsingular ⇐⇒ a mixed matrix I O Pi Xi I O O Mi[Ft ] O is nonsingular 18 / 20
36. Algorithm Mi [Ft ]XiPi is NOT a mixed matrix ... BUT Lemma Mi [Ft ]XiPi is nonsingular ⇐⇒ a mixed matrix I O Pi Xi I O O Mi[Ft ] O is nonsingular We can find Xi s.t. I O Pi Xi I O O Mi[Ft ] O is nonsingular for each t by simultaneous mixed matrix completion ! Theorem If |F| > d, multicast problem in LDRN can be solved in O(dq(nr)3 log(nr)) time. d: # sinks, n: max # nodes in each layer, q: # layers, r: capacity of node 18 / 20
37. 1 Linear Deterministic Relay Network (LDRN) 2 Unicast Algorithm 3 Mixed Matrix Completion 4 Algorithm 5 Conclusion 19 / 20
38. Conclusion • Deterministic algorithm for multicast in LDRN using matrix completion • Faster than the previous algorithm when n = o(r) • Complexity matches (current best complexity of unicast)×d d: # sinks, n: max # nodes in each layer, q: # layers, r: capacity of node 20 / 20