Dictionary Learning with BLOTLESS Update

Abstract

Algorithms for learning a dictionary to sparsely represent a given dataset typically alternate between sparse coding and dictionary update stages. Methods for dictionary update aim to minimise expansion error by updating dictionary vectors and expansion coefficients given patterns of non-zero coefficients obtained in the sparse coding stage. We propose a block total least squares (BLOTLESS) algorithm for dictionary update. BLOTLESS updates a block of dictionary elements and the corresponding sparse coefficients simultaneously. In the error free case, three necessary conditions for exact recovery are identified. Lower bounds on the number of training data are established so that the necessary conditions hold with high probability. Numerical simulations show that the bounds approximate well the number of training data needed for exact dictionary recovery. Numerical experiments further demonstrate several benefits of dictionary learning with BLOTLESS update compared with state-of-the-art algorithms especially when the amount of training data is small.

References in corpus (11)

• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Simultaneous Codeword Optimization (SimCO) for Dictionary Update and Learning
• Exact Recovery of Sparsely-Used Dictionaries
• Simple, Efficient, and Neural Algorithms for Sparse Coding
• New Algorithms for Learning Incoherent and Overcomplete Dictionaries
• On the Identifiability of Overcomplete Dictionaries via the Minimisation Principle Underlying K-SVD
• More Algorithms for Provable Dictionary Learning
• On the Local Correctness of L^1 Minimization for Dictionary Learning
• Local Identification of Overcomplete Dictionaries
• When can dictionary learning uniquely recover sparse data from subsamples?

Cited by in corpus (1)

• Dictionary Learning with Low-rank Coding Coefficients for Tensor Completion