A complete characterization of optimal dictionaries for least squares representation

DOI10.1016/J.LAA.2020.05.011MaRDI QIDQ2187393zbMATH OpenOpenAlexFDO

Authors Mohammed Rayyan Sheriff, Debasish Chatterjee

Publication date 2 June 2020

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.06763

zbMATH Keywords

\( \ell_2\)-optimal dictionaryframe theorymajorizationoptimization

Mathematics Subject Classification ID

General harmonic expansions, frames (42C15) General topics in artificial intelligence (68T01) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Dynamic programming (90C39) Controllability (93B05) Linear systems in control theory (93C05)

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., $el{l}_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 $el{l}_2$-sense. For us, optimality of representation is equivalent to minimization of the average $el{l}_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 $el{l}_2$-optimal dictionaries. Our results are accompanied by polynomial time algorithms that construct $el{l}_2$-optimal dictionaries from given data.

Recommendations

• Optimal dictionary for least squares representation
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Optimal non-linear models for sparsity and sampling
• scientific article; zbMATH DE number 2079345
• Sparse representations in unions of bases

Cites work

• An Extremum Property of Sums of Eigenvalues
• Analysis and optimization of certain qualities of controllability and observability for linear dynamical systems
• Calculus of variations and optimal control theory. A concise introduction
• Doubly Stochastic Matrices and the Diagonal of a Rotation Matrix
• Functional analysis, calculus of variations and optimal control
• scientific article; zbMATH DE number 1095138 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 5064374 (Why is no real title available?)
• scientific article; zbMATH DE number 2235418 (Why is no real title available?)
• scientific article; zbMATH DE number 3073200 (Why is no real title available?)
• Matrix theory. Basic results and techniques
• Optimal dictionary for least squares representation
• The Pythagorean Theorem: I. The finite case

Cited in

(5)

• Euclidean distances and least squares problems for a given set of vectors
• scientific article; zbMATH DE number 4155862 (Why is no real title available?)
• Optimal dictionary for least squares representation
• On some deterministic dictionaries supporting sparsity
• On the identifiability of overcomplete dictionaries via the minimisation principle underlying K-SVD

This page was built for publication: A complete characterization of optimal dictionaries for least squares representation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2187393)