Analysis of Iterative Hard Thresholding for Support Recovery in the High-Dimensional and Noisy Case for Gaussian X Matrices

• Activity Number: 476
• Type: Contributed
• Date/Time: Wednesday, August 3, 2011 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Antony Joseph*+ and Andrew Barron
• Companies: Yale University and Yale University
• Keywords: high dimensional regression ; greedy algorithms ; Lasso ; AWGN channel ; compressed sensing

Abstract

Abstract: Problems of high dimensional regression are becoming increasingly popular nowadays. Greedy algorithms such as Forward Stepwise Regression and Orthogonal Greedy Algorithm (OGA) are commonly used. These algorithms are known to not necessarily select the best subset of explanatory variables. Nevertheless, recent results have shown that they can perform well in function approximation and prediction. It is only very recently that Greedy algorithm began to be analyzed for support recovery with control on pair-wise correlations between variables even when the number of variables p is large compared to the sample size n. Here we analyze a variant of the OGA. We get sharp controls on the relationships between sample size, dimension and sparsity for exact or near exact support recovery. The results specialize to a high dimensional regression setup for a communications system to perform at rates arbitrarily close to capacity for a Gaussian noise channel.