SILO



The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group

3M

with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Simple Meets Optimal: Some New Results for Model Selection Using One-Step Thresholding

Waheed Bajwa, Postdoctoral Researcher, Duke University

Date and Time: Oct 13, 2010 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building

Abstract:

The problem of model selection arises in a number of contexts, such as subset selection in linear regression, estimation of structures in graphical models, and signal denoising. In this talk, I introduce a simple algorithm, termed one-step thresholding (OST) algorithm, for model-order agnostic model selection in linear inference problems. I utilize two geometric measures of coherence, namely, worst-case coherence and average coherence, among the columns of a design matrix to provide an in-depth analysis of OST for model selection. One of the key insights offered by the ensuing analysis is that OST can successfully carry out model selection even when methods based on convex optimization such as the lasso fail due to the rank deficiency of the submatrices of the design matrix. In particular, I show that OST has the ability to perform near-optimally for a number of generic (random or deterministic) matrices as long as the design matrix satisfies conditions that are easily computable in polynomial time. In addition, I talk about extensions of the OST model selection results to recovery of sparse signals. Finally, I present some findings into explicitly designing matrices with small average coherence, which is the key to guaranteeing that algorithms such as OST succeed.