Improved sparse approximation over quasi-incoherent dictionaries

J. A. Tropp, A. C. Gilbert, S. Muthukrishnan, M. J. Strauss

    Research output: Contribution to conferencePaperpeer-review


    This paper discusses a new greedy algorithm for solving the sparse approximation problem over quasi-incoherent dictionaries. These dictionaries consist of waveforms that are uncorrelated "on average," and they provide a natural generalization of incoherent dictionaries. The algorithm provides strong guarantees on the quality of the approximations it produces, unlike most other methods for sparse approximation. Moreover, very efficient implementations are possible via approximate nearest-neighbor data structures.

    Original languageEnglish (US)
    Number of pages4
    StatePublished - 2003
    EventProceedings: 2003 International Conference on Image Processing, ICIP-2003 - Barcelona, Spain
    Duration: Sep 14 2003Sep 17 2003


    OtherProceedings: 2003 International Conference on Image Processing, ICIP-2003

    ASJC Scopus subject areas

    • Hardware and Architecture
    • Computer Vision and Pattern Recognition
    • Electrical and Electronic Engineering


    Dive into the research topics of 'Improved sparse approximation over quasi-incoherent dictionaries'. Together they form a unique fingerprint.

    Cite this