Sparse Estimation with Strongly Correlated Variables

This talk considers the recently introduced ordered weighted L1 (OWL) regularizer for sparse estimation problems with correlated variables. We begin by reviewing several convex analysis results concerning the OWL regularizer, namely: that it is indeed a norm, its dual norm, efficient methods to compute the corresponding proximity operator and the Euclidean projection on an OWL ball. We will also show how the OWL norm can be explicitly written as an atomic norm, opening the door to the use of the conditional gradient (Frank-Wolfe) algorithm. In the analysis front, we show that OWL regularization automatically clusters strongly correlated variables, in the sense that the coefficients associated with such variables have equal estimated values. Furthermore, we characterize the statistical performance of OWL regularization for generative models in which certain clusters of regression variables are strongly (even perfectly) correlated, but variables in different clusters are uncorrelated. We show that if the true p-dimensional signal generating the data involves only s of the clusters, then O(s log p) samples suffice to accurately estimate the signal, regardless of the number of coefficients within the clusters. The estimation of s-sparse signals with completely independent variables requires just as many measurements. In other words, using the OWL we pay no price (in terms of the number of measurements) for the presence of strongly correlated variables.

This work was done in collaboration with Robert Nowak (University of Wisonsin-Madison, USA) and Xiangrong Zeng (IT and IST).

Mário Figueiredo

Mário A. T. Figueiredo received MSc and PhD degrees in electrical and computer engineering, both from Instituto Superior Técnico (IST), the engineering school of the University of Lisbon, in 1990 and 1994. He has been with the faculty of the Department of Electrical and Computer Engineering, IST, since 1994, where he is now a Full Professor. He is also area coordinator and group leader at Instituto de Telecomunicações, a private non-profit research institute. His research interests include image processing and analysis, machine learning, and optimization. Mário Figueiredo is a Fellow of the IEEE and of the IAPR; he received the 1995 Portuguese IBM Scientific Prize, the 2008 UTL/Santander-Totta Scientific Prize, the 2011 IEEE Signal Processing Society Best Paper Award, the 2014 IEEE W. R. G. Baker Award, and several conference best paper awards. His name is included in the Thomson Reuters' Highly Cited Researchers list. He is/was associate editor of several journals (e.g., IEEE Transactions on Image Processing, IEEE Transactions on Pattern Analysis and Machine Intelligence, SIAM Journal on Imaging Sciences, Journal of Mathematical Imaging and Vision) and served as organizer or program committee member of many international conferences.IT