A Primal Dual Active Set with Continuation Algorithm for the ℓ⁰-Regularized Optimization Problem

2014/03/03 by Jiao, Yuling, Jin, Bangti, Lu, Xiliang · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1403.0515

Abstract

We develop a primal dual active set with continuation algorithm for solving the ℓ⁰-regularized least-squares problem that frequently arises in compressed sensing. The algorithm couples the the primal dual active set method with a continuation strategy on the regularization parameter. At each inner iteration, it first identifies the active set from both primal and dual variables, and then updates the primal variable by solving a (typically small) least-squares problem defined on the active set, 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, the finite step global convergence of the algorithm is established. Extensive numerical examples are presented to illustrate the efficiency and accuracy of the algorithm and the convergence analysis.

Cited by

• ℓ₀-Norm Multiobjective Optimization Models Motivated by Applications to Proton Therapy

Related

• A Unified Primal Dual Active Set Algorithm for Nonconvex Sparse Recovery
• Alternating direction algorithms for ℓ₀ regularization in compressed sensing
• Alternating Direction Algorithms for ℓ₁-Problems in Compressive Sensing
• A Homotopy Coordinate Descent Optimization Method for l₀-Norm Regularized Least Square Problem
• Efficient ℓ_q Minimization Algorithms for Compressive Sensing Based on Proximity Operator