Sample complexity bounds for dictionary learning from vector- and tensor-valued data

During the last decade, dictionary learning has emerged as one of the most powerful methods for data-driven extraction of features from data. While the initial focus on dictionary learning had been from an algorithmic perspective, recent years have seen an increasing interest in understanding the theoretical underpinnings of dictionary learning. Many such results rely on the use of information-theoretic analytical tools and help understand the fundamental limitations of different dictionary learning algorithms. This talk focuses on the theoretical aspects of dictionary learning and summarizes existing results that deal with dictionary learning from both vector-valued data and tensor-valued (i.e., multiway) data, which are defined as data having multiple modes. These results are primarily stated in terms of lower and upper bounds on the sample complexity of dictionary learning, defined as the number of samples needed to identify or reconstruct the true dictionary underlying data from noiseless or noisy samples, respectively. In addition to highlighting the effects of different parameters on the sample complexity of dictionary learning, this talk also brings out the potential advantages of dictionary learning from tensor data and concludes with a set of open problems that remain unaddressed for dictionary learning.

(This talk is based on a book chapter with the same title that is slated to appear in the edited volume "information-Theoretic Methods in Data Science," edited by M. R. D. Rodrigues and Y. C. Eldar.)
Waheed U. Bajwa is an associate professor in the Department of Electrical and Computer Engineering and an associate member of the graduate faculty of the Department of Statistics and Biostatistics at Rutgers University–New Brunswick. His research interests include statistical signal processing, high-dimensional statistics, machine learning, harmonic analysis, inverse problems, and networked systems. Dr. Bajwa has received a number of awards in his career including the Army Research Office Young Investigator Award (2014), the National Science Foundation CAREER Award (2015), Rutgers University’s Presidential Merit Award (2016), Rutgers Engineering Governing Council ECE Professor of the Year Award (2016, 2017), and Rutgers University’s Presidential Fellowship for Teaching Excellence (2017). He is a co-investigator on the work that received the Cancer Institute of New Jersey’s Gallo Award for Scientific Excellence in 2017, a co-author on papers that received Best Student Paper Awards at IEEE IVMSP 2016 and IEEE CAMSAP 2017 workshops, and a Member of the Class of 2015 National Academy of Engineering Frontiers of Engineering Education Symposium. He is currently serving as a Senior Area Editor for IEEE Signal Processing Letters, an Associate Editor for IEEE Transactions on Signal and Information Processing over Networks, and an elected member of Big Data Special Interest Group as well as SAM and SPCOM Technical Committees of IEEE Signal Processing Society.