A provable approach for double-sparse coding

Thanh V. Nguyen, Raymond K.W. Wong, Chinmay Hegde

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


    Sparse coding is a crucial subroutine in algorithms for various signal processing, deep learning, and other machine learning applications. The central goal is to learn an overcomplete dictionary that can sparsely represent a given dataset. However, storage, transmission, and processing of the learned dictionary can be untenably high if the data dimension is high. In this paper, we consider the double-sparsity model introduced by Rubinstein, Zibulevsky, and Elad (2010) where the dictionary itself is the product of a fixed, known basis and a data-adaptive sparse component. First, we introduce a simple algorithm for double-sparse coding that can be amenable to efficient implementation via neural architectures. Second, we theoretically analyze its performance and demonstrate asymptotic sample complexity and running time benefits over existing (provable) approaches for sparse coding. To our knowledge, our work introduces the first computationally efficient algorithm for double-sparse coding that enjoys rigorous statistical guarantees. Finally, we support our analysis via several numerical experiments on simulated data, confirming that our method can indeed be useful in problem sizes encountered in practical applications.

    Original languageEnglish (US)
    Title of host publication32nd AAAI Conference on Artificial Intelligence, AAAI 2018
    PublisherAAAI press
    Number of pages8
    ISBN (Electronic)9781577358008
    StatePublished - 2018
    Event32nd AAAI Conference on Artificial Intelligence, AAAI 2018 - New Orleans, United States
    Duration: Feb 2 2018Feb 7 2018

    Publication series

    Name32nd AAAI Conference on Artificial Intelligence, AAAI 2018


    Other32nd AAAI Conference on Artificial Intelligence, AAAI 2018
    Country/TerritoryUnited States
    CityNew Orleans

    ASJC Scopus subject areas

    • Artificial Intelligence


    Dive into the research topics of 'A provable approach for double-sparse coding'. Together they form a unique fingerprint.

    Cite this