Title: A complete characterization of optimal dictionaries for least squares representation,
Abstract: 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.