CIF: Small: Structured Signal Modeling via Nonconvex Optimization

Columbia University, New York NY

Investigators

Abstract

Many problems in modern signal processing and data analysis can be cast as searching for a structured, low-dimensional model for observed data. Images, audio signals, video sequences, and more, can be modeled as sparse in an appropriate dictionary. Scientific data, from neural spike sorting to microscopy, can be modeled as superpositions of characteristic patterns, translated over space. Learned data representations yield excellent results on a variety of classical problems in image processing and vision, and are also play a crucial role in recent breakthroughs in signal classification and computational scientific discovery. In contrast, much less is known theoretically about the properties of learned representations, and of algorithms for learning them. This project develops theory and dedicated optimization algorithms, which are guaranteed, under appropriate conditions, to provide good representations for observed signals. The investigators study theoretical and computational aspects of a family of problems, including sparse dictionary learning, sparse deconvolution, and convolutional dictionary learning. The natural formulations of these problems are nonconvex. The goal of the project is to develop geometric insights into these nonconvex problems, and to use these insights to develop recovery theory and scalable, efficient algorithms. Key challenges include understanding the properties of local and global minima, and developing efficient algorithms that avoid stalling near saddle points. The algorithms are demonstrated on real signal data arising in image classification and scientific imaging.