Abstract
Dictionary learning, the problem of recovering a sparsely used matrix D ∈ RM×K and N independent K×1 s-sparse vectors X ∈ RK×N from samples of the form Y = DX, is of increasing importance to applications in signal processing and data science. Early papers on provable dictionary learning identified that one can detect whether two samples yi, yj share a common dictionary element by testing if their inner product (correlation) exceeds a certain threshold: | 〈yi, yj〉 | > τ. These correlation-based methods work well _when sparsity is small, but suffer from declining performance when sparsity grows faster than √M; as a result, such methods were abandoned in the search for dictionary learning algorithms when sparsity is nearly linear in M. In this paper, we revisit correlation-based dictionary learning. Instead of seeking to recover individual dictionary atoms, we employ a spectral method to recover the subspace spanned by the dictionary atoms in the support of each sample. This approach circumvents the primary challenge encountered by previous correlation methods, namely that when sharing information between two samples it is difficult to tell which dictionary element the two samples share. We prove that under a suitable random model the resulting algorithm recovers dictionaries in polynomial time for sparsity linear in M up to log factors. Our results improve on the best known methods by achieving a decaying error bound in dimension M; the best previously known results for the overcomplete (K > M) setting achieve polynomial time in the linear regime only for constant error bounds. Numerical simulations confirm our results.
Original language | English (US) |
---|---|
Pages (from-to) | 1516-1554 |
Number of pages | 39 |
Journal | Proceedings of Machine Learning Research |
Volume | 201 |
State | Published - 2023 |
Event | 34th International Conference onAlgorithmic Learning Theory, ALT 2023 - Singapore, Singapore Duration: Feb 20 2023 → Feb 23 2023 |
All Science Journal Classification (ASJC) codes
- Artificial Intelligence
- Software
- Control and Systems Engineering
- Statistics and Probability