Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Multicasting in Linear Deterministic Relay Netw...

Tasuku Soma
June 29, 2014
1.7k

Multicasting in Linear Deterministic Relay Network by Matrix Completion

ISIT 2014

Tasuku Soma

June 29, 2014
Tweet

Transcript

  1. 1 Linear Deterministic Relay Network (LDRN) 2 Unicast Algorithm 3

    Mixed Matrix Completion 4 Algorithm 5 Conclusion 2 / 20
  2. 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
  3. 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
  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) • Superposition is modeled as addition in F. 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) • Superposition is modeled as addition in F. 3 / 20
  6. 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
  7. 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
  8. 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
  9. 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
  10. 1 Linear Deterministic Relay Network (LDRN) 2 Unicast Algorithm 3

    Mixed Matrix Completion 4 Algorithm 5 Conclusion 8 / 20
  11. 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
  12. 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
  13. 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
  14. 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
  15. 1 Linear Deterministic Relay Network (LDRN) 2 Unicast Algorithm 3

    Mixed Matrix Completion 4 Algorithm 5 Conclusion 11 / 20
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 1 Linear Deterministic Relay Network (LDRN) 2 Unicast Algorithm 3

    Mixed Matrix Completion 4 Algorithm 5 Conclusion 14 / 20
  23. 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
  24. 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
  25. 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
  26. Algorithm vi+1 = MiXivi = MiXiPiw. Thus At = Mi

    [Ft ]XiPi (Mi [Ft ]: Ft -row submatrix of Mi) 17 / 20
  27. 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
  28. 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
  29. 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
  30. 1 Linear Deterministic Relay Network (LDRN) 2 Unicast Algorithm 3

    Mixed Matrix Completion 4 Algorithm 5 Conclusion 19 / 20
  31. 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