Convergence radius and sample complexity of ITKM algorithms for dictionary learning

被引：18
|
作者：
Schnass, Karin [1 ]
机构：
[1] Univ Innsbruck, Dept Math, Tech Str 13, A-6020 Innsbruck, Austria
来源：
APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS | 2018年 / 45卷 / 01期
基金：
奥地利科学基金会;
关键词：
Dictionary learning; Sparse coding; Sparse component analysis; Sample complexity; Convergence radius; Alternating optimisation; Thresholding; K-means; BLIND SOURCE SEPARATION; OVERCOMPLETE DICTIONARIES; SPARSE REPRESENTATION; MATRIX-FACTORIZATION; K-SVD; IDENTIFICATION; NOISE;
D O I：
10.1016/j.acha.2016.08.002
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this work we show that iterative thresholding and K means (ITKM) algorithms can recover a generating dictionary with K atoms from noisy S sparse signals up to an error (epsilon) over tilde as long as the initialisation is within a convergence radius, that is up to a log K factor inversely proportional to the dynamic range of the signals, and the sample size is proportional to K log K (epsilon) over tilde (-2). The results are valid for arbitrary target errors if the sparsity level is of the order of the square root of the signal dimension d and for target errors down to K-l if S scales as S <= d/(l log K). (C) 2016 Elsevier Inc. All rights reserved.
引用
收藏
页码：22 / 58
页数：37
相关论文
共 50 条
  • [1] ON THE SAMPLE COMPLEXITY OF SPARSE DICTIONARY LEARNING
    Seibert, M.
    Kleinsteuber, M.
    Gribonval, R.
    Jenatton, R.
    Bach, F.
    2014 IEEE WORKSHOP ON STATISTICAL SIGNAL PROCESSING (SSP), 2014, : 244 - 247
  • [2] The Sample Complexity of Dictionary Learning
    Vainsencher, Daniel
    Mannor, Shie
    Bruckstein, Alfred M.
    JOURNAL OF MACHINE LEARNING RESEARCH, 2011, 12 : 3259 - 3281
  • [3] DICTIONARY LEARNING FOR SPARSE REPRESENTATION: COMPLEXITY AND ALGORITHMS
    Razaviyayn, Meisam
    Tseng, Hung-Wei
    Luo, Zhi-Quan
    2014 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2014,
  • [4] Sample Complexity of Dictionary Learning and Other Matrix Factorizations
    Gribonval, Remi
    Jenatton, Rodolphe
    Bach, Francis
    Kleinsteuber, Martin
    Seibert, Matthias
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2015, 61 (06) : 3469 - 3486
  • [5] Sample Complexity of Dictionary Learning on Stationary Mixing Data
    Guo, Li-juan
    PROCEEDINGS OF THE 2015 CONFERENCE ON INFORMATIZATION IN EDUCATION, MANAGEMENT AND BUSINESS, 2015, 20 : 312 - 318
  • [6] Dictionary Learning for Sparse Coding: Algorithms and Convergence Analysis
    Bao, Chenglong
    Ji, Hui
    Quan, Yuhui
    Shen, Zuowei
    IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2016, 38 (07) : 1356 - 1369
  • [7] SAMPLE COMPLEXITY BOUNDS FOR DICTIONARY LEARNING OF TENSOR DATA
    Shakeri, Zahra
    Bajwa, Waheed U.
    Sarwate, Anand D.
    2017 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2017, : 4501 - 4505
  • [8] Improved Identifiability and Sample Complexity Analysis of Complete Dictionary Learning
    Sun, Yuchen
    Huang, Kejun
    2024 IEEE 13RD SENSOR ARRAY AND MULTICHANNEL SIGNAL PROCESSING WORKSHOP, SAM 2024, 2024,
  • [9] On the Convergence of a Bayesian Algorithm for Joint Dictionary Learning and Sparse Recovery
    Joseph, Geethu
    Murthy, Chandra R.
    IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2020, 68 : 343 - 358
  • [10] Optimal Quantum Sample Complexity of Learning Algorithms
    Arunachalam, Srinivasan
    de Wolf, Ronald
    JOURNAL OF MACHINE LEARNING RESEARCH, 2018, 19
12345