A Convergent Fixed-Point Proximity Algorithm Accelerated by FISTA for the ℓ0 Sparse Recovery Problem

Xueying Zeng; Lixin Shen; Yuesheng Xu

doi:10.1007/978-3-319-91274-5_2

A Convergent Fixed-Point Proximity Algorithm Accelerated by FISTA for the ℓ₀ Sparse Recovery Problem

Xueying Zeng, Lixin Shen, Yuesheng Xu

Research output: Chapter in Book/Entry/Poem › Conference contribution

5 Scopus citations

Abstract

We propose an approximation model of the original ℓ₀ minimization model arising from various sparse signal recovery problems. The objective function of the proposed model uses the Moreau envelope of the ℓ₀ norm to promote the sparsity of the signal in a tight framelet system. This leads to a non-convex optimization problem involved the ℓ₀ norm. We identify a local minimizer of the proposed non-convex optimization problem with a global minimizer of a related convex optimization problem. Based on this identification, we develop a two stage algorithm for solving the proposed non-convex optimization problem and study its convergence. Moreover, we show that FISTA can be employed to speed up the convergence rate of the proposed algorithm to reach the optimal convergence rate of O(1 ∕ k²). We present numerical results to confirm the theoretical estimate.

Original language	English (US)
Title of host publication	Mathematics and Visualization
Editors	Xue-Cheng Tai, Egil Bae, Marius Lysaker
Publisher	Springer Heidelberg
Pages	27-45
Number of pages	19
ISBN (Electronic)	9783319912745
ISBN (Print)	9783319912738, 9783319912738, 9783540250326, 9783540250760, 9783540332749, 9783540886051, 9783642150135, 9783642216077, 9783642231742, 9783642273421, 9783642341403, 9783642543005
DOIs	https://doi.org/10.1007/978-3-319-91274-5_2
State	Published - 2018
Event	International conference on Imaging, Vision and Learning Based on Optimization and PDEs, IVLOPDE 2016 - Bergen, Norway Duration: Aug 29 2016 → Sep 2 2016

Publication series

Name	Mathematics and Visualization
Volume	0
ISSN (Print)	1612-3786
ISSN (Electronic)	2197-666X

Other

Other	International conference on Imaging, Vision and Learning Based on Optimization and PDEs, IVLOPDE 2016
Country/Territory	Norway
City	Bergen
Period	8/29/16 → 9/2/16

ASJC Scopus subject areas

Modeling and Simulation
Geometry and Topology
Computer Graphics and Computer-Aided Design
Applied Mathematics

Access to Document

10.1007/978-3-319-91274-5_2

Cite this

A Convergent Fixed-Point Proximity Algorithm Accelerated by FISTA for the ℓ₀ Sparse Recovery Problem. / Zeng, Xueying; Shen, Lixin; Xu, Yuesheng.
Mathematics and Visualization. ed. / Xue-Cheng Tai; Egil Bae; Marius Lysaker. Springer Heidelberg, 2018. p. 27-45 (Mathematics and Visualization; Vol. 0).

Research output: Chapter in Book/Entry/Poem › Conference contribution

Zeng, X, Shen, L & Xu, Y 2018, A Convergent Fixed-Point Proximity Algorithm Accelerated by FISTA for the ℓ₀ Sparse Recovery Problem. in X-C Tai, E Bae & M Lysaker (eds), Mathematics and Visualization. Mathematics and Visualization, vol. 0, Springer Heidelberg, pp. 27-45, International conference on Imaging, Vision and Learning Based on Optimization and PDEs, IVLOPDE 2016, Bergen, Norway, 8/29/16. https://doi.org/10.1007/978-3-319-91274-5_2

