Sparse Estimation via Lower-order Penalty Optimization Methods in High-dimensional Linear Regression

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 ℓ₂ recovery bounds of order O(ϵ²) 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.