In this paper, we present a novel yet simple homotopy proximal mapping algorithm for compressive sensing. The algorithm adopts a simple proximal mapping of the @math norm at each iteration and gradually reduces the regularization parameter for the @math norm. We prove a global linear convergence of the proposed homotopy proximal mapping (HPM) algorithm for solving compressive sensing under three different settings (i) sparse signal recovery under noiseless measurements, (ii) sparse signal recovery under noisy measurements, and (iii) nearly-sparse signal recovery under sub-gaussian noisy measurements. In particular, we show that when the measurement matrix satisfies Restricted Isometric Properties (RIP), our theoretical results in settings (i) and (ii) almost recover the best condition on the RIP constants for compressive sensing. In addition, in setting (iii), our results for sparse signal recovery are better than the previous results, and furthermore our analysis explicitly exhibits that more observations lead to not only more accurate recovery but also faster convergence. Compared with previous studies on linear convergence for sparse signal recovery, our algorithm is simple and efficient, and our results are better and provide more insights. Finally our empirical studies provide further support for the proposed homotopy proximal mapping algorithm and verify the theoretical results.
Recently, several algorithms exhibit global linear convergence for the BPDN problem. @cite_2 studied an optimization problem ) for statistical recovery. They used a different update where @math , and @math is a parameter related to the restricted smoothness of the loss function. They proved a global linear convergence of the above update with @math for finding a solution up to the statistical tolerance. @cite_0 studied a proximal-gradient homotopy gradient method for solving ). They iteratively solve the problem ) by the proximal gradient descent with a decreasing regularization parameter @math and an increasing accuracy at each stage, and use the solution obtained at each stage to warm start the next stage. A global linear convergence was also established.
@cite_0 @cite_2
2161227280 1874232560
We consider solving the @math -regularized least-squares ( @math -LS) problem in the context of sparse recovery for applications such as compressed sensing. The standard proximal gradient method, also known as iterative soft-thresholding when applied to this problem, has low computational cost per iteration but a rather slow convergence rate. Nevertheless, when the solution is sparse, it often exhibits fast linear convergence in the final stage. We exploit the local linear convergence using a homotopy continuation strategy, i.e., we solve the @math -LS problem for a sequence of decreasing values of the regularization parameter, and use an approximate solution at the end of each stage to warm start the next stage. Although similar strategies have been studied in the literature, there have been no theoretical analysis of their global iteration complexity. This paper shows that under suitable assumptions for sparse recovery, the proposed homotopy strategy ensures that all iterates along the homotopy sol... Many statistical M-estimators are based on convex optimization problems formed by the weighted sum of a loss function with a norm-based regularizes We analyze the convergence rates of first-order gradient methods for solving such problems within a high-dimensional framework that allows the data dimension d to grow with (and possibly exceed) the sample size n. This high-dimensional structure precludes the usual global assumptions— namely, strong convexity and smoothness conditions—that underlie classical optimization analysis. We define appropriately restricted versions of these conditions, and show that they are satisfied with high probability for various statistical models. Under these conditions, our theory guarantees that Nesterov's first-order method [12] has a globally geometric rate of convergence up to the statistical precision of the model, meaning the typical Euclidean distance between the true unknown parameter θ* and the optimal solution ^θ. This globally linear rate is substantially faster than previous analyses of global convergence for specific methods that yielded only sublinear rates. Our analysis applies to a wide range of M-estimators and statistical models, including sparse linear regression using Lasso (l1-regularized regression), group Lasso, block sparsity, and low-rank matrix recovery using nuclear norm regularization. Overall, this result reveals an interesting connection between statistical precision and computational efficiency in high-dimensional estimation.