ParNes: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals (Q372857): Difference between revisions

This article develops an algorithm for underdetermined least squares problems with 1-norm constraint on the solution. It relies on a modified Nestorev method that periodically updates the prox-center optimally and renders the proposed method almost always linearly convergent. The method is then applied to find the minimum 1-norm solution to an underdetermined least squares problem when teamed with the Pareto root finder. Numerical tests show that these methods achieve comparable numerical results in comparable time for such a problem in image processing and other areas of application.

0 references

reviewed by

Frank Uhlig

0 references

zbMATH Keywords

least squares problem

0 references

Nesterov's method

0 references

basis pursuit

0 references

denoising problem

0 references

Pareto root finder

0 references

convex minimization

0 references

numerical example

0 references

algorithm

0 references

1-norm constraint

0 references

minimum 1-norm solution

0 references

image processing

0 references

describes a project that uses

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Fast Image Recovery Using Variable Splitting and Constrained Optimization

0 references

Two-Point Step Size Gradient Methods

0 references

A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems

0 references

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

0 references

Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing

0 references

Nonmonotone Spectral Projected Gradient Methods on Convex Sets

0 references

The restricted isometry property and its implications for compressed sensing

0 references

The Dantzig selector: statistical estimation when $p$ is much larger than $n$. (With discussions and rejoinder).

0 references

Stable signal recovery from incomplete and inaccurate measurements

0 references

Atomic Decomposition by Basis Pursuit

0 references

Inexact Newton Methods

0 references

For most large underdetermined systems of linear equations the minimal 𝓁<sub>1</sub>‐norm solution is also the sparsest solution

0 references

Least angle regression. (With discussion)

0 references

Sparse Reconstruction by Separable Approximation

0 references

Pathwise coordinate optimization

0 references

On Sparse Representations in Arbitrary Redundant Bases

0 references

Q4198056

0 references

Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence

0 references

Sparse Approximate Solutions to Linear Systems

0 references

Smooth minimization of non-smooth functions

0 references

A new approach to variable selection in least squares problems

0 references

Submersions and preimages of sets of measure zero

0 references

Q4864293

0 references

Just relax: convex programming methods for identifying sparse signals in noise

0 references

Probing the Pareto Frontier for Basis Pursuit Solutions

0 references

A Fast Algorithm for Sparse Reconstruction Based on Shrinkage, Subspace Optimization, and Continuation

0 references

Identifiers

zbMATH Open document ID

1284.65055

0 references

DOI

10.1007/s11075-012-9668-5

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:372857

