Name
Abstract | ||
|---|---|---|
We consider a learning problem of identifying a dictionary matrix D ∈ RM×N from a sample set of M dimensional vectors Y ∈ RM×P = N-1/2DX ∈ RM×P, where X ∈ RN×p is a sparse matrix in which the density of non-zero entries is 0 <; ρ <; 1. In particular, we focus on the minimum sample size Pc (sample complexity) necessary for perfectly identifying D of the optimal learning scheme when D and X are independently generated from certain distributions. By using the replica method of statistical mechanics, we show that Pc ~ O(N) holds as long as α = M/N > ρ is satisfied in the limit of N → ∞. Our analysis also implies that the posterior distribution given Y is condensed only at the correct dictionary D when the compression rate α is greater than a certain critical value αM(p). This suggests that belief propagation may allow us to learn D with a low computational complexity using O(N) samples. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/ISIT.2013.6620310 | international symposium on information theory |
Keywords | Field | DocType |
Bayes methods,computational complexity,learning (artificial intelligence),sparse matrices,statistical mechanics,vectors,Bayesian optimal dictionary learning,M dimensional vectors,compression rate,dictionary matrix identification,nonzero entry density,posterior distribution,replica method,sample complexity,sparse matrix,sparse representations,statistical mechanics | Information theory,Discrete mathematics,Combinatorics,Data compression ratio,Computer science,Matrix (mathematics),Posterior probability,Sparse matrix,Computational complexity theory,Bayesian probability,Belief propagation | Journal |
Volume | ISSN | Citations |
abs/1301.6199 | 2157-8095 | 3 |
PageRank | References | Authors |
0.45 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ayaka Sakata | 1 | 24 | 3.93 |
| Yoshiyuki Kabashima | 2 | 136 | 27.83 |