Optimal Dictionary for Least Squares Representation
Mohammed Rayyan Sheriff, Debasish Chatterjee.
Year: 2017, Volume: 18, Issue: 107, Pages: 1−28
Abstract
Dictionaries are collections of vectors used for the representation of a class of vectors in Euclidean spaces. Recent research on optimal dictionaries is focused on constructing dictionaries that offer sparse representations, i.e., ℓ0-optimal representations. Here we consider the problem of finding optimal dictionaries with which representations of a given class of vectors is optimal in an ℓ2-sense: optimality of representation is defined as attaining the minimal average ℓ2-norm of the coefficients used to represent the vectors in the given class. With the help of recent results on rank-1 decompositions of symmetric positive semidefinite matrices, we provide an explicit description of ℓ2-optimal dictionaries as well as their algorithmic constructions in polynomial time.