We develop a primaldualactiveset with continuation algorithm for solving the l(0)-regularized least-squares problem that frequently arises in compressed sensing. The algorithm couples the primaldualactiveset met...
详细信息
We develop a primaldualactiveset with continuation algorithm for solving the l(0)-regularized least-squares problem that frequently arises in compressed sensing. The algorithm couples the primaldualactiveset method with a continuation strategy on the regularization parameter. At each inner iteration, it first identifies the activeset from both primal and dual variables, and then updates the primal variable by solving a (typically small) least-squares problem defined on the activeset, from which the dual variable can be updated explicitly. Under certain conditions on the sensing matrix, i.e., mutual incoherence property or restricted isometry property, and the noise level, a finite step global convergence of the overall algorithm is established. Extensive numerical examples are presented to illustrate the efficiency and accuracy of the algorithm and its convergence behavior. (C) 2014 Elsevier Inc. All rights reserved.
Variable selection and parameter estimation are fundamental and important problems in high dimensional data analysis. In this paper, we employ the hard thresholding regularization method [1] to handle these issues und...
详细信息
Variable selection and parameter estimation are fundamental and important problems in high dimensional data analysis. In this paper, we employ the hard thresholding regularization method [1] to handle these issues under the framework of high-dimensional and sparse linear regression model. Theoretically, we establish a sharp non-asymptotic estimation error for the global solution and further show that the support of the global solution coincides with the target support with high probability. Motivated by the KKT condition, we propose a primal dual active set algorithm (PDAS) to solve the minimization problem, and show that the proposed PDAS algorithm is essentially a generalized Newton method, which guarantees that the proposed PDAS algorithm will converge fast if a good initial value is provided. Furthermore, we propose a sequential version of the PDAS algorithm (SPDAS) with a warm-start strategy to choose the initial value adaptively. The most significant advantage of the proposed procedure is its fast calculation speed. Extensive numerical studies demonstrate that the proposed method performs well on variable selection and estimation accuracy. It has favorable exhibition over the existing methods in terms of computational speed. As an illustration, we apply the proposed method to a breast cancer gene expression data set.
Truncated L1 regularization proposed by Fan in[5],is an approximation to the L0 regularization in high-dimensional sparse *** this work,we prove the non-asymptotic error bound for the global optimal solution to the tr...
详细信息
Truncated L1 regularization proposed by Fan in[5],is an approximation to the L0 regularization in high-dimensional sparse *** this work,we prove the non-asymptotic error bound for the global optimal solution to the truncated L1 regularized linear regression problem and study the support recovery ***,a primal dual active set algorithm(PDAS)for variable estimation and selection is *** with continuation by a warm-start strategy leads to a primaldualactiveset with continuation algorithm(PDASC).Data-driven parameter selection rules such as cross validation,BIC or voting method can be applied to select a proper regularization *** application of the proposed method is demonstrated by applying it to simulation data and a breast cancer gene expression data set(bcTCGA).
In this paper, we propose using l(q)-constrained least-squares to decode n dimensional signals with sparsity level s from m noisy and sign flipped 1-bit quantized measurements. We prove that the solution of the propos...
详细信息
In this paper, we propose using l(q)-constrained least-squares to decode n dimensional signals with sparsity level s from m noisy and sign flipped 1-bit quantized measurements. We prove that the solution of the proposed decoder approximates the target signals with the precision delta up to a positive constant with high probability as long as m >= O(s(2/q-1) log n/delta(2)). A weighted primal-dualactivesetalgorithm with continuation is utilized for computing the proposed estimator by combining the data driven majority vote tuning parameter selection rule. Comprehensive numerical simulations indicate that our proposed decoder is robust to noise and sign flips and performs better than state-of-the-art methods. (C) 2020 Elsevier B.V. All rights reserved.
In this paper we investigate finite element approximation of optimal control problem governed by space fractional diffusion equation with control constraints. The control variable is approximated by piecewise constant...
详细信息
In this paper we investigate finite element approximation of optimal control problem governed by space fractional diffusion equation with control constraints. The control variable is approximated by piecewise constant. Regularity estimate for the control problem is proved based on the first order optimality system and a priori error estimates for the state, the adjoint state and the control variables are derived. Due to the nonlocal property of fractional derivative, which will leads to a full stiff matrix, we develop a fast primal dual active set algorithm for the control problem. Numerical examples are given to illustrate the theoretical findings and the efficiency of the fast algorithm.
In 1-bit compressive sensing (1-bit CS) where a target signal is coded into a binary measurement, one goal is to recover the signal from noisy and quantized samples. Mathematically, the 1-bit CS model reads y = eta ci...
详细信息
In 1-bit compressive sensing (1-bit CS) where a target signal is coded into a binary measurement, one goal is to recover the signal from noisy and quantized samples. Mathematically, the 1-bit CS model reads y = eta circle dot sign(Psi x* + epsilon), where x* is an element of R-n;y is an element of R-m, Psi is an element of R(mx)n, and epsilon is the random error before quantization and eta is an element of R-n is a random vector modeling the sign flips. Due to the presence of nonlinearity, noise, and sign flips, it is quite challenging to decode from the 1-bit CS. In this paper, we consider a least squares approach under the overdetermined and underdetermined settings. For m > n, we show that, up to a constant c, with high probability, the least squares solution xls approximates x* with precision ffi as long as m >= (O) over tilde (n/delta(2)). For m < n, we prove that, up to a constant c, with high probability, the l(1)-regularized least-squares solution xl(1) lies in the ball with center x* and radius delta provided that m >= O (s log n/delta(2)) and parallel to x parallel to(0) := s < m. We introduce a Newton type method, the so-called primal and dualactiveset (PDAS) algorithm, to solve the nonsmooth optimization problem. The PDAS possesses the property of one-step convergence. It only requires solving a small least squares problem on the activeset. Therefore, the PDAS is extremely e ffi cient for recovering sparse signals through continuation. We propose a novel regularization parameter selection rule which does not introduce any extra computational overhead. Extensive numerical experiments are presented to illustrate the robustness of our proposed model and the e ffi ciency of our algorithm.
In thispaper, we propose and analyze a novel approach for group sparse recovery. It is based on regularized least squares with an l(0)(l(2)) penalty, which penalizes the number of nonzero groups. One distinct feature ...
详细信息
In thispaper, we propose and analyze a novel approach for group sparse recovery. It is based on regularized least squares with an l(0)(l(2)) penalty, which penalizes the number of nonzero groups. One distinct feature of the approach is that it has the built-in decorrelation mechanism within each group, and thus, can handle challenging strong inner-group correlation. We provide a complete analysis of the regularized model, e.g., existence of a global minimizer, invariance property, support recovery, and properties of block coordinatewise minimizers. Further, the regularized problem admits an efficient primal dual active set algorithm with a provable finite-step global convergence. At each iteration, it involves solving a least-squares problem on the activeset only, and exhibits a fast local convergence, which makes the method extremely efficient for recovering group sparse signals. Extensive numerical experiments are presented to illustrate salient features of the model and the efficiency and accuracy of the algorithm. A comparative study indicates its competitiveness with existing approaches.
暂无评论