28967 articles – 22397 Notices  [english version]

hal-00716593, version 1

Greedy-Like Algorithms for the Cosparse Analysis Model

Raja Giryes a, 1, Sangnam Nam () b, 2, Michael Elad () 1, Rémi Gribonval (, http://www.irisa.fr/metiss/members/remi) 2, Mike E. Davies () 3

  • a –  Technion
  • b –  INRIA
  • 1 :  Department of Computer Science [Haifa]
  • http://www.cs.technion.ac.il
    University of Haifa Taub Building, Technion Israel Institute of Technology, Haifa 32000 Israël
  • 2 :  METISS (INRIA - IRISA)
  • http://www.inria.fr/equipes/metiss
    CNRS : UMR6074 – INRIA – Institut National des Sciences Appliquées (INSA) - Rennes – Université de Rennes 1 Campus de Beaulieu 35042 Rennes cedex France
  • 3 :  Institute for Digital Communication Joint Research Institute for Signal & Image Processing School of Engineering and Electronics - University of Edinburgh
  • http://www.see.ed.ac.uk/
    University of Edinburgh The King's Buildings Edinburgh, EH9 3JL Royaume-Uni
  • Versions disponibles :  v1 (10-07-2012) v2 (18-01-2013)

    • Références bibliographiques

    • Type de publication : Documents sans référence de publication (Preprint)
    • Domaine :
      Informatique/Traitement du signal et de l'image
      Sciences de l'ingénieur/Traitement du signal et de l'image
      Mathématiques/Analyse fonctionnelle
    • Titre : Greedy-Like Algorithms for the Cosparse Analysis Model
    • Résumé : The cosparse analysis model has been introduced recently as an interesting alternative to the standard sparse synthesis approach. A prominent question brought up by this new construction is the analysis pursuit problem -- the need to find a signal belonging to this model, given a set of corrupted measurements of it. Several pursuit methods have already been proposed based on $\ell_1$ relaxation and a greedy approach. In this work we pursue this question further, and propose a new family of pursuit algorithms for the cosparse analysis model, mimicking the greedy-like methods -- compressive sampling matching pursuit (CoSaMP), subspace pursuit (SP), iterative hard thresholding (IHT) and hard thresholding pursuit (HTP). Assuming the availability of a near optimal projection scheme that finds the nearest cosparse subspace to any vector, we provide performance guarantees for these algorithms. Our theoretical study relies on a restricted isometry property adapted to the context of the cosparse analysis model. We explore empirically the performance of these algorithms by adopting a plain thresholding projection, demonstrating their good performance.
    • Langue du document : Anglais
    • Mots-clés : Sparse representations – Compressed sensing – Synthesis – Analysis – CoSaMP – Subspace-pursuit – Iterative hard threshodling – Hard thresholding pursuit.
    • Projet européen :
      Numéro Cordis 225913
      Acronyme SMALL
      Titre Sparse Models, Algorithms, and Learning for Large Scale Data
      Financé par ICT
      Début 2009-01-31
      Date de fin 2012-07-31
      Identifiant de l'appel FP7-ICT-2007-C

    Liste des fichiers attachés à ce document :

    TEX
    ACoSaMP1_2.eps(66.8 KB)
    ACoSaMP1.2Condition.eps(66.8 KB)
    ACoSaMP2.eps(38.6 KB)
    ACoSaMP2_TV.eps(38.6 KB)
    ACoSaMPth1.2Condition.eps(66.8 KB)
    ACoSaMPth1_2.eps(66.8 KB)
    AHTP_adaptive1.2Condition.eps(66.8 KB)
    AHTP_adaptive1_2.eps(66.8 KB)
    AHTP_adaptive2.eps(66.8 KB)
    AHTP_adaptive2_TV.eps(38.6 KB)
    AHTP_adaptive2_TV_Condition.eps(38.6 KB)
    AHTP_adaptive2Condition.eps(66.8 KB)
    AHTP_const1.2Condition.eps(66.8 KB)
    AHTP_const1_2.eps(66.8 KB)
    AHTP_const2.eps(66.8 KB)
    AHTP_const2_TV.eps(38.6 KB)
    AHTP_const2_TV_Condition.eps(38.6 KB)
    AHTP_const2Condition.eps(66.8 KB)
    AIHT_adaptive1.2Condition.eps(66.8 KB)
    AIHT_adaptive1_2.eps(66.8 KB)
    AIHT_adaptive2.eps(66.8 KB)
    AIHT_adaptive2_TV.eps(38.6 KB)
    AIHT_adaptive2_TV_Condition.eps(38.6 KB)
    AIHT_adaptive2Condition.eps(66.8 KB)
    AIHT_const1.2Condition.eps(66.8 KB)
    AIHT_const1_2.eps(66.8 KB)
    AIHT_const2.eps(66.8 KB)
    AIHT_const2_TV.eps(38.6 KB)
    AIHT_const2_TV_Condition.eps(38.6 KB)
    AIHT_const2Condition.eps(66.8 KB)
    analysis_greedy_like.aux(15.7 KB)
    analysis_greedy_like.bbl(6.4 KB)
    analysis_greedy_like.blg(1.1 KB)
    analysis_greedy_like.ps(1.9 MB)
    analysis_greedy_like.spl(0 B)
    analysis_greedy_like.tex(163.1 KB)
    AnalysisGreedyLike.bib(40.7 KB)
    ASP1_2.eps(66.8 KB)
    ASP1_2Condition.eps(66.8 KB)
    ASP2.eps(38.6 KB)
    ASP2_TV.eps(38.6 KB)
    ASPth1_2.eps(66.8 KB)
    ASPth1_2Condition.eps(66.8 KB)
    elsarticle-num.bst(29.3 KB)
    elsarticle.cls(25.5 KB)
    GAP1_2.eps(38.6 KB)
    gradients.eps(22.7 KB)
    L11_2.eps(38.6 KB)
    phantom all.eps(163.2 KB)
    phantom.eps(138.1 KB)
    phantom_and_samples.eps(31.1 KB)
    phantom_noisy.eps(138.2 KB)
    phantom_reconstruction_AIHT35.eps(138.2 KB)
    phantom_reconstruction_ASP.eps(138.2 KB)
    phantom_reconstruction_ASP_noisy.eps(138.2 KB)
    phantom_with_reconstruction_AIHT35.eps(21 KB)
    PDF
    analysis_greedy_like.pdf(442.3 KB)
    PS
    analysis_greedy_like.ps(2 MB)
     
    • hal-00716593, version 1
    • http://hal.inria.fr/hal-00716593
    • oai:hal.inria.fr:hal-00716593
    • Contributeur : Rémi Gribonval <>
    • Soumis le : Mardi 10 Juillet 2012, 20:31:49
    • Dernière modification le : Mardi 10 Juillet 2012, 21:56:55