A fast algorithm for demixing signals with structured sparsity

Chinmay Hegde

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publication2016 International Conference on Signal Processing and Communications, SPCOM 2016
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    ISBN (Electronic)9781509017461
    DOIs
    StatePublished - Nov 16 2016
    Event11th International Conference on Signal Processing and Communications, SPCOM 2016 - Bangalore, India
    Duration: Jun 12 2016Jun 15 2016

    Publication series

    Name2016 International Conference on Signal Processing and Communications, SPCOM 2016

    Conference

    Conference11th International Conference on Signal Processing and Communications, SPCOM 2016
    CountryIndia
    CityBangalore
    Period6/12/166/15/16

    ASJC Scopus subject areas

    • Computer Networks and Communications
    • Signal Processing

    Fingerprint Dive into the research topics of 'A fast algorithm for demixing signals with structured sparsity'. Together they form a unique fingerprint.

  • Cite this

    Hegde, C. (2016). A fast algorithm for demixing signals with structured sparsity. In 2016 International Conference on Signal Processing and Communications, SPCOM 2016 [7746622] (2016 International Conference on Signal Processing and Communications, SPCOM 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SPCOM.2016.7746622