Optimal dictionary for least squares representation
This work addresses a fundamental problem in signal processing and machine learning for researchers and practitioners, offering a novel approach to dictionary optimization, though it is incremental as it builds on existing ℓ₂-norm methods.
The paper tackles the problem of finding optimal dictionaries for least squares representation, focusing on minimizing the average ℓ₂-norm of coefficients, and provides an explicit description and polynomial-time algorithmic construction for such dictionaries.
Dictionaries are collections of vectors used for representations of random vectors in Euclidean spaces. Recent research on optimal dictionaries is focused on constructing dictionaries that offer sparse representations, i.e., $\ell_0$-optimal representations. Here we consider the problem of finding optimal dictionaries with which representations of samples of a random vector are optimal in an $\ell_2$-sense: optimality of representation is defined as attaining the minimal average $\ell_2$-norm of the coefficients used to represent the random vector. With the help of recent results on rank-$1$ decompositions of symmetric positive semidefinite matrices, we provide an explicit description of $\ell_2$-optimal dictionaries as well as their algorithmic constructions in polynomial time.