Title :
Dictionary identifiability from few training samples
Author :
Gribonval, Remi ; Schnass, Karin
Author_Institution :
IRISA, Centre de Rech. INRIA Rennes - Bretagne Atlantique, Rennes, France
Abstract :
This article treats the problem of learning a dictionary providing sparse representations for a given signal class, via ℓ1 minimisation. The problem is to identify a dictionary Φ from a set of training samples Y knowing that Y = ΦX for some coefficient matrix X. Using a characterisation of coefficient matrices X that allow to recover any orthonormal basis (ONB) as a local minimum of an ℓ1 minimisation problem, it is shown that certain types of sparse random coefficient matrices will ensure local identifiability of the ONB with high probability, for a number of training samples which essentially grows linearly with the signal dimension.
Keywords :
learning (artificial intelligence); matrix algebra; minimisation; probability; signal representation; ℓ1 minimisation; ONB; dictionary identifiability; orthonormal basis; probability; sparse random coefficient matrix; sparse signal representation; training sample; Algorithm design and analysis; Dictionaries; Minimization; Signal processing; Sparse matrices; Training; Vectors;
Conference_Titel :
Signal Processing Conference, 2008 16th European
Conference_Location :
Lausanne