Low noise sensitivity analysis of Lq-minimization in oversampled systems
arXiv:1705.03533
Abstract
The class of Lq-regularized least squares (LQLS) are considered for estimating a p-dimensional vector \b{eta} from its n noisy linear observations y = X\b{eta}+w. The performance of these schemes are studied under the high-dimensional asymptotic setting in which p grows linearly with n. In this asymptotic setting, phase transition diagrams (PT) are often used for comparing the performance of different estimators. Although phase transition analysis is shown to provide useful information for compressed sensing, the fact that it ignores the measurement noise not only limits its applicability in many application areas, but also may lead to misunderstandings. For instance, consider a linear regression problem in which n > p and the signal is not exactly sparse. If the measurement noise is ignored in such systems, regularization techniques, such as LQLS, seem to be irrelevant since even the ordinary least squares (OLS) returns the exact solution. However, it is well-known that if n is not much larger than p then the regularization techniques improve the performance of OLS. In response to this limitation of PT analysis, we consider the low-noise sensitivity analysis. We show that this analysis framework (i) reveals the advantage of LQLS over OLS, (ii) captures the difference between different LQLS estimators even when n > p, and (iii) provides a fair comparison among different estimators in high signal-to-noise ratios. As an application of this framework, we will show that under mild conditions LASSO outperforms other LQLS even when the signal is dense. Finally, by a simple transformation we connect our low-noise sensitivity framework to the classical asymptotic regime in which n/p goes to infinity and characterize how and when regularization techniques offer improvements over ordinary least squares, and which regularizer gives the most improvement when the sample size is large.
References in corpus (10)
- Simultaneous analysis of Lasso and Dantzig selector
- Message Passing Algorithms for Compressed Sensing
- Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results
- Various thresholds for -optimization in compressed sensing
- Block-length dependent thresholds in block-sparse compressed sensing
- Precise Error Analysis of Regularized M-estimators in High-dimensions
- Variance Breakdown of Huber (M)-estimators:
- Which bridge estimator is optimal for variable selection?
- Robustness in sparse linear models: relative efficiency based on robust approximate message passing
- Overcoming The Limitations of Phase Transition by Higher Order Analysis of Regularization Techniques