Algebraically-initialized Expectation Maximization for Header-free Communication

Liangzu Peng; Xuming Song; Manolis C. Tsakiris; Hayoung Choi; Laurent Kneip; Yuamming Shi

doi:10.1109/ICASSP.2019.8682683

Algebraically-initialized Expectation Maximization for Header-free Communication

Liangzu Peng, Xuming Song, Manolis C. Tsakiris, Hayoung Choi, Laurent Kneip, Yuamming Shi

ShanghaiTech University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

12 Scopus citations

Abstract

Towards low-latency communication for short-packet transmission, this paper tackles the problem of shuffled linear regression for large-scale wireless sensor networks with header-free communication by using results from algebraic geometry as well as an alternating optimization scheme. The shuffled linear regression problem is to solve a linear system with shuffled entries of the right hand side vector. However, solving the shuffled linear system requires high computational cost. The key idea of our approach is to eliminate the shuffled structure via symmetric polynomials, which leads to a system of polynomial equations. Considering one of the solutions of the resulting polynomial system as an initialization to the Expectation Maximization algorithm, we propose the Algebraically-Initialized Expectation Maximization algorithm. Computational experiments with synthetic data show that our proposed algorithm is extensively efficient, and it performs well even with noise.

Original language	English
Title of host publication	2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	5182-5186
Number of pages	5
ISBN (Electronic)	9781479981311
DOIs	https://doi.org/10.1109/ICASSP.2019.8682683
State	Published - May 2019
Event	44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Brighton, United Kingdom Duration: 12 May 2019 → 17 May 2019

Publication series

Name	ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume	2019-May
ISSN (Print)	1520-6149

Conference

Conference	44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019
Country/Territory	United Kingdom
City	Brighton
Period	12/05/19 → 17/05/19

Keywords

algebraic geometry.
expectation maximization
Header-free communication
permuted linear model
shuffled linear regression
symmetric polynomials

Access to Document

10.1109/ICASSP.2019.8682683

Cite this

Peng, L., Song, X., Tsakiris, M. C., Choi, H., Kneip, L., & Shi, Y. (2019). Algebraically-initialized Expectation Maximization for Header-free Communication. In 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings (pp. 5182-5186). Article 8682683 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2019-May). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2019.8682683

Peng, Liangzu ; Song, Xuming ; Tsakiris, Manolis C. et al. / Algebraically-initialized Expectation Maximization for Header-free Communication. 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 5182-5186 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

@inproceedings{b55e6dc4096a4306a473ccbc84e2544c,

title = "Algebraically-initialized Expectation Maximization for Header-free Communication",

abstract = "Towards low-latency communication for short-packet transmission, this paper tackles the problem of shuffled linear regression for large-scale wireless sensor networks with header-free communication by using results from algebraic geometry as well as an alternating optimization scheme. The shuffled linear regression problem is to solve a linear system with shuffled entries of the right hand side vector. However, solving the shuffled linear system requires high computational cost. The key idea of our approach is to eliminate the shuffled structure via symmetric polynomials, which leads to a system of polynomial equations. Considering one of the solutions of the resulting polynomial system as an initialization to the Expectation Maximization algorithm, we propose the Algebraically-Initialized Expectation Maximization algorithm. Computational experiments with synthetic data show that our proposed algorithm is extensively efficient, and it performs well even with noise.",

keywords = "algebraic geometry., expectation maximization, Header-free communication, permuted linear model, shuffled linear regression, symmetric polynomials",

author = "Liangzu Peng and Xuming Song and Tsakiris, {Manolis C.} and Hayoung Choi and Laurent Kneip and Yuamming Shi",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 ; Conference date: 12-05-2019 Through 17-05-2019",

year = "2019",

month = may,

doi = "10.1109/ICASSP.2019.8682683",

language = "English",

series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "5182--5186",

booktitle = "2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings",

address = "United States",

}

Peng, L, Song, X, Tsakiris, MC, Choi, H, Kneip, L & Shi, Y 2019, Algebraically-initialized Expectation Maximization for Header-free Communication. in 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings., 8682683, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, vol. 2019-May, Institute of Electrical and Electronics Engineers Inc., pp. 5182-5186, 44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019, Brighton, United Kingdom, 12/05/19. https://doi.org/10.1109/ICASSP.2019.8682683

Algebraically-initialized Expectation Maximization for Header-free Communication. / Peng, Liangzu; Song, Xuming; Tsakiris, Manolis C. et al.
2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 5182-5186 8682683 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2019-May).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Algebraically-initialized Expectation Maximization for Header-free Communication

AU - Peng, Liangzu

AU - Song, Xuming

AU - Tsakiris, Manolis C.

AU - Choi, Hayoung

AU - Kneip, Laurent

AU - Shi, Yuamming

PY - 2019/5

Y1 - 2019/5

N2 - Towards low-latency communication for short-packet transmission, this paper tackles the problem of shuffled linear regression for large-scale wireless sensor networks with header-free communication by using results from algebraic geometry as well as an alternating optimization scheme. The shuffled linear regression problem is to solve a linear system with shuffled entries of the right hand side vector. However, solving the shuffled linear system requires high computational cost. The key idea of our approach is to eliminate the shuffled structure via symmetric polynomials, which leads to a system of polynomial equations. Considering one of the solutions of the resulting polynomial system as an initialization to the Expectation Maximization algorithm, we propose the Algebraically-Initialized Expectation Maximization algorithm. Computational experiments with synthetic data show that our proposed algorithm is extensively efficient, and it performs well even with noise.

AB - Towards low-latency communication for short-packet transmission, this paper tackles the problem of shuffled linear regression for large-scale wireless sensor networks with header-free communication by using results from algebraic geometry as well as an alternating optimization scheme. The shuffled linear regression problem is to solve a linear system with shuffled entries of the right hand side vector. However, solving the shuffled linear system requires high computational cost. The key idea of our approach is to eliminate the shuffled structure via symmetric polynomials, which leads to a system of polynomial equations. Considering one of the solutions of the resulting polynomial system as an initialization to the Expectation Maximization algorithm, we propose the Algebraically-Initialized Expectation Maximization algorithm. Computational experiments with synthetic data show that our proposed algorithm is extensively efficient, and it performs well even with noise.

KW - algebraic geometry.

KW - expectation maximization

KW - Header-free communication

KW - permuted linear model

KW - shuffled linear regression

KW - symmetric polynomials

UR - http://www.scopus.com/inward/record.url?scp=85068996361&partnerID=8YFLogxK

U2 - 10.1109/ICASSP.2019.8682683

DO - 10.1109/ICASSP.2019.8682683

M3 - Conference contribution

AN - SCOPUS:85068996361

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 5182

EP - 5186

BT - 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019

Y2 - 12 May 2019 through 17 May 2019

ER -

Peng L, Song X, Tsakiris MC, Choi H, Kneip L, Shi Y. Algebraically-initialized Expectation Maximization for Header-free Communication. In 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2019. p. 5182-5186. 8682683. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). doi: 10.1109/ICASSP.2019.8682683

Algebraically-initialized Expectation Maximization for Header-free Communication

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this