\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Nomonotone spectral gradient method for sparse recovery

Abstract / Introduction Related Papers Cited by
  • In the paper, we present an algorithm framework for the more general problem of minimizing the sum $f(x)+\psi(x)$, where $f$ is smooth and $\psi$ is convex, but possible nonsmooth. At each step, the search direction of the algorithm is obtained by solving an optimization problem involving a quadratic term with diagonal Hessian and Barzilai-Borwein steplength plus $ \psi(x)$. The nonmonotone strategy is combined with -Borwein steplength to accelerate the convergence process. The method with the nomonotone line search techniques is showed to be globally convergent. In particular, if $f$ is convex, we show that the method shares a sublinear global rate of convergence. Moreover, if $f$ is strongly convex, we prove that the method converges R-linearly. Numerical experiments with compressive sense problems show that our approach is competitive with several known methods for some standard $l_2-l_1$ problems.
    Mathematics Subject Classification: 90C06, 90C25, 65Y20, 94A08.

    Citation:

    \begin{equation} \\ \end{equation}
  • [1]

    M. Afonso, J. Bioucas-Dias and M. Figueiredo, Fast image recovery using variable splitting and constrained optimization, IEEE Trans. Image Process., 19 (2010), 2345-2356.doi: 10.1109/TIP.2010.2047910.

    [2]

    S. Aybat and G. Iyengar, A first-order smoothed penalty method for compressed sensing, SIAM J. Optim., 21 (2011), 287-313.doi: 10.1137/090762294.

    [3]

    J. Barzilai and J. M. Borwein, Two point step size gradient methods, IMA J. Numer. Anal., 8 (1988), 141-148.doi: 10.1093/imanum/8.1.141.

    [4]

    A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), 183-202.doi: 10.1137/080716542.

    [5]

    A. Beck and Y. C. Eldar, Sparsity constrained nonlinear optimization: Optimality conditions and algorithms, SIAM J. Optim., 23 (2013), 1480-1509.doi: 10.1137/120869778.

    [6]

    J. M. Bioucas-Dias and M. A. T. Figueiredo, A new TwIST: Two-step iterative shrinkage/thresholding algorithms for image restoration, IEEE Trans. Image Process., 16 (2007), 2992-3004.doi: 10.1109/TIP.2007.909319.

    [7]

    E. G. Birgin, J. M. Martínez and M. Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim., 10 (2000), 1196-1121.doi: 10.1137/S1052623497330963.

    [8]

    D. Boley, Local linear convergence of the alternating direction method of multipliers on quadratic or linear program, SIAM J. Optim., 23 (2013), 2183-2207.doi: 10.1137/120878951.

    [9]

    A. M. Bruckstein, D. L. Donoho and M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., 51 (2009), 34-81.doi: 10.1137/060657704.

    [10]

    E. Candes and J. Romberg, $l_1$-magic: A collection of MATLAB Routines for Solving the Convex Optimization Programs Central to Compressive Sampling 2006 [Online]. Available from: http://www.acm.caltech.edu/l1magic/.

    [11]

    W. Y. Cheng and Z. X. Chen, Nonmonotone spectral method for large-scale symmetric nonlinear equations, Numer Algor., 62 (2013), 149-162.doi: 10.1007/s11075-012-9572-z.

    [12]

    I. Daubechies, M. Defrise and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57 (2004), 1413-1457.doi: 10.1002/cpa.20042.

    [13]

    Y.-H. Dai and R. Fletcher, Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming, Numer. Math., 100 (2005), 21-47.doi: 10.1007/s00211-004-0569-y.

    [14]

    Y.-H. Dai, W. W. Hager, K. Schittkowski and H. Zhang, The cyclic Barzilar-Borwein method for unconstrained optimization, IMA J. Numer. Anal., 26 (2006), 604-627.doi: 10.1093/imanum/drl006.

    [15]

    G. Davis, S. Mallat and M. Avellaneda, Greedy adaptive approximation, Constr Approx., 13 (1997), 57-98.doi: 10.1007/BF02678430.

    [16]

    D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306.doi: 10.1109/TIT.2006.871582.

    [17]

    D. Donoho, M. Elad and V. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Trans. Inform. Theory, 52 (2006), 6-18.doi: 10.1109/TIT.2005.860430.

    [18]

    E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), 201-213.doi: 10.1007/s101070100263.

    [19]

    M. Elad, B. Matalon and M. Zibulevsky, Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization, Appl. Comput. Harmon. Anal., 23 (2007), 346-367.doi: 10.1016/j.acha.2007.02.002.

    [20]

    M. Fukushima and H. Mine, A generalized proximal point algorithm for certain non-convex minimization problems, Int. J. Syst. Sci., 12 (1981), 989-1000.doi: 10.1080/00207728108963798.

    [21]

    M. A. T. Figueiredo and R. D. Nowak, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process., 12 (2003), 906-916.doi: 10.1109/TIP.2003.814255.

    [22]

    M. A. T. Figueiredo, R. D. Nowak and S. J. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems, IEEE J. Sel. Top. Signal Process., 1 (2007), 586-597.doi: 10.1109/JSTSP.2007.910281.

    [23]

    M. Fukushima, A successive quadratic programming method for a class of constrained nonsmooth optimization problems, Math. Program., 49 (1990/91), 231-251. doi: 10.1007/BF01588789.

    [24]

    L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton's method, SIAM J. Numer. Anal., 23 (1986), 707-716.doi: 10.1137/0723046.

    [25]

    E. T. Hale, W. Yin and Y. Zhang, Fixed-point continuation for $l_1$ minimization: Methodology and convergence, SIAM J. Optim., 19 (2008), 1107-1130.doi: 10.1137/070698920.

    [26]

    W. W. Hager, D. T. Phan and H. Zhang, Gradient-based methods for sparse recovery, SIAM J. Imaging Sci., 4 (2011), 146-165.doi: 10.1137/090775063.

    [27]

    K. C. Kiwiel, A method for minimizing the sum of a convex function and a continuously differentiable function, J. Optim. Theory Appl., 48 (1986), 437-449.doi: 10.1007/BF00940570.

    [28]

    S. J. Kim, K. Koh, M. Lustig, S. Boyd and D. Gorinevsky, An interior-point method for large-scale $l_1$-regularized least squares, IEEE J. Sel. Top. Signal Process., 1 (2007), 606-617.

    [29]

    H. Mine and M. Fukushima, A minimization method for the sum of a convex function and a continuously differentiable function, J. Optim. Theory Appl., 33 (1981), 9-23.doi: 10.1007/BF00935173.

    [30]

    Y. Nesterov, Gradient methods for minimizing composite objective function, 2007, CORE Discussion Paper 2007/76 [Online]. Available from: http://www.optimization-online.org/DB_HTML/2007/09/1784.html.

    [31]

    R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, NJ, 1970.

    [32]

    S. M. Robinson, Linear convergence of $\epsilon$-subgradient descent methods for a class of convex functions, Math. Program., 86 (1999), 41-50.doi: 10.1007/s101070050078.

    [33]

    M. Saunders, PDCO: Primal-Dual Interior Method for Convex Objectives 2002 [Online]. Available from: http://web.stanford.edu/group/SOL/software/pdco/.

    [34]

    P. Tseng and S. W. Yun, A coordinate gradient descent method for nonsmooth separable minimization, Math. Program., 117 (2009), 387-423.doi: 10.1007/s10107-007-0170-0.

    [35]

    J. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Inform. Theory, 50 (2006), 2231-2342.doi: 10.1109/TIT.2004.834793.

    [36]

    Z. W. Wen, W. T. Yin, D. Goldfarb and Y. Zhang, A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation, SIAM J. Sci. Comput., 32 (2010), 1832-1857.doi: 10.1137/090747695.

    [37]

    Z. W. Wen, W. T. Yin, H. Zhang and D. Goldfarb, On the convergence of an active-set method for $l_1$ minimization, Optim. Methods Softw., 27 (2012), 1127-1146.doi: 10.1080/10556788.2011.591398.

    [38]

    J. Wright, R. D. Nowak and M. A. T. Figueiredo, Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57 (2009), 2479-2493.doi: 10.1109/TSP.2009.2016892.

    [39]

    W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1 (2008), 143-168.doi: 10.1137/070703983.

  • 加载中
SHARE

Article Metrics

HTML views() PDF downloads(47) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return