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

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.
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]

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

[4]

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

[5]

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

[6]

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

[7]

John A. Morgan. Interception in differential pursuit/evasion games. Journal of Dynamics & Games, 2016, 3 (4) : 335-354. doi: 10.3934/jdg.2016018

[8]

Inês Cruz, M. Esmeralda Sousa-Dias. Reduction of cluster iteration maps. Journal of Geometric Mechanics, 2014, 6 (3) : 297-318. doi: 10.3934/jgm.2014.6.297

[9]

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

[10]

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

[11]

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

[12]

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

[13]

Jianlin Jiang, Shun Zhang, Su Zhang, Jie Wen. A variational inequality approach for constrained multifacility Weber problem under gauge. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1-20. doi: 10.3934/jimo.2017091

[14]

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

[15]

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

[16]

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

[17]

Wenye Ma, Stanley Osher. A TV Bregman iterative model of Retinex theory. Inverse Problems & Imaging, 2012, 6 (4) : 697-708. doi: 10.3934/ipi.2012.6.697

[18]

Miroslava Růžičková, Irada Dzhalladova, Jitka Laitochová, Josef Diblík. Solution to a stochastic pursuit model using moment equations. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 473-485. doi: 10.3934/dcdsb.2018032

[19]

David Maxwell. Kozlov-Maz'ya iteration as a form of Landweber iteration. Inverse Problems & Imaging, 2014, 8 (2) : 537-560. doi: 10.3934/ipi.2014.8.537

[20]

Martin D. Buhmann, Slawomir Dinew. Limits of radial basis function interpolants. Communications on Pure & Applied Analysis, 2007, 6 (3) : 569-585. doi: 10.3934/cpaa.2007.6.569

2016 Impact Factor: 1.094

Metrics

  • PDF downloads (11)
  • HTML views (0)
  • Cited by (37)

Other articles
by authors

[Back to Top]