Minimax lower bounds for Kronecker-structured dictionary learning
Minimax lower bounds for Kronecker-structured dictionary learning
复制标题
DOI：
10.1109/isit.2016.7541479
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Z. Shakeri;W. Bajwa;A. Sarwate
中科院分区：
文献类型：
--
作者：
Z. Shakeri;W. Bajwa;A. Sarwate
字典学习是估计提供测量/收集的信号或数据的稀疏表示的原子元素的集合的问题。本文通过证明极大极小风险的下界，发现了张量数据估计字典的样本复杂性的根本限制。这个下限取决于张量的维度和生成模型的参数。本文的重点是二阶张量数据，与基础的字典构造两个较小的字典和观测数据的字典原子通过白色高斯噪声观察到的稀疏线性组合的Kronecker产品。在这方面，本文提供了一个一般的最小最大风险的下限，并采用稀疏和高斯系数模型的等价结果的证明技术。报告的结果表明，张量数据的字典学习的样本复杂度可以显着低于非结构化数据。
Dictionary learning is the problem of estimating the collection of atomic elements that provide a sparse representation of measured/collected signals or data. This paper finds fundamental limits on the sample complexity of estimating dictionaries for tensor data by proving a lower bound on the minimax risk. This lower bound depends on the dimensions of the tensor and parameters of the generative model. The focus of this paper is on second-order tensor data, with the underlying dictionaries constructed by taking the Kronecker product of two smaller dictionaries and the observed data generated by sparse linear combinations of dictionary atoms observed through white Gaussian noise. In this regard, the paper provides a general lower bound on the minimax risk and also adapts the proof techniques for equivalent results using sparse and Gaussian coefficient models. The reported results suggest that the sample complexity of dictionary learning for tensor data can be significantly lower than that for unstructured data.