期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 57, 期 10, 页码 6976-6994出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2011.2165799
关键词
Compressed sensing; minimax techniques; regression analysis
资金
- National Science Foundation (NSF) [DMS-0605165, DMS-0907362]
- NSF [SES-0835531]
- National Natural Science Foundation of China (NSFC) [60628102]
- Microsoft Research Asia (MSRA)
- Sloan Foundation
- Air Force Office of Scientific Research (AFOSR) [FA9550-09-1-0466]
- Berkeley Graduate Fellowship
Consider the high- dimensional linear regression model y = X beta* + w, where y is an element of R-n is an observation vector, X is an element of R-n x d is a design matrix with, d > n, beta* is an element of R-d is an unknown regression vector, and w similar to N(0, sigma I-2) is additive Gaussian noise. This paper studies the minimax rates of convergence for estimating beta* in either l(2)-loss and l(2)-prediction loss, assuming that beta* belongs to an l(q)-ball B-q (R-q) for some q is an element of [0, 1]. It is shown that under suitable regularity conditions on the design matrix, the minimax optimal rate in l(2)-loss and l(2)-prediction loss scales as. Theta (R-q (log d/n)(1-q/2) The analysis in this paper reveals that conditions on the design matrix enter into the rates for l(2)-error and l(2)-prediction error in complementary ways in the upper and lower bounds. Our proofs of the lower bounds are information theoretic in nature, based on Fano's inequality and results on the metric entropy of the balls B-q (R-q), whereas our proofs of the upper bounds are constructive, involving direct analysis of least squares over l(q)-balls. For the special case, q = 0 corresponding to models with an exact sparsity constraint, our results show that although computationally efficient l(1)-based methods can achieve the minimax rates up to constant factors, they require slightly stronger assumptions on the design matrix than optimal algorithms involving least- squares over the l(0)-ball.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据