@@ Property / review text @@
+This article develops an algorithm for underdetermined least squares problems with 1-norm constraint on the solution. It relies on a modified Nestorev method that periodically updates the prox-center optimally and renders the proposed method almost always linearly convergent. The method is then applied to find the minimum 1-norm solution to an underdetermined least squares problem when teamed with the Pareto root finder. Numerical tests show that these methods achieve comparable numerical results in comparable time for such a problem in image processing and other areas of application.
+Normal rank
@@ Property / reviewed by @@
+Frank Uhlig
@@ Property / reviewed by: Frank Uhlig / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+F20
@@ Property / Mathematics Subject Classification ID: 65F20 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+F50
@@ Property / Mathematics Subject Classification ID: 65F50 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+K05
@@ Property / Mathematics Subject Classification ID: 65K05 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C25
@@ Property / Mathematics Subject Classification ID: 90C25 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+D18
@@ Property / Mathematics Subject Classification ID: 65D18 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6217379
@@ Property / zbMATH DE Number: 6217379 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+least squares problem
@@ Property / zbMATH Keywords: least squares problem / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+Nesterov's method
@@ Property / zbMATH Keywords: Nesterov's method / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+basis pursuit
@@ Property / zbMATH Keywords: basis pursuit / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+denoising problem
@@ Property / zbMATH Keywords: denoising problem / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+Pareto root finder
@@ Property / zbMATH Keywords: Pareto root finder / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+convex minimization
@@ Property / zbMATH Keywords: convex minimization / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+numerical example
@@ Property / zbMATH Keywords: numerical example / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+algorithm
@@ Property / zbMATH Keywords: algorithm / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+-norm constraint
@@ Property / zbMATH Keywords: 1-norm constraint / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+minimum 1-norm solution
@@ Property / zbMATH Keywords: minimum 1-norm solution / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+image processing
@@ Property / zbMATH Keywords: image processing / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+FPC_AS
@@ Property / describes a project that uses: FPC_AS / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+NESTA
@@ Property / describes a project that uses: NESTA / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+Sparco
@@ Property / describes a project that uses: Sparco / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+ParNes
@@ Property / describes a project that uses: ParNes / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+SPGL1
@@ Property / describes a project that uses: SPGL1 / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+PDCO
@@ Property / describes a project that uses: PDCO / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+Publication
@@ Property / MaRDI profile type: Publication / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2108005121
@@ Property / OpenAlex ID: W2108005121 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.0492
@@ Property / arXiv ID: 0911.0492 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Image Recovery Using Variable Splitting and Constrained Optimization
+Normal rank
@@ Property / cites work @@
+Two-Point Step Size Gradient Methods
@@ Property / cites work: Two-Point Step Size Gradient Methods / rank @@
+Normal rank
@@ Property / cites work @@
+A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
+Normal rank
@@ Property / cites work @@
+NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
+Normal rank
@@ Property / cites work @@
+Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
+Normal rank
@@ Property / cites work @@
+Nonmonotone Spectral Projected Gradient Methods on Convex Sets
+Normal rank
@@ Property / cites work @@
+The restricted isometry property and its implications for compressed sensing
+Normal rank
@@ Property / cites work @@
+The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
+Normal rank
@@ Property / cites work @@
+Stable signal recovery from incomplete and inaccurate measurements
+Normal rank
@@ Property / cites work @@
+Atomic Decomposition by Basis Pursuit
@@ Property / cites work: Atomic Decomposition by Basis Pursuit / rank @@
+Normal rank
@@ Property / cites work @@
+Inexact Newton Methods
@@ Property / cites work: Inexact Newton Methods / rank @@
+Normal rank
@@ Property / cites work @@
+For most large underdetermined systems of linear equations the minimal 𝓁<sub>1</sub>‐norm solution is also the sparsest solution
+Normal rank
@@ Property / cites work @@
+Least angle regression. (With discussion)
@@ Property / cites work: Least angle regression. (With discussion) / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse Reconstruction by Separable Approximation
@@ Property / cites work: Sparse Reconstruction by Separable Approximation / rank @@
+Normal rank
@@ Property / cites work @@
+Pathwise coordinate optimization
@@ Property / cites work: Pathwise coordinate optimization / rank @@
+Normal rank
@@ Property / cites work @@
+On Sparse Representations in Arbitrary Redundant Bases
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
+Normal rank
@@ Property / cites work @@
+Sparse Approximate Solutions to Linear Systems
@@ Property / cites work: Sparse Approximate Solutions to Linear Systems / rank @@
+Normal rank
@@ Property / cites work @@
+Smooth minimization of non-smooth functions
@@ Property / cites work: Smooth minimization of non-smooth functions / rank @@
+Normal rank
@@ Property / cites work @@
+A new approach to variable selection in least squares problems
+Normal rank
@@ Property / cites work @@
+Submersions and preimages of sets of measure zero
@@ Property / cites work: Submersions and preimages of sets of measure zero / rank @@
+Normal rank
@@ Property / cites work @@
+Q4864293
@@ Property / cites work: Q4864293 / rank @@
+Normal rank
@@ Property / cites work @@
+Just relax: convex programming methods for identifying sparse signals in noise
+Normal rank
@@ Property / cites work @@
+Probing the Pareto Frontier for Basis Pursuit Solutions
+Normal rank
@@ Property / cites work @@
+A Fast Algorithm for Sparse Reconstruction Based on Shrinkage, Subspace Optimization, and Continuation
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:372857