Accelerated Sparse Recovery via Gradient Descent with Nonlinear Conjugate Gradient Momentum

Mengqi Hu; Yifei Lou; Bao Wang; Ming Yan; Xiu Yang; Qiang Ye

doi:10.1007/s10915-023-02148-y

Accelerated Sparse Recovery via Gradient Descent with Nonlinear Conjugate Gradient Momentum

Mengqi Hu, Yifei Lou, Bao Wang, Ming Yan, Xiu Yang, Qiang Ye

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

This paper applies an idea of adaptive momentum for the nonlinear conjugate gradient to accelerate optimization problems in sparse recovery. Specifically, we consider two types of minimization problems: a (single) differentiable function and the sum of a non-smooth function and a differentiable function. In the first case, we adopt a fixed step size to avoid the traditional line search and establish the convergence analysis of the proposed algorithm for a quadratic problem. This acceleration is further incorporated with an operator splitting technique to deal with the non-smooth function in the second case. We use the convex ℓ₁ and the nonconvex ℓ₁- ℓ₂ functionals as two case studies to demonstrate the efficiency of the proposed approaches over traditional methods.

Original language	English
Article number	33
Journal	Journal of Scientific Computing
Volume	95
Issue number	1
DOIs	https://doi.org/10.1007/s10915-023-02148-y
State	Published - Apr 2023

Bibliographical note

Funding Information:
YL acknowledges the support from NSF CAREER DMS-1846690. BW is supported by NSF DMS-1924935, DMS-1952339, DMS-2152762, and DMS-2208361. BW also acknowledges support from the office of Science of the department of energy under grant number DE-SC0021142 and DE-SC0002722. MY was supported by the NSF DMS-2012439 and Shenzhen Science and Technology Program ZDSYS20211021111415025. XY acknowledges the support from NSF CAREER DMS-2143915. XY was also partly supported by DOE, Office of Science, Office of Advanced Scientific Computing Research (ASCR) as part of Multifaceted Mathematics for Rare, Extreme Events in Complex Energy and Environment Systems (MACSER). QY acknowledges the support from the NSF grant DMS-1821144.

Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

Keywords

Accelerated gradient momentum
Convergence rate
Fixed step size
Operator splitting

ASJC Scopus subject areas

Software
Theoretical Computer Science
Numerical Analysis
Engineering (all)
Computational Mathematics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1007/s10915-023-02148-y

Cite this

@article{2e415670e73a49eab246cad8b3dcd665,

title = "Accelerated Sparse Recovery via Gradient Descent with Nonlinear Conjugate Gradient Momentum",

abstract = "This paper applies an idea of adaptive momentum for the nonlinear conjugate gradient to accelerate optimization problems in sparse recovery. Specifically, we consider two types of minimization problems: a (single) differentiable function and the sum of a non-smooth function and a differentiable function. In the first case, we adopt a fixed step size to avoid the traditional line search and establish the convergence analysis of the proposed algorithm for a quadratic problem. This acceleration is further incorporated with an operator splitting technique to deal with the non-smooth function in the second case. We use the convex ℓ1 and the nonconvex ℓ1- ℓ2 functionals as two case studies to demonstrate the efficiency of the proposed approaches over traditional methods.",

keywords = "Accelerated gradient momentum, Convergence rate, Fixed step size, Operator splitting",

author = "Mengqi Hu and Yifei Lou and Bao Wang and Ming Yan and Xiu Yang and Qiang Ye",

note = "Funding Information: YL acknowledges the support from NSF CAREER DMS-1846690. BW is supported by NSF DMS-1924935, DMS-1952339, DMS-2152762, and DMS-2208361. BW also acknowledges support from the office of Science of the department of energy under grant number DE-SC0021142 and DE-SC0002722. MY was supported by the NSF DMS-2012439 and Shenzhen Science and Technology Program ZDSYS20211021111415025. XY acknowledges the support from NSF CAREER DMS-2143915. XY was also partly supported by DOE, Office of Science, Office of Advanced Scientific Computing Research (ASCR) as part of Multifaceted Mathematics for Rare, Extreme Events in Complex Energy and Environment Systems (MACSER). QY acknowledges the support from the NSF grant DMS-1821144. Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2023",

month = apr,

doi = "10.1007/s10915-023-02148-y",

language = "English",

volume = "95",

number = "1",

}

TY - JOUR

T1 - Accelerated Sparse Recovery via Gradient Descent with Nonlinear Conjugate Gradient Momentum

AU - Hu, Mengqi

AU - Lou, Yifei

AU - Wang, Bao

AU - Yan, Ming

AU - Yang, Xiu

AU - Ye, Qiang

N1 - Funding Information: YL acknowledges the support from NSF CAREER DMS-1846690. BW is supported by NSF DMS-1924935, DMS-1952339, DMS-2152762, and DMS-2208361. BW also acknowledges support from the office of Science of the department of energy under grant number DE-SC0021142 and DE-SC0002722. MY was supported by the NSF DMS-2012439 and Shenzhen Science and Technology Program ZDSYS20211021111415025. XY acknowledges the support from NSF CAREER DMS-2143915. XY was also partly supported by DOE, Office of Science, Office of Advanced Scientific Computing Research (ASCR) as part of Multifaceted Mathematics for Rare, Extreme Events in Complex Energy and Environment Systems (MACSER). QY acknowledges the support from the NSF grant DMS-1821144. Publisher Copyright: © 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2023/4

Y1 - 2023/4

N2 - This paper applies an idea of adaptive momentum for the nonlinear conjugate gradient to accelerate optimization problems in sparse recovery. Specifically, we consider two types of minimization problems: a (single) differentiable function and the sum of a non-smooth function and a differentiable function. In the first case, we adopt a fixed step size to avoid the traditional line search and establish the convergence analysis of the proposed algorithm for a quadratic problem. This acceleration is further incorporated with an operator splitting technique to deal with the non-smooth function in the second case. We use the convex ℓ1 and the nonconvex ℓ1- ℓ2 functionals as two case studies to demonstrate the efficiency of the proposed approaches over traditional methods.

AB - This paper applies an idea of adaptive momentum for the nonlinear conjugate gradient to accelerate optimization problems in sparse recovery. Specifically, we consider two types of minimization problems: a (single) differentiable function and the sum of a non-smooth function and a differentiable function. In the first case, we adopt a fixed step size to avoid the traditional line search and establish the convergence analysis of the proposed algorithm for a quadratic problem. This acceleration is further incorporated with an operator splitting technique to deal with the non-smooth function in the second case. We use the convex ℓ1 and the nonconvex ℓ1- ℓ2 functionals as two case studies to demonstrate the efficiency of the proposed approaches over traditional methods.

KW - Accelerated gradient momentum

KW - Convergence rate

KW - Fixed step size

KW - Operator splitting

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

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

U2 - 10.1007/s10915-023-02148-y

DO - 10.1007/s10915-023-02148-y

M3 - Article

AN - SCOPUS:85150173124

SN - 0885-7474

VL - 95

JO - Journal of Scientific Computing

JF - Journal of Scientific Computing

IS - 1

M1 - 33

ER -

Accelerated Sparse Recovery via Gradient Descent with Nonlinear Conjugate Gradient Momentum

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this