A complete characterization of optimal dictionaries for least squares representation
This work addresses a theoretical gap in dictionary learning for Euclidean spaces, offering a foundational solution for applications requiring efficient data representation, though it is incremental relative to sparse methods.
The paper tackles the problem of finding optimal dictionaries for least squares representation by minimizing the average ℓ₂-norm of coefficients, providing a complete characterization of ℓ₂-optimal dictionaries and polynomial-time algorithms for construction.
Dictionaries are collections of vectors used for representations of elements in Euclidean spaces. While recent research on optimal dictionaries is focussed on providing sparse (i.e., $\ell_0$-optimal,) representations, here we consider the problem of finding optimal dictionaries such that representations of samples of a random vector are optimal in an $\ell_2$-sense. For us, optimality of representation is equivalent to minimization of the average $\ell_2$-norm of the coefficients used to represent the random vector, with the lengths of the dictionary vectors being specified a priori. With the help of recent results on rank-$1$ decompositions of symmetric positive semidefinite matrices and the theory of majorization, we provide a complete characterization of $\ell_2$-optimal dictionaries. Our results are accompanied by polynomial time algorithms that construct $\ell_2$-optimal dictionaries from given data.