Dictionary Identification - Sparse Matrix-Factorisation via $\ell_1$-Minimisation

Details Dictionary Identification - Sparse Matrix-Factorisation via $\ell_1$-Minimisation Dictionary Identification - Sparse Matrix-Factorisation via $\ell_1$-Minimisation

2009-04-30

arxiv.org/abs/0904.4774v2

Computer Science

Information Theory

32 pages (IEEE draft format), 8 figures, submitted to IEEE Trans. Inf. Theory

Scientific paper

This article treats the problem of learning a dictionary providing sparse representations for a given signal class, via $\ell_1$-minimisation. The problem can also be seen as factorising a $\ddim \times \nsig$ matrix $Y=(y_1 >... y_\nsig), y_n\in \R^\ddim$ of training signals into a $\ddim \times \natoms$ dictionary matrix $\dico$ and a $\natoms \times \nsig$ coefficient matrix $\X=(x_1... x_\nsig), x_n \in \R^\natoms$, which is sparse. The exact question studied here is when a dictionary coefficient pair $(\dico,\X)$ can be recovered as local minimum of a (nonconvex) $\ell_1$-criterion with input $Y=\dico \X$. First, for general dictionaries and coefficient matrices, algebraic conditions ensuring local identifiability are derived, which are then specialised to the case when the dictionary is a basis. Finally, assuming a random Bernoulli-Gaussian sparse model on the coefficient matrix, it is shown that sufficiently incoherent bases are locally identifiable with high probability. The perhaps surprising result is that the typically sufficient number of training samples $\nsig$ grows up to a logarithmic factor only linearly with the signal dimension, i.e. $\nsig \approx C \natoms \log \natoms$, in contrast to previous approaches requiring combinatorially many samples.

Affiliated with

Also associated with

No associations

Rating

Dictionary Identification - Sparse Matrix-Factorisation via $\ell_1$-Minimisation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dictionary Identification - Sparse Matrix-Factorisation via $\ell_1$-Minimisation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dictionary Identification - Sparse Matrix-Factorisation via $\ell_1$-Minimisation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-442990