American Institute of Mathematical Sciences

Advanced
August  2009, 3(3): 487-503. doi: 10.3934/ipi.2009.3.487

Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm

Yingying Li 1, and  Stanley Osher 1,

1. 

UCLA Mathematics Department, Box 951555, Los Angeles, CA 90095-1555, United States, United States

Received  February 2009 Revised  June 2009 Published  July 2009

We propose a fast algorithm for solving the Basis Pursuit problem, minu $\{|u|_1\: \Au=f\}$, which has application to compressed sensing. We design an efficient method for solving the related unconstrained problem minu $E(u) = |u|_1 + \lambda \||Au-f\||^2_2$ based on a greedy coordinate descent method. We claim that in combination with a Bregman iterative method, our algorithm will achieve a solution with speed and accuracy competitive with some of the leading methods for the basis pursuit problem.
Keywords: Bregman iteration, Basis Pursuit, shrinkage, greedy sweep, constrained problem..
Mathematics Subject Classification: Primary: 90C25; Secondary: 65K0.
Citation: Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems & Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487
[1]

Rafał Kamocki, Marek Majewski. On the continuous dependence of solutions to a fractional Dirichlet problem. The case of saddle points. Discrete & Continuous Dynamical Systems - B, 2014, 19 (8) : 2557-2568. doi: 10.3934/dcdsb.2014.19.2557
[2]

Gabriella Pinzari. Global Kolmogorov tori in the planetary $\boldsymbol N$-body problem. Announcement of result. Electronic Research Announcements, 2015, 22: 55-75. doi: 10.3934/era.2015.22.55
[3]

Abbas Ja'afaru Badakaya, Aminu Sulaiman Halliru, Jamilu Adamu. Game value for a pursuit-evasion differential game problem in a Hilbert space. Journal of Dynamics & Games, 2022, 9 (1) : 1-12. doi: 10.3934/jdg.2021019
[4]

Sergei A. Avdonin, Boris P. Belinskiy. On the basis properties of the functions arising in the boundary control problem of a string with a variable tension. Conference Publications, 2005, 2005 (Special) : 40-49. doi: 10.3934/proc.2005.2005.40
[5]

Zhuoyi Xu, Yong Xia, Deren Han. On box-constrained total least squares problem. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 439-449. doi: 10.3934/naco.2020043
[6]

Shaoyong Lai, Qichang Xie. A selection problem for a constrained linear regression model. Journal of Industrial & Management Optimization, 2008, 4 (4) : 757-766. doi: 10.3934/jimo.2008.4.757
[7]

Stephan Didas, Joachim Weickert. Integrodifferential equations for continuous multiscale wavelet shrinkage. Inverse Problems & Imaging, 2007, 1 (1) : 47-62. doi: 10.3934/ipi.2007.1.47
[8]

Yunmei Chen, Xianqi Li, Yuyuan Ouyang, Eduardo Pasiliao. Accelerated bregman operator splitting with backtracking. Inverse Problems & Imaging, 2017, 11 (6) : 1047-1070. doi: 10.3934/ipi.2017048
[9]

Jing Qin, Shuang Li, Deanna Needell, Anna Ma, Rachel Grotheer, Chenxi Huang, Natalie Durgin. Stochastic greedy algorithms for multiple measurement vectors. Inverse Problems & Imaging, 2021, 15 (1) : 79-107. doi: 10.3934/ipi.2020066
[10]

Lili Chang, Wei Gong, Guiquan Sun, Ningning Yan. PDE-constrained optimal control approach for the approximation of an inverse Cauchy problem. Inverse Problems & Imaging, 2015, 9 (3) : 791-814. doi: 10.3934/ipi.2015.9.791
[11]

Sören Bartels, Marijo Milicevic. Iterative finite element solution of a constrained total variation regularized model problem. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1207-1232. doi: 10.3934/dcdss.2017066
[12]

Ye Tian, Shucherng Fang, Zhibin Deng, Qingwei Jin. Cardinality constrained portfolio selection problem: A completely positive programming approach. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1041-1056. doi: 10.3934/jimo.2016.12.1041
[13]

Helin Guo, Huan-Song Zhou. Properties of the minimizers for a constrained minimization problem arising in Kirchhoff equation. Discrete & Continuous Dynamical Systems, 2021, 41 (3) : 1023-1050. doi: 10.3934/dcds.2020308
[14]

Biao Qu, Naihua Xiu. A relaxed extragradient-like method for a class of constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 645-654. doi: 10.3934/jimo.2007.3.645
[15]

Yuan Tan, Qingyuan Cao, Lan Li, Tianshi Hu, Min Su. A chance-constrained stochastic model predictive control problem with disturbance feedback. Journal of Industrial & Management Optimization, 2021, 17 (1) : 67-79. doi: 10.3934/jimo.2019099
[16]

Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775
[17]

Yafeng Li, Guo Sun, Yiju Wang. A smoothing Broyden-like method for polyhedral cone constrained eigenvalue problem. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 529-537. doi: 10.3934/naco.2011.1.529
[18]

P.K. Newton, M. Ruith, E. Upchurch. The constrained planar N-vortex problem: I. Integrability. Discrete & Continuous Dynamical Systems - B, 2005, 5 (1) : 137-152. doi: 10.3934/dcdsb.2005.5.137
[19]

Jianlin Jiang, Shun Zhang, Su Zhang, Jie Wen. A variational inequality approach for constrained multifacility Weber problem under gauge. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1085-1104. doi: 10.3934/jimo.2017091
[20]

Antonio Sedeño-Noda, José M. Gutiérrez. Solving a constrained economic lot size problem by ranking efficient production policies. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021102

2020 Impact Factor: 1.639

Tools

Metrics

  • PDF downloads (803)
  • HTML views (0)
  • Cited by (62)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy