Sparse estimation via lower-order penalty optimization methods in high-dimensional linear regression

Abstract

The lower-order penalty optimization methods, including the ℓq minimization method and the ℓq regularization method (0 < q≤ 1) , have been widely applied to find sparse solutions of linear regression problems and gained successful applications in various mathematics and applied science fields. In this paper, we aim to investigate statistical properties of the ℓq penalty optimization methods with randomly noisy observations and a deterministic/random design. For this purpose, we introduce a general q-Restricted Eigenvalue Condition (REC) and provide its sufficient conditions in terms of several widely-used regularity conditions such as sparse eigenvalue condition, restricted isometry property, and mutual incoherence property. By virtue of the q-REC, we exhibit the ℓ2 recovery bounds of order O(ϵ2) and O(λ22-qs) for the ℓq minimization method and the ℓq regularization method, respectively, with high probability for either deterministic or random designs. The results in this paper are nonasymptotic and only assume the weak q-REC. The preliminary numerical results verify the established statistical properties and demonstrate the advantages of the ℓq penalty optimization methods over existing sparse optimization methods.