A Primal Dual Active Set Algorithm with Continuation for Compressed Sensing

The success of compressed sensing relies essentially on the ability to efficiently find an approximately sparse solution to an under-determined linear system. In this paper, we developed an efficient algorithm for the sparsity promoting \(\ell_1\)-regularized least squares problem by coupling the pr...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2013-12
Main Authors: Fan, Qibin, Jiao, Yuling, Lu, Xiliang
Format: Article
Language:English
Subjects:
Algorithms
Bayesian analysis
Convergence
Grey markets
Least squares method
Parameters
Regularization
Sherman Antitrust Act 1890-US
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The success of compressed sensing relies essentially on the ability to efficiently find an approximately sparse solution to an under-determined linear system. In this paper, we developed an efficient algorithm for the sparsity promoting \(\ell_1\)-regularized least squares problem by coupling the primal dual active set strategy with a continuation technique (on the regularization parameter). In the active set strategy, we first determine the active set from primal and dual variables, and then update the primal and dual variables by solving a low-dimensional least square problem on the active set, which makes the algorithm very efficient. The continuation technique globalizes the convergence of the algorithm, with provable global convergence under restricted isometry property (RIP). Further, we adopt two alternative methods, i.e., a modified discrepancy principle and a Bayesian information criterion, to choose the regularization parameter. Numerical experiments indicate that our algorithm is very competitive with state-of-the-art algorithms in terms of accuracy and efficiency.
ISSN:2331-8422
DOI:10.48550/arxiv.1312.7039