TY - GEN
T1 - A fast algorithm for demixing signals with structured sparsity
AU - Hegde, Chinmay
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/11/16
Y1 - 2016/11/16
N2 - Demixing, or source separation, involves disentangling a complicated signal into simpler, more informative components. Algorithms for signal demixing impact several applications, ranging from interference cancellation in communication signals, foreground-background separation in images and video, and outlier suppression in machine learning. Central to several modern demixing algorithms is an assumption of some form of low-dimensional structure in the signal components. However, the majority of these modern algorithms are based on convex optimization, and their computational complexity can be high (polynomial) in terms of the signal size. In this paper, we propose a new algorithmic approach for signal demixing based on structured sparsity models. Our approach leverages recent advances in constructing sparsity models via appropriately chosen graphs; this graphical approach can be shown to model a diverse variety of low-dimensional structures in signals. Despite being highly nonconvex, our algorithm exhibits a nearly-linear running time, and therefore is scalable to very high-dimensional signals. We supplement our proposed algorithm with a theoretical analysis, providing sufficient conditions for provably reconstruction of the underlying components. Finally, we demonstrate the validity of the method via numerical experiments on real 2D image data.
AB - Demixing, or source separation, involves disentangling a complicated signal into simpler, more informative components. Algorithms for signal demixing impact several applications, ranging from interference cancellation in communication signals, foreground-background separation in images and video, and outlier suppression in machine learning. Central to several modern demixing algorithms is an assumption of some form of low-dimensional structure in the signal components. However, the majority of these modern algorithms are based on convex optimization, and their computational complexity can be high (polynomial) in terms of the signal size. In this paper, we propose a new algorithmic approach for signal demixing based on structured sparsity models. Our approach leverages recent advances in constructing sparsity models via appropriately chosen graphs; this graphical approach can be shown to model a diverse variety of low-dimensional structures in signals. Despite being highly nonconvex, our algorithm exhibits a nearly-linear running time, and therefore is scalable to very high-dimensional signals. We supplement our proposed algorithm with a theoretical analysis, providing sufficient conditions for provably reconstruction of the underlying components. Finally, we demonstrate the validity of the method via numerical experiments on real 2D image data.
UR - http://www.scopus.com/inward/record.url?scp=85003906056&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85003906056&partnerID=8YFLogxK
U2 - 10.1109/SPCOM.2016.7746622
DO - 10.1109/SPCOM.2016.7746622
M3 - Conference contribution
AN - SCOPUS:85003906056
T3 - 2016 International Conference on Signal Processing and Communications, SPCOM 2016
BT - 2016 International Conference on Signal Processing and Communications, SPCOM 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 11th International Conference on Signal Processing and Communications, SPCOM 2016
Y2 - 12 June 2016 through 15 June 2016
ER -