@inproceedings{73f2d372cdaf4a4da3b178ce55e0d870,

title = "A Convergent Fixed-Point Proximity Algorithm Accelerated by FISTA for the ℓ0 Sparse Recovery Problem",

abstract = "We propose an approximation model of the original ℓ0 minimization model arising from various sparse signal recovery problems. The objective function of the proposed model uses the Moreau envelope of the ℓ0 norm to promote the sparsity of the signal in a tight framelet system. This leads to a non-convex optimization problem involved the ℓ0 norm. We identify a local minimizer of the proposed non-convex optimization problem with a global minimizer of a related convex optimization problem. Based on this identification, we develop a two stage algorithm for solving the proposed non-convex optimization problem and study its convergence. Moreover, we show that FISTA can be employed to speed up the convergence rate of the proposed algorithm to reach the optimal convergence rate of O(1 ∕ k2). We present numerical results to confirm the theoretical estimate.",

author = "Xueying Zeng and Lixin Shen and Yuesheng Xu",

note = "Funding Information: Fig. 2.1 The effects of using FISTA on the convergence and acceleration effects of the algorithms (blue dashed: Algorithm (2.21), red solid: using FISTA in (2.21)) Acknowledgements The author Xueying Zeng is supported by the Natural Science Foundation of China (No. 11701538, 11771408) and the Fundamental Research Funds for the Central Universities (No. 201562012). Both Lixin Shen and Yuesheng Xu were supported in part by the US National Science Foundation under Grant DMS-1522332. The author Yuesheng Xu is supported in part by the Special Project on High-performance Computing under the National Key R&D Program (No. 2016YFB0200602), and by the Natural Science Foundation of China under grants 11471013 and 11771464. Publisher Copyright: {\textcopyright} 2018, Springer International Publishing AG, part of Springer Nature.; International conference on Imaging, Vision and Learning Based on Optimization and PDEs, IVLOPDE 2016 ; Conference date: 29-08-2016 Through 02-09-2016",

year = "2018",

doi = "10.1007/978-3-319-91274-5_2",

language = "English (US)",

isbn = "9783319912738",

series = "Mathematics and Visualization",

publisher = "Springer Heidelberg",

pages = "27--45",

editor = "Xue-Cheng Tai and Egil Bae and Marius Lysaker",

booktitle = "Mathematics and Visualization",

address = "Germany",

}

TY - GEN

T1 - A Convergent Fixed-Point Proximity Algorithm Accelerated by FISTA for the ℓ0 Sparse Recovery Problem

AU - Zeng, Xueying

AU - Shen, Lixin

AU - Xu, Yuesheng

N1 - Funding Information: Fig. 2.1 The effects of using FISTA on the convergence and acceleration effects of the algorithms (blue dashed: Algorithm (2.21), red solid: using FISTA in (2.21)) Acknowledgements The author Xueying Zeng is supported by the Natural Science Foundation of China (No. 11701538, 11771408) and the Fundamental Research Funds for the Central Universities (No. 201562012). Both Lixin Shen and Yuesheng Xu were supported in part by the US National Science Foundation under Grant DMS-1522332. The author Yuesheng Xu is supported in part by the Special Project on High-performance Computing under the National Key R&D Program (No. 2016YFB0200602), and by the Natural Science Foundation of China under grants 11471013 and 11771464. Publisher Copyright: © 2018, Springer International Publishing AG, part of Springer Nature.

PY - 2018

Y1 - 2018

N2 - We propose an approximation model of the original ℓ0 minimization model arising from various sparse signal recovery problems. The objective function of the proposed model uses the Moreau envelope of the ℓ0 norm to promote the sparsity of the signal in a tight framelet system. This leads to a non-convex optimization problem involved the ℓ0 norm. We identify a local minimizer of the proposed non-convex optimization problem with a global minimizer of a related convex optimization problem. Based on this identification, we develop a two stage algorithm for solving the proposed non-convex optimization problem and study its convergence. Moreover, we show that FISTA can be employed to speed up the convergence rate of the proposed algorithm to reach the optimal convergence rate of O(1 ∕ k2). We present numerical results to confirm the theoretical estimate.

AB - We propose an approximation model of the original ℓ0 minimization model arising from various sparse signal recovery problems. The objective function of the proposed model uses the Moreau envelope of the ℓ0 norm to promote the sparsity of the signal in a tight framelet system. This leads to a non-convex optimization problem involved the ℓ0 norm. We identify a local minimizer of the proposed non-convex optimization problem with a global minimizer of a related convex optimization problem. Based on this identification, we develop a two stage algorithm for solving the proposed non-convex optimization problem and study its convergence. Moreover, we show that FISTA can be employed to speed up the convergence rate of the proposed algorithm to reach the optimal convergence rate of O(1 ∕ k2). We present numerical results to confirm the theoretical estimate.

UR - http://www.scopus.com/inward/record.url?scp=85057458740&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85057458740&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-91274-5_2

DO - 10.1007/978-3-319-91274-5_2

M3 - Conference contribution

AN - SCOPUS:85057458740

SN - 9783319912738

SN - 9783540250326

SN - 9783540250760

SN - 9783540332749

SN - 9783540886051

SN - 9783642150135

SN - 9783642216077

SN - 9783642231742

SN - 9783642273421

SN - 9783642341403

SN - 9783642543005

T3 - Mathematics and Visualization

SP - 27

EP - 45

BT - Mathematics and Visualization

A2 - Tai, Xue-Cheng

A2 - Bae, Egil

A2 - Lysaker, Marius

PB - Springer Heidelberg

T2 - International conference on Imaging, Vision and Learning Based on Optimization and PDEs, IVLOPDE 2016

Y2 - 29 August 2016 through 2 September 2016

ER -