2024/11/02 by Shujun Bi, Bi, Shujun, Yonghua Yang +2
Mathematics · #FOS: Mathematics #Statistical Methods and Inference #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2411.01237
openalex publication_date 2024/11/02 · openalex created_date 2024/11/14 · openalex updated_date 2026/07/28
For high dimensional sparse linear regression problems, we propose a sequential convex relaxation algorithm (iSCRA-TL1) by solving inexactly a sequence of truncated ℓ1-norm regularized minimization problems, in which the working index sets are constructed iteratively with an adaptive strategy. We employ the robust restricted null space property and sequential restricted null space property (rRNSP and rSRNSP) to provide the theoretical certificates of iSCRA-TL1. Specifically, under a mild rRNSP or rSRNSP, iSCRA-TL1 is shown to identify the support of the true r-sparse vector by solving at most r truncated ℓ1-norm regularized problems, and the ℓ1-norm error bound of its iterates from the oracle solution is also established. As a consequence, an oracle estimator of high-dimensional linear regression problems can be achieved by solving at most r + 1 truncated ℓ1-norm regularized problems. To the best of our knowledge, this is the first sequential convex relaxation algorithm to produce an oracle estimator under a weaker NSP condition within a specific number of steps, provided that the Lasso estimator lacks high quality, say, the supports of its first r largest (in modulus) entries do not coincide with those of the true vector.