Atomic Norms

Many signals and systems that we commonly acquire and analyze can be expressed as linear combinations of a few basic building blocks. For example, RADAR signals can be decomposed into a sum of elementary propagating waves, metabolic dynamics can be analyzed as sums of multi-index data arrays, and aggregate rankings of sports teams can be written as sums of a few permutations. Atomic norms provide a framework for estimating these sorts of signals with very few sensors or very fast acquisition times by solving convex optimization problems.

In the atomic norm project, we are interested in exploring the fundamental limitations of optimization methods in data analysis and investigating how these theoretical techniques mesh with the myriad of complex systems and signals that we encounter in practice.

Relevant papers and reports

The atomic norm paper: The Convex Algebraic Geometry of Linear Inverse Problems. Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, and Alan S. Willsky. Foundations of Computational Mathematics. 12(6):805–849, 2012.

Extensions of the generic theory

Atomic Norm Denoising with Applications to Line Spectral Estimation. Badri Bhaskar and Benjamin Recht. IEEE Transactions on Signal Processing. 61(23):5987–5999, 2013.

Simple Bounds for Recovering Low-complexity Models. Emmanuel Candès and Benjamin Recht. Mathematical Programming. Series A. 141(1):577–589. 2013.

Isometric sketching of arbitrary sets via the Restricted Isometry Property. Samet Oymak, Mahdi Soltanolkotabi, and Benjamin Recht. Preprint, 2015.

Sparse Recovery Over Continuous Dictionaries: Just Discretize. Gongguo Tang, Badri Narayan Bhaskar, and Benjamin Recht. In Proceedings of the Asilomar Conference on Signals, Systems, and Computers, 2013.

The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems. Nicholas Boyd, Geoffrey Schiebinger, and Benjamin Recht. Preprint, 2015.

Line-spectrum, superresolution, and compressive sensing

Super-Resolution Without Separation. Geoffrey Schiebinger, Elina Robeva and Benjamin Recht. Preprint, 2015.

Near Minimax Line Spectral Estimation. Gongguo Tang, Badri Narayan Bhaskar, and Benjamin Recht. IEEE Transactions on Information Theory. 61(1):499–512, 2015.

Compressed Sensing off the Grid. Gongguo Tang, Badri Narayan Bhaskar, Parikshit Shah, and Benjamin Recht. IEEE Transactions on Information Theory. 59(11)7465–7490, 2013.

Other applications

Blind Deconvolution using Convex Programming. Ali Ahmed, Benjamin Recht, and Justin Romberg. IEEE Transactions on Information Theory. 60(3):1711–1732, 2014.

Linear System Identification via Atomic Norm Regularization. Parikshit Shah, Badri Narayan Bhaskar, Gongguo Tang, and Benjamin Recht. In Proceedings of the 51st Annual Conference on Decision and Control, 2012.

Measurement Bounds for Exact Recovery of Structured Sparse Signals. Nikhil Rao, Benjamin Recht, and Robert Nowak. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, 2012.

Probability of Unique Integer Solution to a System of Linear Equations. Olvi Mangasarian and Benjamin Recht. European Journal of Operational Research. 214(1):27—30, 2011.