# A Preconditioner for A Primal-Dual Newton Conjugate Gradient Method for Compressed Sensing Problems

@article{Dassios2015APF, title={A Preconditioner for A Primal-Dual Newton Conjugate Gradient Method for Compressed Sensing Problems}, author={Ioannis K. Dassios and Kimon Fountoulakis and Jacek Gondzio}, journal={SIAM J. Sci. Comput.}, year={2015}, volume={37} }

In this paper we are concerned with the solution of compressed sensing (CS) problems where the signals to be recovered are sparse in coherent and redundant dictionaries. We extend the primal-dual Newton Conjugate Gradient method (pdNCG) in [T. F. Chan, G. H. Golub, and P. Mulet, SIAM J. Sci. Comput., 20 (1999), pp. 1964--1977] to CS problems. We provide an inexpensive and provably effective preconditioning technique for linear systems using pdNCG. Numerical results are presented on CS problems… Expand

#### Figures, Tables, and Topics from this paper

#### 54 Citations

New Preconditioners Applied to Linear Programming and the Compressive Sensing Problems

- Computer Science
- 2020

A new preconditioner is presented, in the construction of which the fact that close to a solution the authors can split the variables into two groups and the matrices satisfy certain properties is exploited, as demonstrated in a method known from the literature. Expand

A Primal Douglas–Rachford Splitting Method for the Constrained Minimization Problem in Compressive Sensing

- Mathematics, Computer Science
- Circuits Syst. Signal Process.
- 2017

Numerical results show that the developed algorithm performs better than the popular NESTA and LADMM (inexact ADMM) in terms of accuracy and run time for large-scale sparse signal recovery. Expand

Preconditioned Nonlinear Conjugate Gradient methods based on a modified secant equation

- Computer Science, Mathematics
- Appl. Math. Comput.
- 2018

The results of an extended numerical experience using large scale CUTEst problems is reported, showing that the preconditioners proposed can considerably improve the performance of NCG methods. Expand

A fast conjugate gradient algorithm with active set prediction for ℓ1 optimization

- Computer Science, Mathematics
- Optim. Methods Softw.
- 2019

An active set identification technique that has a strong ability to accurately identify the zero components in a neighbourhood of an optimal solution for solving optimization problems is developed and it is shown that the method is globally convergent. Expand

On a Sparse Approximation of Compressible Signals

- Computer Science
- Circuits Syst. Signal Process.
- 2020

A relation between mean square error of the recovered signal and the residual error is explored and the proposed quality metric provides fine control over the approximation process of the compressible signals in the mean sense even though it has not been directly designed for use in compressed sensing methods such as OMP. Expand

Non-interior-point smoothing Newton method for CP revisited and its application to support vector machines

- Mathematics
- 2019

Non-interior-point smoothing Newton method (SNM) for optimization have been widely studied for over three decades. SNM is a popular approach for solving small- and medium-scale complementarity… Expand

Krylov-Simplex method that minimizes the residual in $\ell_1$-norm or $\ell_\infty$-norm

- Mathematics, Computer Science
- 2021

Two variants of a Krylov-Simplex iterative method that combines Krylov and simplex iterations to minimize the residual r = b−Ax are presented and the solution with the least absolute residuals is found. Expand

Joint-block-sparsity for efficient 2-D DOA estimation with multiple separable observations

- Computer Science
- Multidimens. Syst. Signal Process.
- 2019

A new sparsity structure is introduced that can be used to model the optimization problem in case of multiple data snapshots and multiple separable observations where the dictionary can be decomposed into two parts: azimuth and elevation dictionaries, called joint-block-sparsity. Expand

Compressive Imaging: Structure, Sampling, Learning

- 2021

Accurate, robust and fast image reconstruction is a critical task in many scientific, industrial and medical applications. Over the last decade, image reconstruction has been revolutionized by the… Expand

Restarted primal-dual Newton conjugate gradient method for enhanced spatial resolution of reconstructed cone-beam X-ray luminescence computed tomography images.

- Medicine, Physics
- Physics in medicine and biology
- 2020

The results demonstrate that compared with conventional reconstruction methods, the proposed re-pdNCG method can accurately and efficiently resolve the adjacent NPs with the least relative error. Expand

#### References

SHOWING 1-10 OF 30 REFERENCES

Matrix-free interior point method for compressed sensing problems

- Mathematics, Computer Science
- Math. Program. Comput.
- 2014

An approach which redesigns IPM to avoid the need to explicitly formulate (and store) the Newton equation systems is used, and the special features of the signal processing matrices within the matrix-free IPM are exploited. Expand

An Augmented Lagrangian Approach to the Constrained Optimization Formulation of Imaging Inverse Problems

- Computer Science, Mathematics
- IEEE Transactions on Image Processing
- 2011

This paper proposes a new efficient algorithm to handle one class of constrained problems (often known as basis pursuit denoising) tailored to image recovery applications and shows that the proposed algorithm is a strong contender for the state-of-the-art. Expand

Compressed Sensing with Coherent and Redundant Dictionaries

- Computer Science, Mathematics
- ArXiv
- 2010

A condition on the measurement/sensing matrix is introduced, which is a natural generalization of the now well-known restricted isometry property, and which guarantees accurate recovery of signals that are nearly sparse in (possibly) highly overcomplete and coherent dictionaries. Expand

Templates for convex cone problems with applications to sparse signal recovery

- Mathematics, Computer Science
- Math. Program. Comput.
- 2011

A general framework for solving a variety of convex cone problems that frequently arise in signal processing, machine learning, statistics, and other fields, and results showing that the smooth and unsmoothed problems are sometimes formally equivalent are applied. Expand

A Second-Order Method for Strongly Convex L1-Regularization Problems

- Mathematics
- 2013

In this paper a robust second-order method is developed for the solution of strongly convex l1-regularized problems. The main aim is to make the proposed method as inexpensive as possible, while even… Expand

NESTA: A Fast and Accurate First-Order Method for Sparse Recovery

- Computer Science, Mathematics
- SIAM J. Imaging Sci.
- 2011

A smoothing technique and an accelerated first-order algorithm are applied and it is demonstrated that this approach is ideally suited for solving large-scale compressed sensing reconstruction problems and is robust in the sense that its excellent performance across a wide range of problems does not depend on the fine tuning of several parameters. Expand

A Nonlinear Primal-Dual Method for Total Variation-Based Image Restoration

- Mathematics, Computer Science
- SIAM J. Sci. Comput.
- 1999

A new method for solving total variation (TV) minimization problems in image restoration by introducing an additional variable for the flux quantity appearing in the gradient of the objective function, which can be interpreted as the normal vector to the level sets of the image u. Expand

An efficient augmented Lagrangian method with applications to total variation minimization

- Mathematics, Computer Science
- Comput. Optim. Appl.
- 2013

An algorithm for solving a class of equality-constrained non-smooth optimization problems (chiefly but not necessarily convex programs) with a particular structure that effectively combines an alternating direction technique with a nonmonotone line search to minimize the augmented Lagrangian function at each iteration is proposed. Expand

The restricted isometry property and its implications for compressed sensing

- Mathematics
- 2008

Abstract It is now well-known that one can reconstruct sparse or compressible signals accurately from a very limited number of measurements, possibly contaminated with noise. This technique known as… Expand

Primal dual algorithms for convex models and applications to image restoration, registration and nonlocal inpainting

- Mathematics
- 2010

The main subject of this dissertation is a class of practical algorithms for minimizing convex non-differentiable functionals coming from image processing problems defined as variational models. This… Expand