Provably accurate double-sparse coding

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

    Research output: Contribution to journalArticle

    Abstract

    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 input dataset. However, a key challenge is that 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 et al. (2010b) 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 corroborate our theory with several numerical experiments on simulated data, suggesting that our method may be useful for problem sizes encountered in practice.

    Original languageEnglish (US)
    JournalJournal of Machine Learning Research
    Volume20
    StatePublished - Sep 1 2019

    Keywords

    • Provable algorithms
    • Sparse coding
    • Unsupervised learning

    ASJC Scopus subject areas

    • Software
    • Control and Systems Engineering
    • Statistics and Probability
    • Artificial Intelligence

    Fingerprint Dive into the research topics of 'Provably accurate double-sparse coding'. Together they form a unique fingerprint.

  • Cite this

    Nguyen, T. V., Wong, R. K. W., & Hegde, C. (2019). Provably accurate double-sparse coding. Journal of Machine Learning Research, 20.