Dictionary Learning With Few Samples and Matrix Concentration

DOI10.1109/TIT.2016.2517011MaRDI QIDQ2976985zbMATH OpenOpenAlexFDO

Authors Kyle Luh, Van Vu

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Let $A$ be an $nimesn$ matrix, $X$ be an $nimesp$ matrix and $Y=AX$. A challenging and important problem in data analysis, motivated by dictionary learning and other practical problems, is to recover both $A$ and $X$, given $Y$. Under normal circumstances, it is clear that this problem is underdetermined. However, in the case when $X$ is sparse and random, Spielman, Wang and Wright showed that one can recover both $A$ and $X$ efficiently from $Y$ with high probability, given that $p$ (the number of samples) is sufficiently large. Their method works for $pgeC{n}^{2}lo{g}^{2}n$ and they conjectured that $pgeCnlogn$ suffices. The bound $nlogn$ is sharp for an obvious information theoretical reason. In this paper, we show that $pgeCnlo{g}^{4}n$ suffices, matching the conjectural bound up to a polylogarithmic factor. The core of our proof is a theorem concerning $l_1$ concentration of random matrices, which is of independent interest. Our proof of the concentration result is based on two ideas. The first is an economical way to apply the union bound. The second is a refined version of Bernstein's concentration inequality for the sum of independent variables. Both have nothing to do with random matrices and are applicable in general settings.

Cited in

(8)

• Dictionary Learning With BLOTLESS Update
• Dictionary Learning for Two-Dimensional Kendall Shapes
• Sparse random matrices have simple spectrum
• Dictionary Learning on Grassmann Manifolds
• A novel dictionary learning method based on total least squares approach with application in high dimensional biological data
• Dictionary learning based on nonnegative matrix factorization using parallel coordinate descent
• Minimax Lower Bounds on Dictionary Learning for Tensor Data
• Trainlets: Dictionary Learning in High Dimensions

This page was built for publication: Dictionary Learning With Few Samples and Matrix Concentration

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